diff options
Diffstat (limited to 'gcc-1.40/loop.c')
| -rw-r--r-- | gcc-1.40/loop.c | 5436 |
1 files changed, 5436 insertions, 0 deletions
diff --git a/gcc-1.40/loop.c b/gcc-1.40/loop.c new file mode 100644 index 0000000..3097efb --- /dev/null +++ b/gcc-1.40/loop.c @@ -0,0 +1,5436 @@ +/* Move constant computations out of loops. + Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 1, or (at your option) +any later version. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +/* This is the loop optimization pass of the compiler. + It finds invariant computations within loops and moves them + to the beginning of the loop. Then it identifies basic and + general induction variables. Strength reduction is applied to the general + induction variables, and induction variable elimination is applied to + the basic induction variables. + + It also finds cases where + a register is set within the loop by zero-extending a narrower value + and changes these to zero the entire register once before the loop + and merely copy the low part within the loop. + + Most of the complexity is in heuristics to decide when it is worth + while to do these things. */ + +/* ??? verify_loop would run faster if we made one table + of the minimum and maximum luids from which each label is reached. + Also, it would be faster if loop_store_addrs were a hash table. */ + +#include "config.h" +#include "rtl.h" +#include "expr.h" +#include "insn-config.h" +#include "regs.h" +#include "hard-reg-set.h" +#include "recog.h" +#include "flags.h" +#include <stdio.h> + +/* Vector mapping INSN_UIDs to luids. + The luids are like uids but increase monononically always. + We use them to see whether a jump comes from outside a given loop. */ + +static int *uid_luid; + +/* Get the luid of an insn. */ + +#define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)]) + +/* 1 + largest uid of any insn. */ + +static int max_uid; + +/* 1 + luid of last insn. */ + +static int max_luid; + +/* Nonzero if somewhere in the current loop + there is either a subroutine call, + or a store into a memory address that is not fixed, + or a store in a BLKmode memory operand, + or too many different fixed addresses stored in + to record them all in `loop_store_addrs'. + + In any of these cases, no memory location can be regarded + as invariant. */ + +static int unknown_address_altered; + +/* Nonzero if somewhere in the current loop there is a store + into a memory address that is not fixed but is known to be + part of an aggregate. + + In this case, no memory reference in an aggregate may be + considered invariant. */ + +static int unknown_aggregate_altered; + +/* Nonzero if somewhere in the current loop there is a store + into a memory address other than a fixed address not in an aggregate. + + In this case, no memory reference in an aggregate at a varying address + may be considered invariant. */ + +static int fixed_aggregate_altered; + +/* Nonzero if there is a subroutine call in the current loop. + (unknown_address_altered is also nonzero in this case.) */ + +static int loop_has_call; + +/* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the + current loop. A continue statement will generate a branch to + NEXT_INSN (loop_continue). */ + +static rtx loop_continue; + +/* Indexed by register number, contains the number of times the reg + is set during the loop being scanned. + During code motion, -1 indicates a reg that has been made a candidate. + After code motion, regs moved have 0 (which is accurate now) + while the failed candidates have the original number of times set. + + Therefore, at all times, 0 indicates an invariant register; + -1 a conditionally invariant one. */ + +static short *n_times_set; + +/* Original value of n_times_set; same except that this value + is not set to -1 for a reg whose sets have been made candidates + and not set to 0 for a reg that is moved. */ + +static short *n_times_used; + +/* Index by register number, 1 indicates that the register + cannot be moved or strength reduced. */ + +static char *may_not_optimize; + +/* Nonzero means reg N has already been moved out of one loop. + This reduces the desire to move it out of another. */ + +static char *moved_once; + +/* Array of fixed memory addresses that are stored in this loop. + If there are too many to fit here, + we just turn on unknown_address_altered. */ + +#define NUM_STORES 10 +static rtx loop_store_addrs[NUM_STORES]; +static int loop_store_widths[NUM_STORES]; + +/* Index of first available slot in above array. */ +static int loop_store_addrs_idx; + +/* Count of movable (i.e. invariant) instructions discovered in the loop. */ +static int num_movables; + +/* Count of memory write instructions discovered in the loop. */ +static int num_mem_sets; + +/* Number of loops contained within the current one, including itself. */ +static int loops_enclosed; + +/* Bound on pseudo register number before loop optimization. + A pseudo has valid regscan info if its number is < old_max_reg. */ +static int old_max_reg; + +/* During the analysis of a loop, a chain of `struct movable's + is made to record all the movable insns found. + Then the entire chain can be scanned to decide which to move. */ + +struct movable +{ + rtx insn; /* A movable insn */ + rtx set_src; /* The expression this reg is set from. + Either SET_SRC (body) or a REG_EQUAL. */ + int consec; /* Number of consecutive following insns + that must be moved with this one. */ + int regno; /* The register it sets */ + short lifetime; /* lifetime of that register; + may be adjusted when matching movables + that load the same value are found. */ + short savings; /* Number of insns we can move for this reg, + including other movables that force this + or match this one. */ + unsigned int cond : 1; /* 1 if only conditionally movable */ + unsigned int force : 1; /* 1 means MUST move this insn */ + unsigned int global : 1; /* 1 means reg is live outside this loop */ + /* If PARTIAL is 1, GLOBAL means something different: + that the reg is live outside the range from where it is set + to the following label. */ + unsigned int done : 1; /* 1 inhibits further processing of this */ + /* 1 in PARTIAL means this reg is used for zero-extending. + In particular, moving it does not make it invariant. */ + unsigned int partial : 1; + enum machine_mode savemode; /* Nonzero means it is a mode for a low part + that we should avoid changing when clearing + the rest of the reg. */ + struct movable *match; /* First entry for same value */ + struct movable *forces; /* An insn that must be moved if this is */ + struct movable *next; +}; + +static FILE *loop_dump_stream; + +/* Forward declarations. */ + +struct induction; +struct iv_class; + +static rtx loop_find_reg_equal (); +static int reg_in_basic_block_p (); +static rtx verify_loop (); +static int invariant_p (); +static int consec_sets_invariant_p (); +static int can_jump_into_range_p (); +static int labels_in_range_p (); +static void count_loop_regs_set (); +static void note_addr_stored (); +static int loop_reg_used_before_p (); +static void constant_high_bytes (); +static void scan_loop (); +static rtx replace_regs (); +static void replace_call_address (); +static rtx skip_consec_insns (); +static void ignore_some_movables (); +static void force_movables (); +static void combine_movables (); +static int rtx_equal_for_loop_p (); +static void move_movables (); +static void strength_reduce (); +static void find_mem_givs (); +static void record_giv (); +static void delete_insn_forces (); +static int basic_induction_var (); +static int general_induction_var (); +static int consec_sets_giv (); +static int check_dbra_loop (); +static void emit_iv_init_code (); +static int product_cheap_p (); +static void emit_iv_inc (); +static void check_eliminate_biv (); +static int can_eliminate_biv_p (); +static void eliminate_biv (); +static rtx final_biv_value (); +static int last_use_this_basic_block (); + +/* Entry point of this file. Perform loop optimization + on the current function. F is the first insn of the function + and DUMPFILE is a stream for output of a trace of actions taken + (or 0 if none should be output). */ + +void +loop_optimize (f, dumpfile) + /* f is the first instruction of a chain of insns for one function */ + rtx f; + FILE *dumpfile; +{ + register rtx insn; + register int i; + rtx end; + rtx last_insn; + + loop_dump_stream = dumpfile; + + init_recog (); + + old_max_reg = max_reg_num (); + + moved_once = (char *) alloca (old_max_reg); + bzero (moved_once, old_max_reg); + + /* First find the last real insn, and count the number of insns, + and assign insns their luids. */ + + for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) + if (INSN_UID (insn) > i) + i = INSN_UID (insn); + + max_uid = i + 1; + uid_luid = (int *) alloca ((i + 1) * sizeof (int)); + bzero (uid_luid, (i + 1) * sizeof (int)); + + /* Compute the mapping from uids to luids. + LUIDs are numbers assigned to insns, like uids, + except that luids increase monotonically through the code. + Don't assign luids to line-number NOTEs, so that the distance in luids + between two insns is not affected by -g. */ + + for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) + { + last_insn = insn; + if (GET_CODE (insn) != NOTE + || NOTE_LINE_NUMBER (insn) < 0) + INSN_LUID (insn) = ++i; + else + /* Give a line number note the same luid as preceding insn. */ + INSN_LUID (insn) = i; + } + + max_luid = i; + + /* Don't leave gaps in uid_luid for insns that have been + deleted. It is possible that the first or last insn + using some register has been deleted by cross-jumping. + Make sure that uid_luid for that former insn's uid + points to the general area where that insn used to be. */ + for (i = 0; i < max_uid; i++) + { + uid_luid[0] = uid_luid[i]; + if (uid_luid[0] != 0) + break; + } + for (i = 0; i < max_uid; i++) + if (uid_luid[i] == 0) + uid_luid[i] = uid_luid[i - 1]; + + /* Find and process each loop. + We scan from the end, and process each loop when its start is seen, + so we process innermost loops first. */ + + for (insn = last_insn; insn; insn = PREV_INSN (insn)) + if (GET_CODE (insn) == NOTE + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) + { + /* Make sure it really is a loop -- no jumps in from outside. */ + end = verify_loop (f, insn); + if (end != 0) + /* If so, optimize this loop. */ + scan_loop (insn, end, max_reg_num ()); + else if (loop_dump_stream) + fprintf (loop_dump_stream, + "\nLoop at %d ignored due to multiple entry points.\n", + INSN_UID (insn)); + } +} + +/* Optimize one loop whose start is LOOP_START and end is END. + LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching + NOTE_INSN_LOOP_END. */ + +/* ??? can also move memory writes out of loop if destination + address is invariant? */ + +static void +scan_loop (loop_start, end, nregs) + rtx loop_start, end; + int nregs; +{ + register int i; + register rtx p = NEXT_INSN (loop_start); + /* 1 if we are scanning insns that could be executed zero times. */ + int maybe_never = 0; + /* 1 if we are scanning insns that might never be executed + due to a subroutine call which might exit before they are reached. */ + int call_passed = 0; + /* For a rotated loop that is entered near the bottom, + this is the label at the top. Otherwise it is zero. */ + rtx loop_top = 0; + /* Jump insn that enters the loop, or 0 if control drops in. */ + rtx loop_entry_jump = 0; + /* Place in the loop where control enters. */ + rtx scan_start; + /* Number of insns in the loop. */ + int insn_count; + int tem; + rtx temp; + /* Chain describing insns movable in current loop. */ + struct movable *movables = 0; + /* Last element in `movables' -- so we can add elements at the end. */ + struct movable *last_movable = 0; + /* Ratio of extra register life span we can justify + for saving an instruction. More if loop doesn't call subroutines + since in that case saving an insn makes more difference + and more registers are available. */ + int threshold = loop_has_call ? 15 : 30; + /* Nonzero if the insn that jumps into the real loop + is not the very first thing after the loop-beginning note. */ + int something_before_entry_jump = 0; + + n_times_set = (short *) alloca (nregs * sizeof (short)); + n_times_used = (short *) alloca (nregs * sizeof (short)); + may_not_optimize = (char *) alloca (nregs); + + /* Determine whether this loop starts with a jump down + to a test at the end. */ + while (p != end + && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN) + { + if (GET_CODE (p) == CALL_INSN || GET_CODE (p) == INSN) + something_before_entry_jump = 1; + p = NEXT_INSN (p); + } + + /* "Loop" contains neither jumps nor labels; + it must have been a dummy. Think no more about it. */ + if (p == end) + return; + + scan_start = p; + + /* If loop has a jump before the first label, + the true entry is the target of that jump. + Start scan from there. + But record in LOOP_TOP the place where the end-test jumps + back to so we can scan that after the end of the loop. */ + if (GET_CODE (p) == JUMP_INSN) + { + loop_entry_jump = p; + loop_top = NEXT_INSN (p); + /* Loop entry will never be a conditional jump. + If we see one, this must not be a real loop. + Also, a return-insn isn't a jump to enter the loop. */ + if (GET_CODE (loop_top) != BARRIER + || GET_CODE (PATTERN (p)) != SET) + return; + /* Get the label at which the loop is entered. */ + p = XEXP (SET_SRC (PATTERN (p)), 0); + /* Check to see whether the jump actually + jumps out of the loop (meaning it's no loop). + This case can happen for things like + do {..} while (0). */ + if (p == 0 + || INSN_LUID (p) < INSN_LUID (loop_start) + || INSN_LUID (p) >= INSN_LUID (end)) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n", + INSN_UID (loop_start), INSN_UID (end)); + return; + } + + /* Find the first label after the entry-jump. */ + while (GET_CODE (loop_top) != CODE_LABEL) + { + loop_top = NEXT_INSN (loop_top); + if (loop_top == 0) + abort (); + } + + /* Maybe rearrange the loop to drop straight in + with a new test to jump around it entirely. + (The latter is considered outside the loop.) + If this is done, we no longer enter with a jump. */ + if (! something_before_entry_jump + && loop_skip_over (loop_start, end, loop_entry_jump)) + { + scan_start = loop_top; + loop_top = 0; + } + else + /* We really do enter with a jump; + scan the loop from the place where the jump jumps to. */ + scan_start = p; + } + + /* Count number of times each reg is set during this loop. + Set may_not_optimize[I] if it is not safe to move out + the setting of register I. */ + + bzero (n_times_set, nregs * sizeof (short)); + bzero (may_not_optimize, nregs); + count_loop_regs_set (loop_top ? loop_top : loop_start, end, + may_not_optimize, &insn_count, nregs); + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + may_not_optimize[i] = 1, n_times_set[i] = 1; + bcopy (n_times_set, n_times_used, nregs * sizeof (short)); + + if (loop_dump_stream) + { + fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n", + INSN_UID (loop_start), INSN_UID (end), insn_count); + if (loop_continue) + fprintf (loop_dump_stream, "Continue at insn %d.\n", + INSN_UID (loop_continue)); + } + + /* Scan through the loop finding insns that are safe to move. + In each such insn, store QImode as the mode, to mark it. + Then set n_times_set to -1 for the reg being set, so that + this reg will be considered invariant for subsequent insns. + We consider whether subsequent insns use the reg + in deciding whether it is worth actually moving. + + MAYBE_NEVER is nonzero if we have passed a conditional jump insn + and therefore it is possible that the insns we are scanning + would never be executed. At such times, we must make sure + that it is safe to execute the insn once instead of zero times. + When MAYBE_NEVER is 0, all insns will be executed at least once + so that is not a problem. */ + + p = scan_start; + while (1) + { + p = NEXT_INSN (p); + /* At end of a straight-in loop, we are done. + At end of a loop entered at the bottom, scan the top. */ + if (p == scan_start) + break; + if (p == end) + { + if (loop_top != 0) + p = NEXT_INSN (loop_top); + else + break; + if (p == scan_start) + break; + } + if (GET_CODE (p) == INSN + && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))]) + { + int tem1 = 0; + /* Don't try to optimize a register that was made + by loop-optimization for an inner loop. + We don't know its life-span, so we can't compute the benefit. */ + if (REGNO (SET_DEST (PATTERN (p))) >= old_max_reg) + ; + /* IN order to move a register, we need to have one of three cases: + (1) it is used only in the same basic block as the set + (2) it is not a user variable. + (3) the set is guaranteed to be executed once the loop starts, + and the reg is not used until after that. */ + else if (! ((! maybe_never + && ! loop_reg_used_before_p (p, loop_start, scan_start, end)) + || ! REG_USERVAR_P (SET_DEST (PATTERN (p))) + || reg_in_basic_block_p (p, SET_DEST (PATTERN (p))))) + ; + else if (((tem = invariant_p (SET_SRC (PATTERN (p)))) + || ((temp = loop_find_reg_equal (p)) + && (tem = invariant_p (XEXP (temp, 0))))) + && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1 + || (tem1 + = consec_sets_invariant_p (SET_DEST (PATTERN (p)), + n_times_set[REGNO (SET_DEST (PATTERN (p)))], + p))) + /* If the insn can cause a trap (such as divide by zero), + can't move it unless it's guaranteed to be executed + once loop is entered. Even a function call might + prevent the trap insn from being reached + (since it might exit!) */ + && ! ((maybe_never || call_passed) + && (may_trap_p (SET_SRC (PATTERN (p))) + || ((temp = loop_find_reg_equal (p)) + && may_trap_p (XEXP (temp, 0)))))) + { + register struct movable *m; + register int regno = REGNO (SET_DEST (PATTERN (p))); + int count; + m = (struct movable *) alloca (sizeof (struct movable)); + m->next = 0; + m->insn = p; + temp = loop_find_reg_equal (p); + if (temp) + m->set_src = XEXP (temp, 0); + else + m->set_src = SET_SRC (PATTERN (p)); + m->force = 0; + m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1; + m->done = 0; + m->forces = 0; + m->partial = 0; + m->savemode = VOIDmode; + m->regno = regno; + /* Set M->cond if either invariant_p or consec_sets_invariant_p + returned 2 (only conditionally invariant). */ + m->cond = ((tem | tem1) > 1); + m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) + || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); + m->match = 0; + m->lifetime = (uid_luid[regno_last_uid[regno]] + - uid_luid[regno_first_uid[regno]]); + m->savings = n_times_used[regno]; + n_times_set[regno] = -1; + /* Add M to the end of the chain MOVABLES. */ + if (movables == 0) + movables = m; + else + last_movable->next = m; + last_movable = m; + if (m->consec > 0) + { + /* Skip this insn, not checking REG_LIBCALL notes. */ + p = NEXT_INSN (p); + /* Skip the consecutive insns, if there are any. */ + p = skip_consec_insns (p, m->consec); + /* Back up, so the main loop will advance to the right place. */ + p = PREV_INSN (p); + } + } + /* If this register is always set within a STRICT_LOW_PART + or set to zero, then its high bytes are constant. + So clear them outside the loop and within the loop + just load the low bytes. + We must check that the machine has an instruction to do so. + Also, if the value loaded into the register + depends on the same register, this cannot be done. */ + else if (SET_SRC (PATTERN (p)) == const0_rtx + && GET_CODE (NEXT_INSN (p)) == INSN + && GET_CODE (PATTERN (NEXT_INSN (p))) == SET + && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p)))) + == STRICT_LOW_PART) + && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) + == SUBREG) + && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) + == SET_DEST (PATTERN (p))) + && !reg_mentioned_p (SET_DEST (PATTERN (p)), + SET_SRC (PATTERN (NEXT_INSN (p))))) + { + register int regno = REGNO (SET_DEST (PATTERN (p))); + if (n_times_set[regno] == 2) + { + register struct movable *m; + int count; + m = (struct movable *) alloca (sizeof (struct movable)); + m->next = 0; + m->insn = p; + m->force = 0; + m->consec = 0; + m->done = 0; + m->forces = 0; + m->partial = 1; + /* If the insn may not be executed on some cycles, + we can't clear the whole reg; clear just high part. + Not even if the reg is used only within this loop. + Consider this: + while (1) + while (s != t) { + if (foo ()) x = *s; + use (x); + } + Clearing x before the inner loop could clobber a value + being saved from the last time around the outer loop. + However, if the reg is not used outside this loop + and all uses of the register are in the same + basic block as the store, there is no problem. */ + m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) + || uid_luid[regno_first_uid[regno]] < INSN_LUID (p) + || (labels_in_range_p + (p, uid_luid[regno_first_uid[regno]]))); + if (maybe_never && m->global) + m->savemode = GET_MODE (SET_SRC (PATTERN (NEXT_INSN (p)))); + else + m->savemode = VOIDmode; + m->regno = regno; + m->cond = 0; + m->match = 0; + m->lifetime = (uid_luid[regno_last_uid[regno]] + - uid_luid[regno_first_uid[regno]]); + m->savings = 1; + n_times_set[regno] = -1; + /* Add M to the end of the chain MOVABLES. */ + if (movables == 0) + movables = m; + else + last_movable->next = m; + last_movable = m; + } + } + } + /* Past a call insn, we get to insns which might not be executed + because the call might exit. This matters for insns that trap. */ + else if (GET_CODE (p) == CALL_INSN) + call_passed = 1; + /* Past a label or a jump, we get to insns for which we + can't count on whether or how many times they will be + executed during each iteration. Therefore, we can + only move out sets of trivial variables + (those not used after the loop). */ + else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) + /* If we enter the loop in the middle, and scan around + to the beginning, don't set maybe_never for that. */ + && ! (NEXT_INSN (p) == end && GET_CODE (p) == JUMP_INSN + && simplejump_p (p))) + maybe_never = 1; + } + + /* If one movable subsumes another, ignore that other. */ + + ignore_some_movables (movables); + + /* For each movable insn, see if the reg that it loads + leads when it dies right into another conditionally movable insn. + If so, record that the second insn "forces" the first one, + since the second can be moved only if the first is. */ + + force_movables (movables); + + /* See if there are multiple movable insns that load the same value. + If there are, make all but the first point at the first one + through the `match' field, and add the priorities of them + all together as the priority of the first. */ + + combine_movables (movables, nregs); + + /* Now consider each movable insn to decide whether it is worth moving. + Store 0 in n_times_set for each reg that is moved. */ + + move_movables (movables, threshold, + insn_count, loop_start, end, nregs); + + /* Now candidates that still have -1 are those not moved. + Change n_times_set to indicate that those are not actually invariant. */ + for (i = 0; i < nregs; i++) + if (n_times_set[i] < 0) + n_times_set[i] = n_times_used[i]; + + if (flag_strength_reduce) + strength_reduce (scan_start, end, loop_top, + insn_count, loop_start, end, nregs); +} + +/* Return 1 if all uses of REG + are between INSN and the end of the basic block. */ + +static int +reg_in_basic_block_p (insn, reg) + rtx insn, reg; +{ + int regno = REGNO (reg); + rtx p; + + if (regno_first_uid[regno] != INSN_UID (insn)) + return 0; + + /* Search this basic block for the already recorded last use of the reg. */ + for (p = insn; p; p = NEXT_INSN (p)) + { + switch (GET_CODE (p)) + { + case NOTE: + break; + + case INSN: + case CALL_INSN: + /* Ordinary insn: if this is the last use, we win. */ + if (regno_last_uid[regno] == INSN_UID (p)) + return 1; + break; + + case JUMP_INSN: + /* Jump insn: if this is the last use, we win. */ + if (regno_last_uid[regno] == INSN_UID (p)) + return 1; + /* Otherwise, it's the end of the basic block, so we lose. */ + return 0; + + case CODE_LABEL: + case BARRIER: + /* It's the end of the basic block, so we lose. */ + return 0; + } + } + + /* The "last use" doesn't follow the "first use"?? */ + abort (); +} + +/* Skip COUNT insns from INSN, counting library calls as 1 insn. */ + +static rtx +skip_consec_insns (insn, count) + rtx insn; + int count; +{ + for (; count > 0; count--) + { + if (GET_CODE (insn) == NOTE) + insn = NEXT_INSN (insn); + else if (GET_CODE (insn) == BARRIER || GET_CODE (insn) == CODE_LABEL) + abort (); + else + { + rtx i1, temp; + + /* If first insn of gnulib call sequence, skip to end. */ + /* Do this at start of loop, since INSN is guaranteed to + be an insn here. */ + if (temp = find_reg_note (insn, REG_LIBCALL, 0)) + insn = XEXP (temp, 0); + + do insn = NEXT_INSN (insn); + while (GET_CODE (insn) == NOTE); + } + } + + return insn; +} + +/* Find a REG_EQUAL note in INSN but only if it is safe to use for our + purposes. Those put in by CSE are not safe since they may fail to + use the registers that appear in the actual insn source. */ + +static rtx +loop_find_reg_equal (insn) + rtx insn; +{ + return (find_reg_note (insn, REG_RETVAL, 0) + ? find_reg_note (insn, REG_EQUAL, 0) + : 0); +} + +/* Ignore any movable whose insn falls within a libcall + which is part of another movable. + We make use of the fact that the movable for the libcall value + was made later and so appears later on the chain. */ + +static void +ignore_some_movables (movables) + struct movable *movables; +{ + register struct movable *m, *m1; + + for (m = movables; m; m = m->next) + { + /* Is this a movable for the value of a libcall? */ + rtx note = find_reg_note (m->insn, REG_RETVAL, 0); + if (note) + { + /* Find the beginning of that libcall. */ + rtx first_insn = XEXP (note, 0); + /* Check for earlier movables inside that range, + and mark them invalid. */ + for (m1 = movables; m1 != m; m1 = m1->next) + if (INSN_LUID (m1->insn) >= INSN_LUID (first_insn) + && INSN_LUID (m1->insn) < INSN_LUID (m->insn)) + m1->done = 1; + } + } +} + +/* For each movable insn, see if the reg that it loads + leads when it dies right into another conditionally movable insn. + If so, record that the second insn "forces" the first one, + since the second can be moved only if the first is. */ + +static void +force_movables (movables) + struct movable *movables; +{ + register struct movable *m, *m1; + for (m1 = movables; m1; m1 = m1->next) + /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */ + if (!m1->partial && !m1->done) + { + int regno = m1->regno; + for (m = m1->next; m; m = m->next) + /* ??? Could this be a bug? What if CSE caused the + register of M1 to be used after this insn? + Since CSE does not update regno_last_uid, + this insn M->insn might not be where it dies. + But very likely this doesn't matter; what matters is + that M's reg is computed from M1's reg. */ + if (INSN_UID (m->insn) == regno_last_uid[regno] + && !m->done) + break; + if (m != 0 && m->set_src == SET_DEST (PATTERN (m1->insn))) + m = 0; + + /* Increase the priority of the moving the first insn + since it permits the second to be moved as well. */ + if (m != 0) + { + m->forces = m1; + m1->lifetime += m->lifetime; + m1->savings += m1->savings; + } + } +} + +/* Find invariant expressions that are equal and can be combined into + one register. */ + +static void +combine_movables (movables, nregs) + struct movable *movables; + int nregs; +{ + register struct movable *m; + char *matched_regs = (char *) alloca (nregs); + enum machine_mode mode; + + /* Regs that are set more than once are not allowed to match + or be matched. I'm no longer sure why not. */ + /* Perhaps testing m->consec_sets would be more appropriate here? */ + + for (m = movables; m; m = m->next) + if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial) + { + register struct movable *m1; + int regno = m->regno; + + bzero (matched_regs, nregs); + matched_regs[regno] = 1; + + for (m1 = m->next; m1; m1 = m1->next) + if (m1->match == 0 && n_times_used[m1->regno] == 1 + /* A reg used outside the loop mustn't be eliminated. */ + && !m1->global + /* A reg used for zero-extending mustn't be eliminated. */ + && !m1->partial + && (matched_regs[m1->regno] + || + ( + /* Can't combine regs with different modes + even if loaded from the same constant. */ + (GET_MODE (SET_DEST (PATTERN (m->insn))) + == GET_MODE (SET_DEST (PATTERN (m1->insn)))) + /* See if the source of M1 says it matches M. */ + && ((GET_CODE (m1->set_src) == REG + && matched_regs[REGNO (m1->set_src)]) + || rtx_equal_for_loop_p (m->set_src, m1->set_src, + movables) + || (REG_NOTES (m->insn) && REG_NOTES (m1->insn) + && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV + && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV + && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0), + XEXP (REG_NOTES (m1->insn), 0))))))) + { + m->lifetime += m1->lifetime; + m->savings += m1->savings; + m1->match = m; + matched_regs[m1->regno] = 1; + } + } + + /* Now combine the regs used for zero-extension. + This can be done for those not marked `global' + provided their lives don't overlap. */ + + for (mode = VOIDmode; (int) mode < (int) MAX_MACHINE_MODE; + mode = (enum machine_mode) ((int) mode + 1)) + if (GET_MODE_CLASS (mode) == MODE_INT) + { + register struct movable *m0 = 0; + + /* Combine all the registers for extension from mode MODE. + Don't combine any that are used outside this loop. */ + for (m = movables; m; m = m->next) + if (m->partial && ! m->global + && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn))))) + { + register struct movable *m1; + int first = uid_luid[regno_first_uid[m->regno]]; + int last = uid_luid[regno_last_uid[m->regno]]; + + if (m0 == 0) + { + /* First one: don't check for overlap, just record it. */ + m0 = m; + continue; + } + + /* Make sure they extend to the same mode. + (Almost always true.) */ + if (GET_MODE (SET_DEST (PATTERN (m->insn))) + != GET_MODE (SET_DEST (PATTERN (m0->insn)))) + continue; + + /* We already have one: check for overlap with those + already combined together. */ + for (m1 = movables; m1 != m; m1 = m1->next) + if (m1 == m0 || (m1->partial && m1->match == m0)) + if (! (uid_luid[regno_first_uid[m1->regno]] > last + || uid_luid[regno_last_uid[m1->regno]] < first)) + goto overlap; + + /* No overlap: we can combine this with the others. */ + m0->lifetime += m->lifetime; + m0->savings += m->savings; + m->match = m0; + + overlap: ; + } + } +} + +/* Return 1 if regs X and Y will become the same if moved. */ + +static int +regs_match_p (x, y, movables) + rtx x, y; + struct movable *movables; +{ + int xn = REGNO (x); + int yn = REGNO (y); + struct movable *mx, *my; + + for (mx = movables; mx; mx = mx->next) + if (mx->regno == xn) + break; + + for (my = movables; my; my = my->next) + if (my->regno == yn) + break; + + return (mx && my + && ((mx->match == my->match && mx->match != 0) + || mx->match == my + || mx == my->match)); +} + +/* Return 1 if X and Y are identical-looking rtx's. + This is the Lisp function EQUAL for rtx arguments. */ + +static int +rtx_equal_for_loop_p (x, y, movables) + rtx x, y; + struct movable *movables; +{ + register int i; + register int j; + register enum rtx_code code; + register char *fmt; + + if (x == y) + return 1; + if (x == 0 || y == 0) + return 0; + + code = GET_CODE (x); + /* Rtx's of different codes cannot be equal. */ + if (code != GET_CODE (y)) + return 0; + + /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. + (REG:SI x) and (REG:HI x) are NOT equivalent. */ + + if (GET_MODE (x) != GET_MODE (y)) + return 0; + + /* These three types of rtx's can be compared nonrecursively. */ + /* Until the end of reload, + don't consider the a reference to the return register of the current + function the same as the return from a called function. This eases + the job of function integration. Once the distinction no longer + matters, the insn will be deleted. */ + if (code == REG) + return ((REGNO (x) == REGNO (y) + && REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)) + || regs_match_p (x, y, movables)); + + if (code == LABEL_REF) + return XEXP (x, 0) == XEXP (y, 0); + if (code == SYMBOL_REF) + return XSTR (x, 0) == XSTR (y, 0); + + /* Compare the elements. If any pair of corresponding elements + fail to match, return 0 for the whole things. */ + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + switch (fmt[i]) + { + case 'i': + if (XINT (x, i) != XINT (y, i)) + return 0; + break; + + case 'E': + /* Two vectors must have the same length. */ + if (XVECLEN (x, i) != XVECLEN (y, i)) + return 0; + + /* And the corresponding elements must match. */ + for (j = 0; j < XVECLEN (x, i); j++) + if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0) + return 0; + break; + + case 'e': + if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0) + return 0; + break; + + case 's': + if (strcmp (XSTR (x, i), XSTR (y, i))) + return 0; + break; + + case 'u': + /* These are just backpointers, so they don't matter. */ + break; + + case '0': + break; + + /* It is believed that rtx's at this level will never + contain anything but integers and other rtx's, + except for within LABEL_REFs and SYMBOL_REFs. */ + default: + abort (); + } + } + return 1; +} + +/* Scan MOVABLES, and move the insns that deserve to be moved. + If two matching movables are combined, replace one reg with the + other throughout. */ + +static void +move_movables (movables, threshold, insn_count, loop_start, end, nregs) + struct movable *movables; + int threshold; + int insn_count; + rtx loop_start; + rtx end; + int nregs; +{ + rtx new_start = 0; + register struct movable *m; + register rtx p; + /* Map of pseudo-register replacements to handle combining + when we move several insns that load the same value + into different pseudo-registers. */ + rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); + char *already_moved = (char *) alloca (nregs); + + bzero (already_moved, nregs); + bzero (reg_map, nregs * sizeof (rtx)); + + num_movables = 0; + + for (m = movables; m; m = m->next) + { + /* Describe this movable insn. */ + + if (loop_dump_stream) + { + fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ", + INSN_UID (m->insn), m->regno, m->lifetime); + if (m->consec > 0) + fprintf (loop_dump_stream, "consec %d, ", m->consec); + if (m->cond) + fprintf (loop_dump_stream, "cond "); + if (m->force) + fprintf (loop_dump_stream, "force "); + if (m->global) + fprintf (loop_dump_stream, "global "); + if (m->done) + fprintf (loop_dump_stream, "done "); + if (m->match) + fprintf (loop_dump_stream, "matches %d ", + INSN_UID (m->match->insn)); + if (m->forces) + fprintf (loop_dump_stream, "forces %d ", + INSN_UID (m->forces->insn)); + } + + /* Count movables. Value used in heuristics in strength_reduce. */ + num_movables++; + + /* Ignore the insn if it's already done (it matched something else). + Otherwise, see if it is now safe to move. */ + + if (!m->done + && (! m->cond + || (1 == invariant_p (m->set_src) + && (m->consec == 0 + || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)), + m->consec + 1, + m->insn)))) + && (! m->forces || m->forces->done)) + { + register int regno; + register rtx p; + int savings = m->savings; + + /* We have an insn that is safe to move. + Compute its desirability. */ + + p = m->insn; + regno = m->regno; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "savings %d ", savings); + + if (moved_once[regno]) + { + insn_count *= 2; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "halved since already moved "); + } + + /* An insn MUST be moved if we already moved something else + which is safe only if this one is moved too: that is, + if already_moved[REGNO] is nonzero. */ + + /* An insn is desirable to move if the new lifetime of the + register is no more than THRESHOLD times the old lifetime. + If it's not desirable, it means the loop is so big + that moving won't speed things up much, + and it is liable to make register usage worse. */ + + /* It is also desirable to move if it can be moved at no + extra cost because something else was already moved. */ + + if (already_moved[regno] + || (threshold * savings * m->lifetime) >= insn_count + || (m->forces && m->forces->done + && n_times_used[m->forces->regno] == 1)) + { + int count; + register struct movable *m1; + rtx first; + + /* Now move the insns that set the reg. */ + + for (count = m->consec; count >= 0; count--) + { + rtx i1, temp; + + /* If first insn of gnulib call sequence, skip to end. */ + /* Do this at start of loop, since p is guaranteed to + be an insn here. */ + if (temp = find_reg_note (p, REG_LIBCALL, 0)) + p = XEXP (temp, 0); + + /* If last insn of gnulib call sequence, move all + insns except the last before the loop. The last insn is + handled in the normal manner. */ + if (temp = find_reg_note (p, REG_RETVAL + , 0)) + { + rtx fn_address = 0; + rtx fn_reg = 0; + first = 0; + for (temp = XEXP (temp, 0); temp != p; + temp = NEXT_INSN (temp)) + { + rtx body = PATTERN (temp); + rtx n; + /* Extract the function address from the insn + that loads it into a register. + If this insn was cse'd, we get incorrect code. + So delete it and stick the fn address right + into the call insn. Since the moved insns + won't be cse'd, that does no harm. */ + if (GET_CODE (NEXT_INSN (temp)) == CALL_INSN + && GET_CODE (body) == SET + && GET_CODE (SET_DEST (body)) == REG + && (n = find_reg_note (temp, REG_EQUIV, 0))) + { + fn_reg = SET_SRC (body); + if (GET_CODE (fn_reg) != REG) + fn_reg = SET_DEST (body); + fn_address = XEXP (n, 0); + continue; + } + /* We have the call insn. + Substitute the fn address for the reg + that we believe this insn will use. */ + if (GET_CODE (temp) == CALL_INSN + && fn_address != 0) + replace_call_address (body, fn_reg, fn_address); + if (GET_CODE (temp) == CALL_INSN) + i1 = emit_call_insn_before (body, loop_start); + else + i1 = emit_insn_before (body, loop_start); + if (first == 0) + first = i1; + REG_NOTES (i1) = REG_NOTES (temp); + delete_insn (temp); + } + } + if (m->savemode != VOIDmode) + { + /* P sets REG to zero; but we should clear only the bits + that are not covered by the mode m->savemode. */ + rtx reg = SET_DEST (PATTERN (p)); + i1 = emit_insn_before + (gen_rtx (SET, VOIDmode, reg, + gen_rtx (AND, GET_MODE (reg), + reg, + gen_rtx (CONST_INT, VOIDmode, + (1 << GET_MODE_BITSIZE (m->savemode)) - 1))), + loop_start); + } + else if (GET_CODE (PATTERN (p)) == CALL_INSN) + i1 = emit_call_insn_before (PATTERN (p), loop_start); + else + i1 = emit_insn_before (PATTERN (p), loop_start); + + if (new_start == 0) + new_start = i1; + + if (loop_dump_stream) + fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1)); + + /* Mark the moved, invariant reg as being equivalent to + its constant value. */ + REG_NOTES (i1) = REG_NOTES (p); + if (REG_NOTES (i1) == 0 + && ! m->partial /* But not if it's a zero-extend clr. */ + && ! m->global /* and not if used outside the loop + (since it might get set outside). */ + && CONSTANT_P (SET_SRC (PATTERN (p)))) + REG_NOTES (i1) + = gen_rtx (EXPR_LIST, REG_EQUIV, + SET_SRC (PATTERN (p)), REG_NOTES (i1)); + + /* If library call, now fix the REG_NOTES that contain + insn pointers, namely REG_LIBCALL on FIRST + and REG_RETVAL on I1. */ + if (temp = find_reg_note (i1, REG_RETVAL, 0)) + { + XEXP (temp, 0) = first; + temp = find_reg_note (first, REG_LIBCALL, 0); + XEXP (temp, 0) = i1; + } + + delete_insn (p); + do p = NEXT_INSN (p); + while (p != 0 && GET_CODE (p) == NOTE); + } + + /* The more regs we move, the less we like moving them. */ + threshold -= 3; + + /* Any other movable that loads the same register + MUST be moved. */ + already_moved[regno] = 1; + + /* This reg has been moved out of one loop. */ + moved_once[regno] = 1; + + /* The reg set here is now invariant. */ + if (! m->partial) + n_times_set[regno] = 0; + + m->done = 1; + + /* Change the length-of-life info for the register + to say it lives at least the full length of this loop. + This will help guide optimizations in outer loops. */ + + if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start)) + /* This is the old insn before all the moved insns. + We can't use the moved insn because it is out of range + in uid_luid. Only the old insns have luids. */ + regno_first_uid[regno] = INSN_UID (loop_start); + if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end)) + regno_last_uid[regno] = INSN_UID (end); + + /* Combine with this moved insn any other matching movables. */ + + for (m1 = m->next; m1; m1 = m1->next) + if (m1->match == m) + { + rtx temp; + + /* Schedule the reg loaded by M1 + for replacement so that shares the reg of M. */ + reg_map[m1->regno] = SET_DEST (PATTERN (m->insn)); + /* Get rid of the matching insn + and prevent further processing of it. */ + m1->done = 1; + + /* if library call, delete all insn except last, which + is deleted below */ + if (temp = find_reg_note (m1->insn, REG_RETVAL, 0)) + { + for (temp = XEXP (temp, 0); temp != m1->insn; + temp = NEXT_INSN (temp)) + delete_insn (temp); + } + delete_insn (m1->insn); + + /* Any other movable that loads the same register + MUST be moved. */ + already_moved[m1->regno] = 1; + + /* The reg merged here is now invariant, + if the reg it matches is invariant. */ + if (! m->partial) + n_times_set[m1->regno] = 0; + } + } + else if (loop_dump_stream) + fprintf (loop_dump_stream, "not desirable"); + } + else if (loop_dump_stream && !m->match) + fprintf (loop_dump_stream, "not safe"); + + if (loop_dump_stream) + fprintf (loop_dump_stream, "\n"); + } + + if (new_start == 0) + new_start = loop_start; + + /* Go through all the instructions in the loop, making + all the register substitutions scheduled in REG_MAP. */ + for (p = new_start; p != end; p = NEXT_INSN (p)) + if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN + || GET_CODE (p) == CALL_INSN) + { + rtx tail; + + replace_regs (PATTERN (p), reg_map, nregs); + /* Subsitute registers in the equivalent expression also. */ + for (tail = REG_NOTES (p); tail; tail = XEXP (tail, 1)) + if (REG_NOTE_KIND (tail) == REG_EQUAL + || REG_NOTE_KIND (tail) == REG_EQUIV) + replace_regs (XEXP (tail, 0), reg_map, nregs); + } +} + +/* Optionally change a loop which enters just before the endtest + to one which falls straight in + after skipping around the entire loop if the endtest would drop out. + Returns 1 if the change was made, 0 if the loop was not really suitable. */ + +int +loop_skip_over (start, end, loop_entry_jump) + rtx start; + rtx end; + rtx loop_entry_jump; +{ + rtx entry_insn; + rtx endtest; + rtx endtestjump; + register rtx p = JUMP_LABEL (loop_entry_jump); + + while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN + && GET_CODE (p) != CALL_INSN) + p = NEXT_INSN (p); + entry_insn = p; + + /* Skip any ordinary arithmetic insns to find the compare. */ + for (; p != 0; p = NEXT_INSN (p)) + if (GET_CODE (p) != NOTE) + if (GET_CODE (p) != INSN || sets_cc0_p (PATTERN (p))) + break; + if (p == 0 || GET_CODE (p) != INSN) + return 0; + endtest = p; + endtestjump = next_real_insn (p); + + /* Check that (1) we have reached a compare insn and (2) + the insn (presumably a jump) following that compare + is the last in the loop and jumps back to the loop beginning. */ + + if (sets_cc0_p (PATTERN (endtest)) > 0 + && endtestjump == prev_real_insn (end) + && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump) + { + rtx newlab; + /* This is the jump that we insert. */ + rtx new_jump; + + /* Duplicate the ordinary arith insns before the compare. */ + for (p = entry_insn; p != endtest; p = NEXT_INSN (p)) + if (GET_CODE (p) == INSN) + { + rtx new = emit_insn_before (copy_rtx (PATTERN (p)), start); + if (REG_NOTES (p)) + REG_NOTES (new) = copy_rtx (REG_NOTES (p)); + } + + /* Ok, duplicate that test before start of loop. */ + emit_insn_before (copy_rtx (PATTERN (endtest)), start); + /* Make a new entry-jump (before the original one) + whose condition is opposite to the loop-around endtest + and which jumps around the loop (to just after the ending NOTE). */ + newlab = gen_label_rtx (); + emit_label_after (newlab, end); + emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start); + new_jump = PREV_INSN (start); + JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump); + LABEL_NUSES (JUMP_LABEL (endtestjump))++; + invert_jump (new_jump, newlab); + /* Delete the original entry-jump. */ + delete_insn (loop_entry_jump); + + return 1; + } + + return 0; +} + +/* Throughout the rtx X, replace many registers according to REG_MAP. + Return the replacement for X (which may be X with altered contents). + REG_MAP[R] is the replacement for register R, or 0 for don't replace. + NREGS is the length of REG_MAP; regs >= NREGS are not mapped. */ + +static rtx +replace_regs (x, reg_map, nregs) + rtx x; + rtx *reg_map; + int nregs; +{ + register enum rtx_code code; + register int i; + register char *fmt; + + if (x == 0) + return x; + + code = GET_CODE (x); + switch (code) + { + case PC: + case CC0: + case CONST_INT: + case CONST_DOUBLE: + case CONST: + case SYMBOL_REF: + case LABEL_REF: + return x; + + case REG: + /* Verify that the register has an entry before trying to access it. */ + if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0) + return reg_map[REGNO (x)]; + return x; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs); + if (fmt[i] == 'E') + { + register int j; + for (j = 0; j < XVECLEN (x, i); j++) + XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map, nregs); + } + } + return x; +} + +/* Scan X and replace the address of any MEM in it with ADDR. + REG is the address that MEM should have before the replacement. */ + +static void +replace_call_address (x, reg, addr) + rtx x, reg, addr; +{ + register enum rtx_code code; + register int i; + register char *fmt; + + if (x == 0) + return; + code = GET_CODE (x); + switch (code) + { + case PC: + case CC0: + case CONST_INT: + case CONST_DOUBLE: + case CONST: + case SYMBOL_REF: + case LABEL_REF: + case REG: + return; + + case SET: + /* Short cut for very common case. */ + replace_call_address (XEXP (x, 1), reg, addr); + return; + + case CALL: + /* Short cut for very common case. */ + replace_call_address (XEXP (x, 0), reg, addr); + return; + + case MEM: + /* If this MEM uses a reg other than the one we expected, + something is wrong. */ + if (XEXP (x, 0) != reg) + abort (); + XEXP (x, 0) = addr; + return; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + replace_call_address (XEXP (x, i), reg, addr); + if (fmt[i] == 'E') + { + register int j; + for (j = 0; j < XVECLEN (x, i); j++) + replace_call_address (XVECEXP (x, i, j), reg, addr); + } + } +} + +/* Return the number of memory refs to addresses that vary + in the rtx X. */ + +static int +count_nonfixed_reads (x) + rtx x; +{ + register enum rtx_code code; + register int i; + register char *fmt; + int value; + + if (x == 0) + return 0; + + code = GET_CODE (x); + switch (code) + { + case PC: + case CC0: + case CONST_INT: + case CONST_DOUBLE: + case CONST: + case SYMBOL_REF: + case LABEL_REF: + case REG: + return 0; + + case MEM: + return rtx_varies_p (XEXP (x, 0)) + count_nonfixed_reads (XEXP (x, 0)); + } + + value = 0; + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + value += count_nonfixed_reads (XEXP (x, i)); + if (fmt[i] == 'E') + { + register int j; + for (j = 0; j < XVECLEN (x, i); j++) + value += count_nonfixed_reads (XVECEXP (x, i, j)); + } + } + return value; +} + + +#if 0 +/* P is an instruction that sets a register to the result of a ZERO_EXTEND. + Replace it with an instruction to load just the low bytes + if the machine supports such an instruction, + and insert above LOOP_START an instruction to clear the register. */ + +static void +constant_high_bytes (p, loop_start) + rtx p, loop_start; +{ + register rtx new; + register int insn_code_number; + + /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) + to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ + + new = gen_rtx (SET, VOIDmode, + gen_rtx (STRICT_LOW_PART, VOIDmode, + gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), + SET_DEST (PATTERN (p)), + 0)), + XEXP (SET_SRC (PATTERN (p)), 0)); + insn_code_number = recog (new, p); + + if (insn_code_number) + { + register int i; + + /* Clear destination register before the loop. */ + emit_insn_before (gen_rtx (SET, VOIDmode, + SET_DEST (PATTERN (p)), + const0_rtx), + loop_start); + + /* Inside the loop, just load the low part. */ + PATTERN (p) = new; + } +} +#endif + +/* Verify that the ostensible loop starting at START + really is a loop: nothing jumps into it from outside. + Return the marker for the end of the loop, or zero if not a real loop. + + Also set the variables `unknown_*_altered' and `loop_has_call', + and fill in the array `loop_store_addrs'. */ + +static rtx +verify_loop (f, start) + rtx f, start; +{ + register int level = 1; + register rtx insn, end; + + /* First find the LOOP_END that matches. + Also check each insn for storing in memory and record where. */ + + unknown_address_altered = 0; + unknown_aggregate_altered = 0; + fixed_aggregate_altered = 0; + loop_has_call = 0; + loop_store_addrs_idx = 0; + + num_mem_sets = 0; + loops_enclosed = 1; + loop_continue = 0; + + for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn)) + { + if (insn == 0) + /* Parse errors can cause a loop-beg with no loop-end. */ + return 0; + if (GET_CODE (insn) == NOTE) + { + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) + { + ++level; + /* Count number of loops contained in this one. */ + loops_enclosed++; + } + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) + { + --level; + if (level == 0) + { + end = insn; + break; + } + } + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT) + { + if (level == 1) + loop_continue = insn; + } + + /* Don't optimize loops containing setjmps. + On some machines, longjmp does not restore the reg + values as of the time of the setjmp. */ + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) + return 0; + } + else if (GET_CODE (insn) == CALL_INSN) + { + unknown_address_altered = 1; + loop_has_call = 1; + } +/* ??? + else if (! unknown_address_altered) */ + else + { + if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) + note_stores (PATTERN (insn), note_addr_stored); + } + } + + /* Now scan all jumps in the function and see if any of them can + reach a label within the range of the loop. */ + + for (insn = f; insn; insn = NEXT_INSN (insn)) + if (GET_CODE (insn) == JUMP_INSN + /* Don't get fooled by jumps inserted by loop-optimize. + They don't have valid LUIDs, and they never jump into loops. */ + && INSN_UID (insn) < max_uid + && (INSN_LUID (insn) < INSN_LUID (start) + || INSN_LUID (insn) > INSN_LUID (end)) + /* We have a jump that is outside the loop. + Does it jump into the loop? */ + && can_jump_into_range_p (PATTERN (insn), + INSN_LUID (start), INSN_LUID (end))) + return 0; + +#if 0 + /* Now scan all labels between them and check for any jumps from outside. + This uses the ref-chains set up by find_basic_blocks. + This code is not used because it's more convenient for other reasons + to do the loop optimization before find_basic_blocks. */ + + for (insn = start; insn != end; insn = NEXT_INSN (insn)) + if (GET_CODE (insn) == CODE_LABEL) + { + register rtx y; + for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y)) + if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start) + || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end)) + return 0; + } +#endif + + return end; +} + +/* Return 1 if somewhere in X is a LABEL_REF to a label + located between BEG and END. */ + +static int +can_jump_into_range_p (x, beg, end) + rtx x; + int beg, end; +{ + register enum rtx_code code = GET_CODE (x); + register int i; + register char *fmt; + + if (code == LABEL_REF) + { + register int luid = INSN_LUID (XEXP (x, 0)); + return luid > beg && luid < end; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + { + if (can_jump_into_range_p (XEXP (x, i), beg, end)) + return 1; + } + else if (fmt[i] == 'E') + { + register int j; + for (j = 0; j < XVECLEN (x, i); j++) + if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end)) + return 1; + } + } + + return 0; +} + +/* Return nonzero if there is a label in the range from + insn INSN to the insn whose luid is END. */ + +static int +labels_in_range_p (insn, end) + rtx insn; + int end; +{ + while (insn && INSN_LUID (insn) <= end) + { + if (GET_CODE (insn) == CODE_LABEL) + return 0; + insn = NEXT_INSN (insn); + } + + return 0; +} + +/* Record that a memory reference X is being set. */ + +static void +note_addr_stored (x) + rtx x; +{ + if (x == 0 || GET_CODE (x) != MEM) + return; + + /* Count number of memory writes. + This affects heuristics in strength_reduce. */ + num_mem_sets++; + if (unknown_address_altered) + return; + + if (GET_MODE (x) == BLKmode) + unknown_address_altered = 1; + else if (rtx_addr_varies_p (x)) + { + if (GET_CODE (XEXP (x, 0)) == PLUS) + unknown_aggregate_altered = 1; + else + unknown_address_altered = 1; + } + else + { + register int i; + register rtx addr = XEXP (x, 0); + + if (MEM_IN_STRUCT_P (x)) + fixed_aggregate_altered = 1; + for (i = 0; i < loop_store_addrs_idx; i++) + if (rtx_equal_p (loop_store_addrs[i], addr)) + { + if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x))) + loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); + break; + } + if (i == NUM_STORES) + unknown_address_altered = 1; + else if (i == loop_store_addrs_idx) + { + loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); + loop_store_addrs[loop_store_addrs_idx++] = addr; + } + } +} + +/* Return nonzero if the rtx X is invariant over the current loop. + + The value is 2 if we refer to something only conditionally invariant. + + If `unknown_address_altered' is nonzero, no memory ref is invariant. + Otherwise if `unknown_aggregate_altered' is nonzero, + a memory ref is invariant if it is not part of an aggregate + and its address is fixed and not in `loop_store_addrs'. + Otherwise if `fixed_aggregate_altered' is nonzero, + a memory ref is invariant + if its address is fixed and not in `loop_store_addrs'. + Otherwise, a memory ref is invariant if its address is fixed and not in + `loop_store_addrs' or if it is not an aggregate. */ + +static int +invariant_p (x) + register rtx x; +{ + register int i; + register enum rtx_code code; + register char *fmt; + int conditional = 0; + + if (x == 0) + return 1; + code = GET_CODE (x); + switch (code) + { + case CONST_INT: + case CONST_DOUBLE: + case SYMBOL_REF: + case LABEL_REF: + case CONST: + return 1; + + case PC: + case CC0: + return 0; + + case REG: + /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid + since the reg might be set by initialization within the loop. */ + if (x == frame_pointer_rtx || x == arg_pointer_rtx) + return 1; + if (n_times_set[REGNO (x)] == -1) + return 2; + return n_times_set[REGNO (x)] == 0; + + case MEM: + /* Constants in the constant pool are invariant. + ?? Really we should detect any constant address in the + text section. */ + if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF + && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))) + return 1; + /* A store in a varying-address scalar (or a subroutine call) + could clobber anything in memory. */ + if (unknown_address_altered) + return 0; + /* Don't mess with volatile memory references. */ + if (MEM_VOLATILE_P (x)) + return 0; +#if 0 + /* If it's declared read-only, it is invariant + if its address is invariant. */ + if (RTX_UNCHANGING_P (x)) + return invariant_p (XEXP (x, 0)); +#endif + /* A store in a varying-address aggregate component + could clobber anything except a scalar with a fixed address. */ + if (unknown_aggregate_altered + && ((MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) + || rtx_addr_varies_p (x))) + return 0; + /* A store in a fixed-address aggregate component + could clobber anything whose address is not fixed, + even an aggregate component. */ + if (fixed_aggregate_altered + && rtx_addr_varies_p (x)) + return 0; + /* Any store could clobber a varying-address scalar. */ + if (loop_store_addrs_idx + && !(MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) + && rtx_addr_varies_p (x)) + return 0; + /* A store in a fixed address clobbers overlapping references. */ + for (i = loop_store_addrs_idx - 1; i >= 0; i--) + if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i])) + return 0; + /* It's not invalidated by a store in memory + but we must still verify the address is invariant. */ + break; + + case ASM_OPERANDS: + /* Don't mess with insns declared volatile. */ + if (MEM_VOLATILE_P (x)) + return 0; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + { + int tem = invariant_p (XEXP (x, i)); + if (tem == 0) + return 0; + if (tem == 2) + conditional = 1; + } + else if (fmt[i] == 'E') + { + register int j; + for (j = 0; j < XVECLEN (x, i); j++) + { + int tem = invariant_p (XVECEXP (x, i, j)); + if (tem == 0) + return 0; + if (tem == 2) + conditional = 1; + } + + } + } + + return 1 + conditional; +} + +/* Return 1 if OTHER (a mem ref) overlaps the area of memory + which is SIZE bytes starting at BASE. */ + +int +addr_overlap_p (other, base, size) + rtx other; + rtx base; + int size; +{ + int start = 0, end; + + if (GET_CODE (base) == CONST) + base = XEXP (base, 0); + if (GET_CODE (base) == PLUS + && GET_CODE (XEXP (base, 1)) == CONST_INT) + { + start = INTVAL (XEXP (base, 1)); + base = XEXP (base, 0); + } + + end = start + size; + return refers_to_mem_p (other, base, start, end); +} + +/* Return nonzero if all the insns in the loop that set REG + are INSN and the immediately following insns, + and if each of those insns sets REG in an invariant way + (not counting uses of REG in them). + + The value is 2 if some of these insns are only conditionally invariant. + + We assume that INSN itself is the first set of REG + and that its source is invariant. */ + +static int +consec_sets_invariant_p (reg, n_sets, insn) + int n_sets; + rtx reg, insn; +{ + register rtx p = insn; + register int regno = REGNO (reg); + rtx temp; + /* Number of sets we have to insist on finding after INSN. */ + int count = n_sets - 1; + int old = n_times_set[regno]; + int value = 0; + int this; + + /* If N_SETS hit the limit, we can't rely on its value. */ + if (n_sets == 127) + return 0; + + n_times_set[regno] = 0; + + while (count > 0) + { + register enum rtx_code code; + p = NEXT_INSN (p); + code = GET_CODE (p); + + /* If library call, skip to end of of it. */ + if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) + p = XEXP (temp, 0); + + this = 0; + if (code == INSN && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && REGNO (SET_DEST (PATTERN (p))) == regno) + { + this = invariant_p (SET_SRC (PATTERN (p))); + if (this != 0) + value |= this; + else if (temp = loop_find_reg_equal (p)) + { + this = invariant_p (XEXP (temp, 0)); + if (this != 0) + value |= this; + } + } + if (this != 0) + count--; + else if (code != NOTE) + { + n_times_set[regno] = old; + return 0; + } + } + + n_times_set[regno] = old; + /* If invariant_p ever returned 2, we return 2. */ + return 1 + (value & 2); +} + +#if 0 +/* I don't think this condition is sufficient to allow INSN + to be moved, so we no longer test it. */ + +/* Return 1 if all insns in the basic block of INSN and following INSN + that set REG are invariant according to TABLE. */ + +static int +all_sets_invariant_p (reg, insn, table) + rtx reg, insn; + short *table; +{ + register rtx p = insn; + register int regno = REGNO (reg); + + while (1) + { + register enum rtx_code code; + p = NEXT_INSN (p); + code = GET_CODE (p); + if (code == CODE_LABEL || code == JUMP_INSN) + return 1; + if (code == INSN && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && REGNO (SET_DEST (PATTERN (p))) == regno) + { + if (!invariant_p (SET_SRC (PATTERN (p)), table)) + return 0; + } + } +} +#endif /* 0 */ + +/* Increment N_TIMES_SET at the index of each register + that is modified by an insn between FROM and TO. + If the value of an element of N_TIMES_SET becomes 127 or more, + stop incrementing it, to avoid overflow. + + Store in *COUNT_PTR the number of actual instruction + in the loop. We use this to decide what is worth moving out. */ + +/* last_set[n] is nonzero iff reg n has been set in the current basic block. + In that case, it is the insn that last set reg n. */ + +static void +count_loop_regs_set (from, to, may_not_move, count_ptr, nregs) + register rtx from, to; + char *may_not_move; + int *count_ptr; + int nregs; +{ + register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); + register rtx insn; + register int count = 0; + register rtx dest; + + bzero (last_set, nregs * sizeof (rtx)); + for (insn = from; insn != to; insn = NEXT_INSN (insn)) + { + if (GET_CODE (insn) == CALL_INSN) + { + /* If a register is used as a subroutine address, + don't allow this register's setting to be moved out of the loop. + This condition is not at all logically correct + but it averts a very common lossage pattern + and creates lossage much less often. */ + if (GET_CODE (PATTERN (insn)) == CALL + && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM + && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG) + { + register int regno + = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0)); + may_not_move[regno] = 1; + } + else if (GET_CODE (PATTERN (insn)) == SET + && GET_CODE (SET_SRC (PATTERN (insn))) == CALL + && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM + && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG) + { + register int regno + = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)); + may_not_move[regno] = 1; + /* The call insn itself sets a reg, which cannot be moved. */ + may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1; + if (n_times_set[REGNO (SET_DEST (PATTERN (insn)))] < 127) + n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++; + } + } + if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) + { + ++count; + if (GET_CODE (PATTERN (insn)) == CLOBBER + && GET_CODE (XEXP (PATTERN (insn), 0)) == REG) + /* Don't move a reg that has an explicit clobber. + We might do so sometimes, but it's not worth the pain. */ + may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1; + else if (GET_CODE (PATTERN (insn)) == SET) + { + dest = SET_DEST (PATTERN (insn)); + while (GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT + || GET_CODE (dest) == SIGN_EXTRACT + || GET_CODE (dest) == STRICT_LOW_PART) + dest = XEXP (dest, 0); + if (GET_CODE (dest) == REG) + { + register int regno = REGNO (dest); + /* If this is the first setting of this reg + in current basic block, and it was set before, + it must be set in two basic blocks, so it cannot + be moved out of the loop. */ + if (n_times_set[regno] > 0 && last_set[regno] == 0) + may_not_move[regno] = 1; + /* If this is not first setting in current basic block, + see if reg was used in between previous one and this. + If so, neither one can be moved. */ + if (last_set[regno] != 0 + && reg_used_between_p (dest, last_set[regno], insn)) + may_not_move[regno] = 1; + if (n_times_set[regno] < 127) + ++n_times_set[regno]; + last_set[regno] = insn; + } + } + else if (GET_CODE (PATTERN (insn)) == PARALLEL) + { + register int i; + for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) + { + register rtx x = XVECEXP (PATTERN (insn), 0, i); + if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG) + /* Don't move a reg that has an explicit clobber. + It's not worth the pain to try to do it correctly. */ + may_not_move[REGNO (XEXP (x, 0))] = 1; + if (GET_CODE (x) == SET) + { + dest = SET_DEST (x); + while (GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT + || GET_CODE (dest) == SIGN_EXTRACT + || GET_CODE (dest) == STRICT_LOW_PART) + dest = XEXP (dest, 0); + if (GET_CODE (dest) == REG) + { + register int regno = REGNO (dest); + if (n_times_set[regno] < 127) + ++n_times_set[regno]; + may_not_move[regno] = 1; + last_set[regno] = insn; + } + } + } + } + } + if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) + bzero (last_set, nregs * sizeof (rtx)); + } + *count_ptr = count; +} + +/* Given a loop that is bounded by LOOP_START and LOOP_END + and that is entered at SCAN_START, + return 1 if the register set by insn INSN is used by + any insn that precedes INSN in cyclic order starting + from the loop entry point. */ + +static int +loop_reg_used_before_p (insn, loop_start, scan_start, loop_end) + rtx insn, loop_start, scan_start, loop_end; +{ + rtx reg = SET_DEST (PATTERN (insn)); + rtx p; + + /* Scan forward checking for register usage. If we hit INSN, we + are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */ + for (p = scan_start; p != insn; p = NEXT_INSN (p)) + { + if ((GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN + || GET_CODE (p) == JUMP_INSN) + && reg_overlap_mentioned_p (reg, PATTERN (p))) + return 1; + + if (p == loop_end) + p = loop_start; + } + + return 0; +} + +/* A "basic induction variable" or biv is a pseudo reg that is set + (within this loop) only by incrementing or decrementing it. */ +/* A "general induction variable" or giv is a pseudo reg whose + value is a linear function of a biv. */ + +/* Bivs are recognized by `basic_induction_var'; + Givs by `general_induct_var'. */ + +/* An enum for the two different types of givs, those that are used + as memory addresses and those that are calculated into registers. */ +enum g_types { DEST_ADDR, DEST_REG }; + +/* A `struct induction' is created for every instruction that sets + an induction variable (either a biv or a giv). */ + +struct induction +{ + rtx insn; /* The insn that sets a biv or giv */ + rtx new_reg; /* New register, containing strength reduced + version of this giv. */ + int src_regno; /* Biv from which this giv is computed. + (If this is a biv, then this is the biv.) */ + enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG giv */ + int dest_regno; /* Destination register for insn: this is the + register which was the biv or giv. + For a biv, this equals src_reg. + For a DEST_ADDR type giv, this is 0. */ + rtx *location; /* Place in the insn where this giv occurs. + If GIV_TYPE is DEST_REG, this is 0. */ + enum machine_mode mode; /* The mode of this biv or giv */ + rtx mult_val; /* Multiplicative factor for src_reg. */ + rtx add_val; /* Additive constant for that product. */ + int benefit; /* Gain from eliminating this insn. */ + int consec; /* The number of consecutive insn that set this + register; they are all eliminated if this + one is. */ + char replaceable; /* 1 if we can substitute the strength-reduced + variable for the original variable. + 0 means they must be kept separate and the + new one must be copied into the old pseudo + reg each time the old one is set. */ + char ignore; /* 1 prohibits further processing of this giv */ + int lifetime; /* Length of life of this giv */ + int times_used; /* # times this giv is used. */ + struct induction *family; /* Links together all induction variables that + have the same src register. */ + struct induction *forces; /* Points to an induction variable insn which + is used only once, to compute this giv, + and hence can be deleted if this insn is + strength reduced. */ + struct induction *forces2; /* Likewise. */ + struct induction *same; /* Links together all induction variables that + have the same tuple (src, mult, add). */ +}; + +/* A `struct iv_class' is created for each biv. */ + +struct iv_class { + int regno; /* Pseudo reg which is the biv. */ + int biv_count; /* Number of insns setting this reg. */ + struct induction *biv; /* List of all insns that set this reg. */ + int giv_count; /* Number of DEST_REG givs computed from this + biv. The resulting count is only used in + check_dbra_loop. */ + struct induction *giv; /* List of all insns that compute a giv + from this reg. */ + int total_benefit; /* Sum of BENEFITs of all those givs */ + rtx initial_value; /* Value of reg at loop start */ + struct iv_class *next; /* Links all class structures together */ + rtx init_insn; /* insn which intializes biv, 0 if none seen. */ + char eliminable; /* 1 if plausible candidate for elimination. */ + char nonneg; /* 1 if we added a REG_NONNEG note for this. */ +}; + +/* Definitions used by the basic induction variable discovery code. */ +enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, + GENERAL_INDUCT }; + +/* Relative gain of eliminating various kinds of operations. */ +#define NO_BENEFIT 0 +#define ADD_BENEFIT 1 +#define SHIFT_BENEFIT 2 +#define MULT_BENEFIT 4 +#define LIBCALL_BENEFIT 15 +/* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to + copy the value of the strength reduced giv to its original register. */ +#define COPY_PENALTY 2 + +/* Indexed by register number, indicates whether or not register is an + induction variable, and if so what type. */ + +static enum iv_mode *induct_var; + +/* Indexed by register number, contains pointer to `struct induction' + if register is a general induction variable. */ + +static struct induction **induct_struct; + +/* Indexed by register number, contains pointer to `struct iv_class' + if register is a basic induction variable. */ + +static struct iv_class **class_struct; + +/*********************************/ + +/* ??? Unfinished optimizations, wilson@ji.Berkeley.EDU */ + +/* strength reduce addresses found in sources (set () (mem ())*/ + +/* There is one more optimization you might be interested in doing: to + allocate pseudo registers for frequently-accessed memory locations. + If the same memory location is referenced each time around, it might + be possible to copy it into a register before and out after. + This is especially useful when the memory location is a variable which + is in a stack slot because somewhere its address is taken. If the + loop doesn't contain a function call and the variable isn't volatile, + it is safe to keep the value in a register for the duration of the + loop. One tricky thing is that the copying of the value back from the + register has to be done on all exits from the loop. You need to check that + all the exits from the loop go to the same place. */ + +/* WARNING: the interaction of biv elimination, and recognizing 'constant' + bivs may cause problems */ + +/* add heuristic so that DEST_ADDR strength reduction does not cause + performance problems */ + +/* don't eliminate things that can be combined with an addressing mode? + find all giv that have same biv and mult_val (now must also have + same add_val), then for each giv, check to see if its only use + dies in a following memory address, generate a new memory address + and check to see if valid, if valid then store modified mem addr, + else if not valid addr mark giv as not done so that it will get its + own iv */ + +/* consec_sets_giv does not calculate replaceable and forces correctly, + forces should be a more general linked list instead of two entries */ + +/* try to optimize branches when it is known that a biv is always positive */ + +/* when replace biv in compare insn, should replace with closest giv so that + an optimized branch can still be recognized by combiner, i.e. VAXen acb */ + +/* should merge final_value calculation in check_dbra_loop with the + new final_biv_value function */ + +/* many of the checks involving uid_luid could be simplified if regscan + was rerun in loop_optimize() whenever a register was added or moved, + also some of the optimizations could be a little less conservative */ + +/* Perform strength reduction and induction variable elimination. */ + +/* Pseudo registers created during this function will be beyond the last + valid index in several tables including n_times_set and regno_last_uid. + This does not cause a problem here, because the added registers cannot be + givs outside of their loop, and hence will never be reconsidered. + But scan_loop must check regnos to make sure they are in bounds. */ + +static void +strength_reduce (scan_start, end, loop_top, insn_count, + loop_start, loop_end, nregs) + rtx scan_start; + rtx end; + rtx loop_top; + int insn_count; + rtx loop_start; + rtx loop_end; + int nregs; +{ + rtx p; + rtx inc_val; + rtx mult_val; + int dest_regno; + int biv_found; + /* This is 1 if current insn could be executed zero times in the loop. */ + int maybe_never = 0; + /* List of all possible basic induction variables. */ + struct iv_class *iv_list = 0; + /* Temporary list pointers for traversing iv_list. */ + struct iv_class *bl, *backbl; + /* Ratio of extra register life span we can justify + for saving an instruction. More if loop doesn't call subroutines + since in that case saving an insn makes more difference + and more registers are available. */ + /* ??? could set this to last value of threshold in move_movables */ + int threshold = loop_has_call ? 17 : 34; + /* Map of pseudo-register replacements. */ + rtx *reg_map; + int call_seen; + + induct_var = (enum iv_mode *) alloca (nregs * sizeof (induct_var[0])); + bzero ((char *)induct_var, nregs * sizeof (induct_var[0])); + induct_struct = (struct induction **) + alloca (nregs * sizeof (struct induction *)); + bzero ((char *)induct_struct, nregs * sizeof (struct induction *)); + class_struct = (struct iv_class **) + alloca (nregs * sizeof (struct iv_class *)); + bzero ((char *)class_struct, nregs * sizeof (struct iv_class *)); + + /* Scan through loop to find all possible bivs. */ + + for (p = NEXT_INSN (loop_start); p != end; p = NEXT_INSN (p)) + { + if (GET_CODE (p) == INSN + && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG) + { + dest_regno = REGNO (SET_DEST (PATTERN (p))); + if (induct_var[dest_regno] != NOT_BASIC_INDUCT + && dest_regno >= FIRST_PSEUDO_REGISTER) + { + if (basic_induction_var (SET_SRC (PATTERN (p)), dest_regno, + &inc_val, &mult_val)) + { + /* It is a possible basic induction variable. + Create and initialize an induction structure for it. */ + + struct induction *v = + (struct induction *) alloca (sizeof (struct induction)); + + v->insn = p; + v->src_regno = dest_regno; + v->dest_regno = dest_regno; + v->mult_val = mult_val; + v->add_val = inc_val; + v->mode = GET_MODE (SET_DEST (PATTERN (p))); + + /* Add this to the reg's iv_class, creating a class + if this is the first incrementation of the reg. */ + + bl = class_struct[dest_regno]; + if (bl) + { + v->family = bl->biv; + bl->biv = v; + bl->biv_count++; + } + else + { + /* Create and initialize new iv_class. */ + + bl = (struct iv_class *) alloca (sizeof (struct iv_class)); + + bl->regno = dest_regno; + bl->biv = v; + v->family = 0; + bl->giv = 0; + bl->biv_count = 1; + bl->giv_count = 0; + + /* Set initial value to the reg itself. */ + bl->initial_value = SET_DEST (PATTERN (p)); + /* We haven't seen the intializing insn yet */ + bl->init_insn = 0; + bl->eliminable = 0; + bl->nonneg = 0; + + /* Add this insn to iv_list. */ + bl->next = iv_list; + iv_list = bl; + + /* Put it in the array of iv_lists. */ + class_struct[dest_regno] = bl; + } + + induct_var[dest_regno] = BASIC_INDUCT; + + if (loop_dump_stream) + { + fprintf (loop_dump_stream, + "Insn %d: possible biv, reg %d,", + INSN_UID (p), dest_regno); + if (GET_CODE (inc_val) == CONST_INT) + fprintf (loop_dump_stream, " const = %d\n", + INTVAL (inc_val)); + else + { + fprintf (loop_dump_stream, " const = "); + print_rtl (loop_dump_stream, inc_val); + fprintf (loop_dump_stream, "\n"); + } + } + } + else + induct_var[dest_regno] = NOT_BASIC_INDUCT; + } + } + } + + /* Scan iv_list to remove all regs that proved not to be bivs. + Make a sanity check against n_times_set. */ + + biv_found = 0; + + for (backbl = bl = iv_list; bl; backbl = bl, bl = bl->next) + { + if (induct_var[bl->regno] != BASIC_INDUCT) + { + /* Not a basic induction variable, remove this iv_class. */ + + if (backbl == bl) + iv_list = bl->next; + else + backbl->next = bl->next; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Reg %d: biv discarded, not induct\n", + bl->regno); + } + else if (n_times_set[bl->regno] != bl->biv_count) + { + /* This happens if register modified by subreg, etc. */ + /* Make sure it is not recognized as a basic induction var: */ + /* remove this iv_class from iv_list. */ + + induct_var[bl->regno] = NOT_BASIC_INDUCT; + + if (backbl == bl) + iv_list = bl->next; + else + backbl->next = bl->next; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Reg %d: biv discarded, count error\n", + bl->regno); + } + else + { + /* This is a valid basic induction variable. */ + + biv_found++; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno); + } + } + + /* Exit if there are no bivs. */ + if (!iv_list) + return; + + /* Find initial value for each biv. */ + /* Search backwards from loop_start, halting at first label + or when all bivs have been seen. */ + + call_seen = 0; + p = loop_start; + while (biv_found) + { + p = PREV_INSN (p); + if (p == 0) + break; + + if (GET_CODE (p) == CALL_INSN) + call_seen = 1; + + if (GET_CODE (p) == INSN + && GET_CODE (PATTERN (p)) == SET) + { + rtx dest = SET_DEST (PATTERN (p)); + + while (GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT + || GET_CODE (dest) == SIGN_EXTRACT + || GET_CODE (dest) == STRICT_LOW_PART) + dest = XEXP (dest, 0); + + if (GET_CODE (dest) == REG) + { + int dest_regno = REGNO (dest); + if (induct_var[dest_regno] == BASIC_INDUCT + && class_struct[dest_regno]->init_insn == 0) + { + /* This is the first modification found for this reg. */ + + rtx src = SET_SRC (PATTERN (p)); + + /* Record the intializing INSN */ + + class_struct[dest_regno]->init_insn = p; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Biv %d initialized at insn %d: ", + dest_regno, INSN_UID (p)); + + /* Save value if it is a constant or register. */ + if (CONSTANT_P (src) + || (GET_CODE (src) == REG + /* Don't try to use a value in a hard reg + across a call which clobbers it. */ + && ! (REGNO (src) < FIRST_PSEUDO_REGISTER + && call_used_regs[REGNO (src)] + && call_seen) + && ! reg_set_between_p (src, p, loop_start))) + { + class_struct[dest_regno]->initial_value = src; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "initial value "); + if (loop_dump_stream) + { + if (GET_CODE (src) == CONST_INT) + fprintf (loop_dump_stream, "%d\n", INTVAL (src)); + else + { + print_rtl (loop_dump_stream, src); + fprintf (loop_dump_stream, "\n"); + } + } + } + else + { + /* Biv initial value is not simple move, + so let it keep intial value of "itself". */ + + if (loop_dump_stream) + fprintf (loop_dump_stream, "complex initial value\n"); + } + + biv_found--; + } + } + } + else if (GET_CODE (p) == CODE_LABEL) + break; + } + + /* Search the loop for general induction variables. */ + + /* A register is a giv if: it is only set once, it is a function of a + biv and a constant (or invariant), and it is not a biv. */ + + p = scan_start; + while (1) + { + p = NEXT_INSN (p); + /* At end of a straight-in loop, we are done. + At end of a loop entered at the bottom, scan the top. */ + if (p == scan_start) + break; + if (p == end) + { + if (loop_top != 0) + p = NEXT_INSN (loop_top); + else + break; + if (p == scan_start) + break; + } + + /* Look for a general induction variable in a register. */ + if (GET_CODE (p) == INSN + && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))]) + { + int src_regno; + rtx add_val; + rtx mult_val; + int benefit; + rtx regnote = 0; + struct induction *forces = 0; + struct induction *forces2 = 0; + + dest_regno = REGNO (SET_DEST (PATTERN (p))); + if (dest_regno < FIRST_PSEUDO_REGISTER) + continue; + + if (/* Normal giv. */ + ((benefit = general_induction_var (SET_SRC (PATTERN (p)), + &src_regno, &add_val, + &mult_val, + &forces, &forces2)) + /* Giv set with call to a library routine. */ + || ((regnote = loop_find_reg_equal (p)) + && + (benefit = general_induction_var (XEXP (regnote, 0), + &src_regno, + &add_val, &mult_val, + &forces, &forces2)))) + /* Don't try to handle any regs made by loop optimization. + We have nothing on them in regno_first_uid, etc. */ + && dest_regno < old_max_reg + /* Don't recognize a BASIC_INDUCT_VAR here. */ + && dest_regno != src_regno + /* This must be the only place where the register is set. */ + && (n_times_set[dest_regno] == 1 + || (benefit = consec_sets_giv (benefit, p, + src_regno, dest_regno, + &add_val, &mult_val)))) + { + int count; + struct induction *v = + (struct induction *) alloca (sizeof (struct induction)); + rtx temp; + + record_giv (v, p, src_regno, dest_regno, mult_val, add_val, benefit, + forces, forces2, DEST_REG, maybe_never, 0, loop_end); + + /* Skip the consecutive insns, if there are any. */ + for (count = v->consec - 1; count >= 0; count--) + { + /* If first insn of libcall sequence, skip to end. */ + /* Do this at start of loop, since INSN is guaranteed to + be an insn here. */ + if (temp = find_reg_note (p, REG_LIBCALL, 0)) + { + /* Eliminating a libcall does more good than + eliminating a single insn to do the same job. */ + benefit += LIBCALL_BENEFIT; + p = XEXP (temp, 0); + } + + do p = NEXT_INSN (p); + while (GET_CODE (p) == NOTE); + } + } + } + +#ifndef DONT_REDUCE_ADDR + /* Look for givs which are memory addresses. */ + /* This resulted in worse code on a VAX 8600. I wonder if it + still does. */ + if (GET_CODE (p) == INSN) + find_mem_givs (PATTERN (p), p, maybe_never, loop_end); +#endif + + /* Past a label or a jump, we get to insns for which we can't count + on whether or how many times they will be executed during each + iteration. Givs found afterwards cannot be marked replaceable. */ + if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) + maybe_never = 1; + } + + /* Try to prove that the loop counter variable (if any) is always + nonnegative; if so, record that fact with a REG_NONNEG note + so that "decrement and branch until zero" insn can be used. */ + check_dbra_loop (loop_end, iv_list, insn_count, loop_start); + + /* Create reg_map to hold substitutions for replaceable giv regs. */ + reg_map = (rtx *) alloca (nregs * sizeof (rtx)); + bzero ((char *)reg_map, nregs * sizeof (rtx)); + + /* Examine each iv class for feasibility of strength reduction/induction + variable elimination. */ + + for (bl = iv_list; bl; bl = bl->next) + { + struct induction *v; + int benefit; + int replaceable; + int all_reduced; + rtx final_value = 0; + + /* Test whether it will be possible to eliminate this biv + provided all givs are reduced. This is possible if either + the reg is not used outside the loop, or we can compute + what its final value will be. + + Don't try if we put a REG_NONNEG note on the endtest for this biv. + ??? That should be only on machines that have dbra insns. */ + + /* Compare against bl->init_insn rather than loop_start. + We aren't concerned with any uses of the biv between + init_insn and loop_start since these won't be affected + by the value of the biv elsewhere in the function, so + long as init_insn doesn't use the biv itself. + March 14, 1989 -- self@bayes.arc.nasa.gov */ + + if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end) + && bl->init_insn + && INSN_UID (bl->init_insn) < max_uid + && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn) + && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), + SET_SRC (PATTERN (bl->init_insn))) + && ! bl->nonneg) + || (final_value = final_biv_value (bl, loop_end))) + check_eliminate_biv (bl, loop_start, end); + else + { + if (loop_dump_stream) + { + fprintf (loop_dump_stream, + "Cannot eliminate biv %d.\n", + bl->regno); + fprintf (loop_dump_stream, + "First use: insn %d, last use: insn %d.\n", + regno_first_uid[bl->regno], + regno_last_uid[bl->regno]); + } + } + + /* This will be true at the end, if all givs which depend on this + biv have been strength reduced. + We can't (currently) eliminate the biv unless this is so. */ + all_reduced = 1; + + /* Check each giv in this class. */ + + for (v = bl->giv; v; v = v->family) + { + struct induction *tv; + + if (v->ignore) + continue; + + benefit = v->benefit; + replaceable = v->replaceable; + + /* Reduce benefit if not replaceable, since we will insert + a move-insn to replace the insn that calculates this giv. */ + if (!replaceable && ! bl->eliminable) + benefit -= COPY_PENALTY; + + /* Decrease the benefit to count the add-insns that we will + insert to increment the reduced reg for the giv. */ + benefit -= ADD_BENEFIT * bl->biv_count; + + /* Find all equivalent givs (that bear same relation to the biv). + Link them via the `same' field and add their benefits together. + They can be replaced with a single register. */ + + for (tv = v->family; tv; tv = tv->family) + { + if (tv->ignore == 0 + && tv->src_regno == v->src_regno + && rtx_equal_p (tv->mult_val, v->mult_val) + && rtx_equal_p (tv->add_val, v->add_val)) + { + benefit += tv->benefit; + if (! tv->replaceable) + benefit -= COPY_PENALTY; + v->lifetime += tv->lifetime; + v->times_used += tv->times_used; + tv->ignore = 1; + + /* Link them together via `same' field. */ + tv->same = v->same; + v->same = tv; + + if (loop_dump_stream) + fprintf (loop_dump_stream, + "giv of insn %d combined with that of %d.\n", + INSN_UID (v->insn), INSN_UID (tv->insn)); + } + } + + /* Decide whether to strength-reduce this giv + or to leave the code unchanged + (recompute it from the biv each time it is used). + This decision can be made independently for each giv. */ + + /* ??? Perhaps attempt to guess whether autoincrement will handle + some of the new add insns; if so, can increase BENEFIT + (undo the subtraction of ADD_BENEFIT that was done above). */ + + /* If an insn is not to be strength reduced, then set its ignore + flag, and clear all_reduced. */ + + /* Is it right to consider times_used? */ + + /* ??? What about the insns that are 'forced' by this one? + Although this insn is not worthwhile to reduce, it may be + worthwhile to reduce the simpler givs used to compute this + complex giv. */ + + /* ??? Hey! If a giv has its forces field set, then that means + it is not computed directly from the biv, it is instead computed + from a simpler giv. If we define UNFORCE_INSNS, then the simpler + giv will be considered for strength reduction, and this giv should + not cause all_reduced to be cleared because it DOESN'T use the + biv!!! If the simpler giv can not be reduced, then that simpler + biv will still cause all_reduced to be cleared. */ + + if (benefit <= 0) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, "giv of insn %d, no benefit\n", + INSN_UID (v->insn)); + v->ignore = 1; + all_reduced = 0; + } + + if (v->lifetime * threshold * benefit < insn_count) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "giv of insn %d not worth while, %d vs %d.\n", + INSN_UID (v->insn), + v->lifetime * threshold * benefit, insn_count); + v->ignore = 1; + all_reduced = 0; + } + + /* Now check that we can increment the reduced giv + without needing a multiply insn. If not, reject it. */ + + if (! v->ignore) + { + int success = 1; + + for (tv = bl->biv; tv; tv = tv->family) + if (tv->mult_val == const1_rtx) + success &= product_cheap_p (tv->add_val, v->mult_val); + + if (! success) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "giv of insn %d: would need a multiply.\n", + INSN_UID (v->insn)); + v->ignore = 1; + all_reduced = 0; + } + } + } + + /* Reduce each giv that we decided to reduce. */ + + for (v = bl->giv; v; v = v->family) + { + struct induction *tv; + if (! v->ignore) + { + rtx new_reg; + + /* Note Iris compiler dies if ?: is used inside gen_reg_rtx. */ + if (v->giv_type == DEST_ADDR) + new_reg = gen_reg_rtx (Pmode); + else + new_reg = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (v->insn)))); + + /* For each place where the biv is incremented, + add an insn to increment the new, reduced reg for the giv. + Insert it before the insn that sets the biv, + so that the biv increment remains last before the endtest, + so that dbra will still be recognized. */ + + for (tv = bl->biv; tv; tv = tv->family) + { + struct induction *iv; + rtx before_insn = tv->insn; + + /* If this increment is between the setting of the giv and + its use, don't increment until after the use. */ + for (iv = v; iv; iv = iv->same) + { + if (INSN_LUID (tv->insn) <= INSN_LUID (iv->insn) + && ((iv->forces + && (INSN_LUID (tv->insn) + >= INSN_LUID (iv->forces->insn)) + || (iv->forces2 + && (INSN_LUID (tv->insn) + >= INSN_LUID (iv->forces2->insn)))))) + { + before_insn = NEXT_INSN (iv->insn); + break; + } + } + + if (tv->mult_val == const1_rtx) + emit_iv_inc (tv->add_val, v->mult_val, + new_reg, before_insn); + else /* tv->mult_val == const0_rtx */ + /* A multiply is acceptable here + since this is presumed to be seldom executed. */ + emit_iv_init_code (tv->add_val, v->mult_val, + v->add_val, new_reg, before_insn); + } + + /* Add code at loop start to initialize giv's reduced reg. */ + + emit_iv_init_code (bl->initial_value, v->mult_val, + v->add_val, new_reg, loop_start); + /* If the initial value uses a register, + then we may have just extended its range of appearance. + Update this conservatively for the sake of outer loops. */ + if (GET_CODE (bl->initial_value) == REG + && (uid_luid[regno_last_uid[REGNO (bl->initial_value)]] + < INSN_LUID (loop_start))) + uid_luid[regno_last_uid[REGNO (bl->initial_value)]] + = INSN_LUID (loop_start); + + /* For each giv register that can be reduced now: + delete old insn that modifies the giv, + if replaceable, substitute reduced reg + wherever the old giv occurs; + else add new move insn "giv_reg = reduced_reg". */ + + for (tv = v; tv; tv = tv->same) + { + /* Record the identity of the reduced reg. */ + tv->new_reg = new_reg; + + if (tv->giv_type == DEST_ADDR) + { + /* Store reduced reg as the address in the memref + where we found this giv. */ + * tv->location = new_reg; + } + else if (tv->replaceable) + { + reg_map[tv->dest_regno] = new_reg; + /* If giv lives after end of loop, + emit insn to copy reduced reg into old reg, + at the end of the loop. + ?? insufficient; used before loop could + mean live after loop, due to surrounding loop. */ + /* Currently a giv used outside + the loop will not be marked replaceable, + so these deficiencies don't really hurt. */ + if (uid_luid[regno_last_uid[tv->dest_regno]] + > uid_luid[INSN_UID (loop_end)]) + { + /* ?? This won't work. We need to do this at + ALL exits. */ + emit_insn_after (gen_rtx (SET, VOIDmode, + SET_DEST (PATTERN (tv->insn)), + new_reg), + loop_end); + abort (); + } + } + else + { + /* Not replaceable; emit an insn to set the + original giv reg from the reduced giv. */ + + int count; + rtx after_insn = tv->insn; + + for (count = tv->consec; count > 0; count--) + after_insn = next_real_insn (after_insn); + + /* Put new insn after, not before, in case + after_insn is the end of a libcall. */ + emit_insn_after (gen_rtx (SET, VOIDmode, + SET_DEST (PATTERN (tv->insn)), + new_reg), + after_insn); + } + + /* Delete the insn that used to set the old giv reg, + unless we modified an address in it. + In any case, delete the other insns used for this one. */ + delete_insn_forces (tv, tv->giv_type != DEST_ADDR); + + if (loop_dump_stream) + fprintf (loop_dump_stream, "giv at %d reduced to reg %d\n", + INSN_UID (tv->insn), REGNO (new_reg)); + } + /* One set of equivalent givs has been strength-reduced. */ + } +#if 0 + else if (v->new_reg == 0) + { + /* This giv wasn't reduced and is not worth reducing. */ + + for (tv = v; tv; tv = tv->same) + if (loop_dump_stream) + fprintf (loop_dump_stream, "giv at %d not reduced\n", + INSN_UID (tv->insn)); + + all_reduced = 0; + } +#endif + } + + /* All the givs in this family have been reduced if they merit it. */ + + /* Try to eliminate the biv, if it is a candidate. + This won't work if ! all_reduced, + since the givs we planned to use might not have been reduced. */ + + if (all_reduced == 1 && bl->eliminable) + { + /* Get the REG rtx for the biv. */ + rtx reg = SET_DEST (PATTERN (bl->biv->insn)); + + for (p = loop_start; p != end; p = NEXT_INSN (p)) + { + enum rtx_code code = GET_CODE (p); + if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) + && reg_mentioned_p (reg, PATTERN (p)) + && SET_DEST (PATTERN (p)) == cc0_rtx) + /* Found a compare instruction using this biv; + rewrite it to use a related giv. */ + { + struct induction *v1; + /* If this is an insn which uses the biv ONLY in the + calculation of a giv which is in the family of this + biv, it's ok becuase it will go away when the giv is + reduced. */ + for (v1 = bl->giv; v1; v1 = v1->family) + if (v1->insn == p) + { + if (v1->giv_type == DEST_REG + || (v1->giv_type == DEST_ADDR + /* I thought the test was backwards, + but then I found the real problem + was in the subroutine. */ + && ! other_reg_use_p (reg, *(v1->location), + PATTERN (p)))) + break; + } + if (!v1) + eliminate_biv (p, bl, loop_start); + } + } + + /* Biv is no longer really needed inside the loop, + so delete all insns that set the biv. */ + + for (v = bl->biv; v; v = v->family) + delete_insn (v->insn); + + /* ?? If we created a new test to bypass the loop entirely, + or otherwise drop straight in, based on this test, then + we might want to rewrite it also. This way some later + pass has more hope of removing the intialization of this + biv entirely. */ + + /* If final_value != 0, then biv may be used after loop end + and we must emit an insn to set it just in case. */ + if (final_value != 0) + emit_insn_after (gen_rtx (SET, VOIDmode, reg, final_value), + loop_end); + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Reg %d: biv eliminated\n", + bl->regno); + } + } + + /* Go through all the instructions in the loop, making all the + register substitutions scheduled in REG_MAP. */ + + for (p = loop_start; p != end; p = NEXT_INSN (p)) + if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN + || GET_CODE (p) == CALL_INSN) + { + rtx tail; + + replace_regs (PATTERN (p), reg_map, nregs); + /* Subsitute registers in the equivalent expression also. */ + for (tail = REG_NOTES (p); tail; tail = XEXP (tail, 1)) + if (REG_NOTE_KIND (tail) == REG_EQUAL + || REG_NOTE_KIND (tail) == REG_EQUIV) + replace_regs (XEXP (tail, 0), reg_map, nregs); + } + + if (loop_dump_stream) + fprintf (loop_dump_stream, "\n"); +} + +/* Nonzero if register REG appears somewhere within IN, other than in + subexpressions EQ to EXPR. This is a modification of reg_mentioned_p. */ + +int +other_reg_use_p (reg, expr, in) + register rtx reg, expr, in; +{ + register char *fmt; + register int i; + register enum rtx_code code; + + if (in == 0 || in == expr) + return 0; + + if (reg == in) + return 1; + + code = GET_CODE (in); + + switch (code) + { + /* Compare registers by number. */ + case REG: + return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg); + + /* These codes have no constituent expressions + and are unique. */ + case CC0: + case PC: + case CONST_INT: + case CONST_DOUBLE: + case SYMBOL_REF: + case CODE_LABEL: + return 0; + } + + fmt = GET_RTX_FORMAT (code); + + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'E') + { + register int j; + for (j = XVECLEN (in, i) - 1; j >= 0; j--) + if (other_reg_use_p (reg, expr, XVECEXP (in, i, j))) + return 1; + } + else if (fmt[i] == 'e' + && other_reg_use_p (reg, expr, XEXP (in, i))) + return 1; + } + return 0; +} + +/* Scan X for memory refs and check each memory address + as a possible giv. INSN is the insn whose pattern X comes from. + MAYBE_NEVER is 1 if the loop might execute INSN zero times. */ + +static void +find_mem_givs (x, insn, maybe_never, loop_end) + rtx x; + rtx insn; + int maybe_never; + rtx loop_end; +{ + register int i, j; + register enum rtx_code code; + register char *fmt; + + if (x == 0) + return; + + code = GET_CODE (x); + switch (code) + { + case REG: + case CONST_INT: + case CONST: + case CONST_DOUBLE: + case SYMBOL_REF: + case LABEL_REF: + case PC: + case CC0: + case ADDR_VEC: + case ADDR_DIFF_VEC: + case USE: + case CLOBBER: + return; + + case MEM: + { + int src_regno; + rtx add_val; + rtx mult_val; + int benefit; + struct induction *forces = 0; + struct induction *forces2 = 0; + + benefit = general_induction_var (XEXP (x, 0), + &src_regno, &add_val, &mult_val, + &forces, &forces2); + if (benefit > 0) + { + /* Found one; record it. */ + struct induction *v = + (struct induction *) oballoc (sizeof (struct induction)); + + record_giv (v, insn, src_regno, 0, mult_val, add_val, benefit, + forces, forces2, DEST_ADDR, maybe_never, &XEXP (x, 0), + loop_end); + } + return; + } + } + + /* Recursively scan the subexpressions for other mem refs. */ + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + if (fmt[i] == 'e') + find_mem_givs (XEXP (x, i), insn, maybe_never, loop_end); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + find_mem_givs (XVECEXP (x, i, j), insn, maybe_never, loop_end); +} + +/* Fill in the data about one giv. + V is the `struct induction' in which we record the giv. (It is + allocated by the caller, with alloca.) + INSN is the insn that sets it. + BENEFIT estimates the savings from deleting this insn. + TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed + into a register or is used as a memory address. + + SRC_REGNO is the biv reg number which the giv is computed from. + DEST_REGNO is the giv's reg number (if the giv is stored in a reg). + MULT_VAL and ADD_VAL are the coefficients used to compute the giv. + FORCES and FORCES2, if nonzero, are other `struct induction's for + other givs which are used to compute this giv indirectly. + LOCATION points to the place where this giv's value appears in INSN. */ + +static void +record_giv (v, insn, src_regno, dest_regno, mult_val, add_val, benefit, + forces, forces2, type, maybe_never, location, loop_end) + struct induction *v; + rtx insn; + int src_regno, dest_regno; + rtx mult_val, add_val; + int benefit; + struct induction *forces, *forces2; + enum g_types type; + int maybe_never; + rtx *location; + rtx loop_end; +{ + struct induction *b; + struct iv_class *bl; + + v->insn = insn; + v->src_regno = src_regno; + v->giv_type = type; + v->dest_regno = dest_regno; + v->mult_val = mult_val; + v->add_val = add_val; + v->benefit = benefit; + v->location = location; + + if (type == DEST_ADDR) + { + v->mode = GET_MODE (*location); + v->consec = 0; + v->lifetime = 1; + v->times_used = 1; + } + else /* type == DEST_REG */ + { + v->mode = GET_MODE (SET_DEST (PATTERN (insn))); + v->consec = n_times_set[dest_regno] - 1; + v->lifetime = (uid_luid[regno_last_uid[dest_regno]] + - uid_luid[regno_first_uid[dest_regno]]); + v->times_used = n_times_used[dest_regno]; + } + + v->same = 0; + v->forces = 0; + v->forces2 = 0; + v->ignore = 0; + v->new_reg = 0; + + /* Mark giv as forced if it is only used to compute another giv. */ + + /* This check is not sufficient as INSN may have been moved giving + it a new uid, so make another check by calculating lifetimes. + This is overconservative but seems to be correct. */ + + if (forces) + { + v->benefit += forces->benefit; + if ((regno_last_uid[forces->dest_regno] == INSN_UID (insn) + || + ((uid_luid[regno_last_uid[forces->dest_regno]] + - uid_luid[regno_first_uid[forces->dest_regno]]) + == (INSN_LUID (insn) - INSN_LUID (forces->insn)))) + && !reg_used_between_p (SET_DEST (PATTERN (forces->insn)), + forces->insn, insn)) + { + v->forces = forces; + forces->ignore = 1; + } + } + + if (forces2) + { + v->benefit += forces2->benefit; + if ((regno_last_uid[forces2->dest_regno] == INSN_UID (insn) + || + ((uid_luid[regno_last_uid[forces2->dest_regno]] + - uid_luid[regno_first_uid[forces2->dest_regno]]) + == (INSN_LUID (insn) - INSN_LUID (forces2->insn)))) + && !reg_used_between_p (SET_DEST (PATTERN (forces2->insn)), + forces2->insn, insn)) + { + if (v->forces) + v->forces2 = forces2; + else + v->forces = forces2; + forces2->ignore = 1; + } + } + + if (type == DEST_REG) + { + induct_var[dest_regno] = GENERAL_INDUCT; + induct_struct[dest_regno] = v; + } + + /* Add the giv to the class of givs computed from one biv. */ + + bl = class_struct[src_regno]; + if (bl) + { + v->family = bl->giv; + bl->giv = v; + /* Don't count DEST_ADDR. This is supposed to count the number of + insns that calculate givs. */ + if (type == DEST_REG) + bl->giv_count++; + bl->total_benefit += benefit; + } + else + /* Fatal error, biv missing for this giv? */ + abort (); + + if (type == DEST_ADDR) + v->replaceable = 1; + else + { + /* The giv can be replaced outright by the reduced register if + - the insn that sets the giv is always executed on any iteration + on which the giv is used at all + (there are two ways to deduce this: + either the insn is executed on every iteration, + or all uses follow that insn in the same basic block), + - the giv is not used before the insn that sets it, + i.e. no definition outside loop reaches into loop + - no assignments to the biv occur during the giv's lifetime. */ + + /* Is this right? Don't we need to make sure the giv is not used + outside the loop. Someday we will know where all the loop exits + are so we can do better, but until then.... + March 18, 1989 -- self@bayes.arc.nasa.gov */ + + if (regno_first_uid[dest_regno] == INSN_UID (insn) + /* Previous line always fails if INSN was moved by loop opt. */ + && uid_luid[regno_last_uid[dest_regno]] < INSN_LUID (loop_end) + && (!maybe_never || last_use_this_basic_block (dest_regno, insn))) + { + v->replaceable = 1; + for (b = bl->biv; b; b = b->family) + { + if ((uid_luid[INSN_UID (b->insn)] >= uid_luid[regno_first_uid[dest_regno]]) + && + (uid_luid[INSN_UID (b->insn)] + <= uid_luid[regno_last_uid[dest_regno]])) + { + v->replaceable = 0; + break; + } + } + } + else + v->replaceable = 0; + } + + if (loop_dump_stream) + { + if (type == DEST_REG) + fprintf (loop_dump_stream, "Insn %d: giv reg %d", + INSN_UID (insn), dest_regno); + else + fprintf (loop_dump_stream, "Insn %d: dest address", + INSN_UID (insn)); + + fprintf (loop_dump_stream, " src reg %d benefit %d", + src_regno, v->benefit); + fprintf (loop_dump_stream, " used %d lifetime %d", + v->times_used, v->lifetime); + + if (v->replaceable) + fprintf (loop_dump_stream, " replaceable"); + + if (GET_CODE (mult_val) == CONST_INT) + fprintf (loop_dump_stream, " mult %d", + INTVAL (mult_val)); + else + { + fprintf (loop_dump_stream, " mult "); + print_rtl (loop_dump_stream, mult_val); + } + + if (GET_CODE (add_val) == CONST_INT) + fprintf (loop_dump_stream, " add %d", + INTVAL (add_val)); + else + { + fprintf (loop_dump_stream, " add "); + print_rtl (loop_dump_stream, add_val); + } + } + + if (loop_dump_stream && v->forces) + fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces->insn)); + if (loop_dump_stream && v->forces2) + fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces2->insn)); + if (loop_dump_stream && v->consec) + fprintf (loop_dump_stream, " consec %d", v->consec); + if (loop_dump_stream) + fprintf (loop_dump_stream, "\n"); +} + +/* Delete the insns forced by the insn described by V. + If THIS_TOO is nonzero, delete that insn itself as well. */ + +static void +delete_insn_forces (v, this_too) + struct induction *v; + int this_too; +{ + rtx x, p; + int count; + rtx insn; + + if (this_too) + { + insn = v->insn; + for (count = v->consec; count >= 0; count--) + { + /* If first insn of libcall sequence, skip to end. */ + /* Do this at start of loop, since p is guaranteed to + be an insn here. */ + if (x = find_reg_note (insn, REG_LIBCALL, 0)) + insn = XEXP (x, 0); + + if (x = find_reg_note (insn, REG_RETVAL, 0)) + { + /* This is a library call; delete all insns backward until get to + first insn in this group. */ + rtx first = XEXP (x, 0); + for (p = insn; p != first; p = PREV_INSN (p)) + delete_insn (p); + /* Delete first insn also. */ + delete_insn (p); + } + else + delete_insn (insn); + + do insn = NEXT_INSN (insn); + while (GET_CODE (insn) == NOTE); + } + } + + if (v->forces) + delete_insn_forces (v->forces, 1); + if (v->forces2) + delete_insn_forces (v->forces2, 1); +} + +/* Check whether an insn is an increment legitimate for a basic induction var. + X is the source of the insn. + DEST_REG is the putative biv, also the destination of the insn. + We accept patterns of these forms: + REG = REG + INVARIANT + REG = INVARIANT + REG + REG = REG - CONSTANT + + If X is suitable, we return 1, + and store the factor multiplying REF in X into *MULT_VAL + and the additive term into *INC_VAL. + Otherwise we return 0. */ + +static int +basic_induction_var (x, dest_regno, inc_val, mult_val) + register rtx x; + int dest_regno; + rtx *inc_val; + rtx *mult_val; +{ + register enum rtx_code code; + rtx arg; + + if (x == 0) + return 0; + code = GET_CODE (x); + switch (code) + { + case PLUS: + if (GET_CODE (XEXP (x, 0)) == REG + && REGNO (XEXP (x, 0)) == dest_regno) + arg = XEXP (x, 1); + else if (GET_CODE (XEXP (x, 1)) == REG + && REGNO (XEXP (x, 1)) == dest_regno) + arg = XEXP (x, 0); + else + return 0; + + if (invariant_p (arg) == 1) + *inc_val = arg; + else + return 0; + + *mult_val = const1_rtx; + return 1; + + case MINUS: + if (GET_CODE (XEXP (x, 0)) == REG + && REGNO (XEXP (x, 0)) == dest_regno + && GET_CODE (XEXP (x, 1)) == CONST_INT) + *inc_val = gen_rtx (CONST_INT, VOIDmode, + - INTVAL (XEXP (x, 1))); + else + return 0; + *mult_val = const1_rtx; + return 1; + + /* Can accept constant setting of biv only when inside inner most loop. + Otherwise, a biv of an inner loop may be incorrectly recognized + as a biv of the outer loop, + causing code to be moved INTO the inner loop. */ + case REG: + if (!invariant_p (x)) + return 0; + case CONST_INT: + case SYMBOL_REF: + case CONST: + if (loops_enclosed == 1) + { + *inc_val = x; + *mult_val = const0_rtx; + return 1; + } + else + return 0; + + default: + return 0; + } +} + +/* A general induction variable (giv) is any quantity that is a linear function + of a basic induction variable, i.e. giv = biv * mult_val + add_val. + The coefficients can be any loop invariant quantity. + A giv need not be computed directly from the biv; + it can be computed by way of other givs. */ + +/* Determine whether X computes a giv. + If it does, return a nonzero value + which is the benefit from eliminating the computation of X; + set *SRC_REGNO to the register number of the biv that it is computed from; + set *ADD_VAL and *MULT_VAL to the coefficients, + such that the value of X is biv * mult + add; + set forces (and forces2) to identify any other givs that are used + solely to compute this one. */ + +/* This routine recognizes four types of patterns that generate givs: + - giv = biv op invariant v = 0, g = 0 + - giv1 = giv2 op invariant v = 0, g = giv2 + where giv1 and giv2 are functions of the same biv + - giv1 = biv op giv2 v = giv2, g = 0 + where giv2 is a function of biv + - giv1 = giv2 op giv3 v = giv3, g = giv2 + where giv2 and giv3 are functions of the save biv */ + +static int +general_induction_var (x, src_regno, add_val, mult_val, forces, forces2) + rtx x; + int *src_regno; + rtx *add_val; + rtx *mult_val; + struct induction **forces; + struct induction **forces2; +{ + register enum rtx_code code; + rtx arg; + struct induction *g = 0; + struct induction *v = 0; + int subexp = 0; + int tem; + + if (x == 0) + return 0; + + code = GET_CODE (x); + switch (code) + { + case NEG: + /* This can generate givs also, but it is not handled. */ + return 0; + + case MULT: + case UMULT: + /* Reject widening multiply in version 1. + That is safer than trying to handle it. */ + { + enum machine_mode m0 = GET_MODE (XEXP (x, 0)); + enum machine_mode m1 = GET_MODE (XEXP (x, 1)); + if (m0 != VOIDmode && m0 != GET_MODE (x)) + return 0; + if (m1 != VOIDmode && m1 != GET_MODE (x)) + return 0; + } + case PLUS: + case MINUS: + /* Result is linear in both operands. */ + /* Determine which operand is the biv, and put the other in ARG. */ + if (GET_CODE (XEXP (x, 0)) == REG + && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) + { + *src_regno = REGNO (XEXP (x, 0)); + arg = XEXP (x, 1); + + } + else if (GET_CODE (XEXP (x, 1)) == REG + && induct_var[REGNO (XEXP (x, 1))] == BASIC_INDUCT) + { + *src_regno = REGNO (XEXP (x, 1)); + arg = XEXP (x, 0); + + } + /* Check for an rtl subexpression that is a giv. Memory address + givs often look like (plus (reg) (mult (biv) (const))). */ + /* Do this before checking for a giv operand, as this function will + fail if this special operand is not recognized. */ +#ifndef DONT_REDUCE_ADDR + else if (tem = general_induction_var (XEXP (x, 1), src_regno, + add_val, mult_val, + forces, forces2) + && code != MINUS) + { + /* Set subexp true so that this can be handled a little + differently from the normal case of g set. */ + /* Note that SRC_REGNO is already set. */ + subexp = TRUE; + g = (struct induction *) alloca (sizeof (struct induction)); + g->mult_val = *mult_val; + g->add_val = *add_val; + /* Fake out the test below. */ + g->replaceable = 1; + /* Count this multiply as a shift, since that's what it + really will do. */ + if (tem == MULT_BENEFIT) + g->benefit = SHIFT_BENEFIT; + else + g->benefit = tem; + arg = XEXP (x, 0); + } + else if (tem = general_induction_var (XEXP (x, 0), src_regno, + add_val, mult_val, + forces, forces2)) + { + /* Set subexp true so that this can be handled a little + differently from the normal case of g set. */ + /* Note that SRC_REGNO is already set. */ + subexp = TRUE; + g = (struct induction *) alloca (sizeof (struct induction)); + g->mult_val = *mult_val; + g->add_val = *add_val; + /* Fake out the test below. */ + g->replaceable = 1; + /* Count this multiply as a shift, since that's what it + really will do. */ + if (tem == MULT_BENEFIT) + g->benefit = SHIFT_BENEFIT; + else + g->benefit = tem; + arg = XEXP (x, 1); + } +#endif + /* Also allow general induction variables. + Could have a mult followed by an add (i.e. an address calculation), + thereby generating two related general induction variables + of which only the second is actually used. */ + /* Do this after checking both args for basic induction variables. */ + else if (GET_CODE (XEXP (x, 0)) == REG + && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) + { + g = induct_struct[REGNO (XEXP (x, 0))]; + *src_regno = g->src_regno; + arg = XEXP (x, 1); + } + else if (GET_CODE (XEXP (x, 1)) == REG + && induct_var[REGNO (XEXP (x, 1))] == GENERAL_INDUCT + && code != MINUS) + { + g = induct_struct[REGNO (XEXP (x, 1))]; + *src_regno = g->src_regno; + arg = XEXP (x, 0); + } + else + return 0; + + /* Overall form of expression looks good. */ + break; + + /* Could handle these also. */ + case DIV: + case UDIV: + /* For a 68020 could handle these? */ + case LSHIFT: + case ASHIFT: + case ASHIFTRT: + case LSHIFTRT: + /* These operations are linear only in first operand. + Check for a biv or giv there; if found, put other operand in ARG. */ + if (GET_CODE (XEXP (x, 0)) == REG + && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) + { + *src_regno = REGNO (XEXP (x, 0)); + arg = XEXP (x, 1); + } + /* Also allow general induction variable. */ + else if (GET_CODE (XEXP (x, 0)) == REG + && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) + { + g = induct_struct[REGNO (XEXP (x, 0))]; + *src_regno = g->src_regno; + arg = XEXP (x, 1); + } + else + return 0; + + /* Overall form of expression looks good. */ + break; + + default: + return 0; + } + + /* ARG is the operand that is NOT a biv or giv. + Test it for superficial validity. */ + + /* This is just a special case of invariant values, + it is not really needed, but it's a shortcut. */ + if (GET_CODE (arg) == CONST_INT) + ; + + /* Depends on previous general induction variable, which has + the same basic induction variable */ + /* This code detects mults that have been generated as shift and add. */ + else if (GET_CODE (arg) == REG + && induct_var[REGNO (arg)] == GENERAL_INDUCT + && induct_struct[REGNO (arg)]->src_regno == *src_regno) + { + v = induct_struct[REGNO (arg)]; + /* Dependence indicated by forces, sort of kludgey. */ + } + + /* Invariant expression, could be a constant-valued register. */ + else if (invariant_p (arg) == 1) + ; + + /* Failure */ + else + return 0; + + /* Until we can do the correct thing, suppress use of nonreplaceable givs + as sources for other givs. */ + if ((g && ! g->replaceable) + || (v && ! v->replaceable)) + return 0; + + /* Now we know looks like a giv; extract the coefficients. + We can still fail if the coefficients are not what we can handle. */ + + /* Only succeed if result mult_val and add_val are only one level of rtl, + for example, (NEG:SI (REG:SI 34)) is not accepted. + This mainly causes problems with the MINUS code. */ + + switch (code) + { + case PLUS: + if (v && g) + { + if (GET_CODE (g->mult_val) == CONST_INT) + { + if (g->mult_val == const0_rtx) + *mult_val = v->mult_val; + else if (GET_CODE (v->mult_val) == CONST_INT) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->mult_val) + + INTVAL (v->mult_val)); + else + return 0; + } + else if (v->mult_val == const0_rtx) + *mult_val = g->mult_val; + else + return 0; + + if (GET_CODE (g->add_val) == CONST_INT) + { + if (g->add_val == const0_rtx) + *add_val = v->add_val; + else if (GET_CODE (v->add_val) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->add_val) + + INTVAL (v->add_val)); + else + return 0; + } + else if (v->add_val == const0_rtx) + *add_val = g->add_val; + else + return 0; + + if (subexp) + { + /* g deleted when return, can't return pointer to it */ + if (*forces2 == 0) + *forces2 = v; + return ADD_BENEFIT + g->benefit; + } + else + { + *forces = g; + *forces2 = v; + return ADD_BENEFIT; + } + } + else if (v) + { + if (GET_CODE (v->mult_val) == CONST_INT) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (v->mult_val) + 1); + else + return 0; + *add_val = v->add_val; + *forces = v; + return ADD_BENEFIT; + } + else if (g) + { + *mult_val = g->mult_val; + if (GET_CODE (g->add_val) == CONST_INT + && nonmemory_operand (arg, GET_MODE (arg))) + *add_val = plus_constant (arg, INTVAL (g->add_val)); + else if (GET_CODE (arg) == CONST_INT + && nonmemory_operand (g->add_val, GET_MODE (g->add_val))) + *add_val = plus_constant (g->add_val, INTVAL (arg)); + else + /* Could succeed if arg == 0, but that will never occur. */ + return 0; + + if (subexp) + /* g deleted when return, can't return pointer to it */ + return ADD_BENEFIT + g->benefit; + else + { + *forces = g; + return ADD_BENEFIT; + } + } + else + { + *mult_val = const1_rtx; + *add_val = arg; + return ADD_BENEFIT; + } + + /* Takes a lot of code and will rarely succeed. */ + case MINUS: + if (v && g) + { + /* G is the first argument of MINUS. */ + + if (GET_CODE (g->mult_val) == CONST_INT) + { + if (g->mult_val == const0_rtx) +#if 0 /* Should not have to fail here */ + *mult_val = gen_rtx (NEG, SImode, v->mult_val); +#endif + return 0; + else if (GET_CODE (v->mult_val) == CONST_INT) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->mult_val) + - INTVAL (v->mult_val)); + else + return 0; + } + else if (v->mult_val == const0_rtx) + *mult_val = g->mult_val; + else + return 0; + + if (GET_CODE (g->add_val) == CONST_INT) + { + if (g->add_val == const0_rtx) +#if 0 /* should not have to fail here */ + *add_val = v->add_val; +#endif + return 0; + else if (GET_CODE (v->add_val) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->add_val) + - INTVAL (v->add_val)); + else + return 0; + } + else if (v->add_val == const0_rtx) + *add_val = g->add_val; + else + return 0; + + if (subexp) + { + /* G deleted when return, can't return pointer to it */ + if (*forces2 == 0) + *forces2 = v; + return ADD_BENEFIT + g->benefit; + } + else + { + *forces = g; + *forces2 = v; + return ADD_BENEFIT; + } + } + else if (v) + { + if (GET_CODE (v->mult_val) != CONST_INT) + return 0; + if (arg == XEXP (x, 0)) /* giv1 = giv2 - biv */ + { + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (v->mult_val) - 1); + *add_val = v->add_val; + } + else /* giv1 = biv - giv2 */ + { + *mult_val = gen_rtx (CONST_INT, VOIDmode, + 1 - INTVAL (v->mult_val)); + if (GET_CODE (v->add_val) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + - INTVAL (v->add_val)); + else + return 0; + } + *forces = v; + return ADD_BENEFIT; + } + else if (g) + { + if (arg == XEXP (x, 1)) + *mult_val = g->mult_val; + else + { + if (GET_CODE (g->mult_val) == CONST_INT) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + - INTVAL (g->mult_val)); + else + return 0; + } + if (GET_CODE (g->add_val) == CONST_INT) + { + if (g->add_val == const0_rtx) + { + if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ + { + /* Fail unless arg is a constant. */ + if (GET_CODE (arg) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + -INTVAL (arg)); + else + return 0; + } + else /* giv1 = arg - giv2 */ + *add_val = arg; + } + else if (GET_CODE (arg) == CONST_INT) + { + if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->add_val) + - INTVAL (arg)); + else /* giv1 = arg - giv2 */ + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (arg), + - INTVAL (g->add_val)); + } + else + return 0; + } + else + /* Could succeed if arg == 0, but that will never occur. */ + return 0; + + if (subexp) + /* G deleted when return, can't return pointer to it. */ + return ADD_BENEFIT + g->benefit; + else + { + *forces = g; + return ADD_BENEFIT; + } + } + else if (GET_CODE (arg) == CONST_INT) + { + if (arg == XEXP (x, 1)) + { + *add_val = gen_rtx (CONST_INT, VOIDmode, - INTVAL (arg)); + *mult_val = const1_rtx; + } + else + { + *add_val = arg; + *mult_val = gen_rtx (CONST_INT, VOIDmode, -1); + } + return ADD_BENEFIT; + } + else + return 0; + + /* UMULT can be handled like MULT since C ignores overflows. */ + case MULT: + case UMULT: + if (v && g) + { + /* Quadratic term, just fail. */ + return 0; + } + else if (v) + { + /* Quadratic term, just fail. */ + return 0; + } + else if (g) + { + /* Takes a lot of code and will rarely succeed. */ + /* dest = m * arg * b + a * arg */ + if (GET_CODE (g->mult_val) == CONST_INT) + { + if (g->mult_val == const0_rtx) + *mult_val = const0_rtx; + else if (g->mult_val == const1_rtx) + *mult_val = arg; + else if (GET_CODE (arg) == CONST_INT) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->mult_val) * INTVAL (arg)); + else + return 0; + } + else + /* Could suceed if arg == 1 or 0, but this will never occur. */ + return 0; + + if (GET_CODE (g->add_val) == CONST_INT) + { + if (g->add_val == const0_rtx) + *add_val = const0_rtx; + else if (g->add_val == const1_rtx) + *add_val = arg; + else if (GET_CODE (arg) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->add_val) * INTVAL (arg)); + else + return 0; + } + else + /* Could suceed if arg == 1 or 0, but this will never occur. */ + return 0; + + if (subexp) + /* G deleted when return, can't return pointer to it. */ + return MULT_BENEFIT + g->benefit; + else + { + *forces = g; + return MULT_BENEFIT; + } + } + else + { + *mult_val = arg; + *add_val = const0_rtx; + return MULT_BENEFIT; + } + + /* These are not worth the trouble. */ + case DIV: + case UDIV: + return 0; + + /* Handle these, but only for left shift. */ + case LSHIFT: + case ASHIFT: + if (v && g) + { + /* Quadratic term, just fail. */ + return 0; + } + else if (v) + { + /* Quadratic term, just fail. */ + return 0; + } + else if (g) + { + /* Takes a lot of code and will rarely succeed. */ + /* dest = ((m * b) << arg) + (a << arg) */ + if (GET_CODE (g->mult_val) == CONST_INT) + { + if (g->mult_val == const0_rtx) + *mult_val = const0_rtx; + else if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) + *mult_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->mult_val) + * (1 << INTVAL (arg))); + else + return 0; + } + else + /* Could suceed if arg == 0, but this will never occur. */ + return 0; + + if (GET_CODE (g->add_val) == CONST_INT) + { + if (g->add_val == const0_rtx) + *add_val = const0_rtx; + else if (GET_CODE (arg) == CONST_INT) + *add_val = gen_rtx (CONST_INT, VOIDmode, + INTVAL (g->add_val) + * (1 << INTVAL (arg))); + else + return 0; + } + else + /* Could suceed if arg == 0, but this will never occur. */ + return 0; + + if (subexp) + /* G deleted when return, can't return pointer to it. */ + return SHIFT_BENEFIT + g->benefit; + else + { + *forces = g; + return SHIFT_BENEFIT; + } + } + + if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) + *mult_val = gen_rtx (CONST_INT, VOIDmode, 1 << INTVAL (arg)); + else + return 0; + *add_val = const0_rtx; + return SHIFT_BENEFIT; + + /* These are not worth the trouble. */ + case ASHIFTRT: + case LSHIFTRT: + return 0; + + /* should never reach here */ + default: + abort (); + return 0; + } +} + +/* Help detect a giv that is calculated by several consecutive insns; + for example, + giv = biv * M + giv = giv + A + The caller has already identified the first insn P as having a giv as dest; + we check that all other insns that set the same register follow + immediately after P, that they alter nothing else, + and that the result of the last is still a giv. + + The value is 0 if the reg set in P is not really a giv. + Otherwise, the value is the amount gained by eliminating + all the consecutive insns that compute the value. + + FIRST_BENEFIT is the amount gained by eliminating the first insn, P. + SRC_REGNO is the regno of the biv; DEST_REGNO is that of the giv. + + The coefficients of the ultimate giv value are stored in + *MULT_VAL and *ADD_VAL. */ + +static int +consec_sets_giv (first_benefit, p, src_regno, dest_regno, + add_val, mult_val) + int first_benefit; + rtx p; + int src_regno; + int dest_regno; + rtx *add_val; + rtx *mult_val; +{ + int count; + int benefit = first_benefit; + enum rtx_code code; + struct induction *forces, *forces2; + rtx temp; + int tem; + + /* Initialize info used by general_induction_var. */ + struct induction *v = + (struct induction *) oballoc (sizeof (struct induction)); + v->src_regno = src_regno; + v->mult_val = *mult_val; + v->add_val = *add_val; + + induct_var[dest_regno] = GENERAL_INDUCT; + induct_struct[dest_regno] = v; + + count = n_times_set[dest_regno] - 1; + + while (count > 0) + { + p = NEXT_INSN (p); + code = GET_CODE (p); + + /* If libcall, skip to end of call sequence. */ + if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) + p = XEXP (temp, 0); + + if (code == INSN && GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && REGNO (SET_DEST (PATTERN (p))) == dest_regno + && ((tem = general_induction_var (SET_SRC (PATTERN (p)), &src_regno, + add_val, mult_val, + &forces, &forces2)) + /* Giv created by call to library routine. */ + || ((temp = loop_find_reg_equal (p)) + && (tem = general_induction_var (XEXP (temp, 0), &src_regno, + add_val, mult_val, + &forces, &forces2)))) + && src_regno == v->src_regno) + { + count--; + benefit += tem; + v->mult_val = *mult_val; + v->add_val = *add_val; + } + else if (code != NOTE) + { + induct_var[dest_regno] = UNKNOWN_INDUCT; + return 0; + } + } + + return benefit; +} + +/* Generate a SEQUENCE to multiply OP0 and OP1 with result in TARGET. + Use expand_mult to "optimally" do the multiply. + This also works for machines that do not have multiply insns. + If one of the operands is a constant, it must be the second. */ + +static rtx +gen_iv_mult (mode, op0, op1, target) + enum machine_mode mode; + register rtx op0, op1, target; +{ + extern rtx gen_sequence (); + extern rtx start_sequence (); + rtx saved, result, temp; + + saved = start_sequence (); + + /* ??? It is very unmodular to use expand_mult here! + This should be redesigned. */ + + /* UNSIGNEDP arg can be zero since operands/target always same width. */ + temp = expand_mult (mode, op0, op1, target, 0); + + /* Move to target register, if expand_mult did not put it there. */ + if (target != 0 && temp != target) + emit_move_insn (target, temp); + + result = gen_sequence (); + end_sequence (saved); + + return result; +} + +/* Emit code to initialize an induction variable created by strength + reduction. + More precisely, emit code before INSERT_BEFORE + to set REG = B * M + A. */ + +static void +emit_iv_init_code (b, m, a, reg, insert_before) + rtx b; /* initial value of basic induction variable */ + rtx m; /* multiplicative constant */ + rtx a; /* additive constant */ + rtx reg; /* destination register */ + rtx insert_before; +{ + rtx seq; + rtx result; + + /* Prevent unexpected sharing of these rtx. */ + a = copy_rtx (a); + b = copy_rtx (b); + + start_sequence (); + result = expand_mult_add (b, m, a, GET_MODE (reg), 0); + if (reg != result) + emit_move_insn (reg, result); + seq = gen_sequence (); + end_sequence (); + + emit_insn_before (seq, insert_before); +} + +/* Emit code to increment the induction variable inside the loop. + Try to emit optimal code for the expression + REG = REG + BIV_ADD * GIV_MULT. */ + +static void +emit_iv_inc (biv_add, giv_mult, reg, insn) + rtx biv_add; /* increment value for biv */ + rtx giv_mult; /* multiply value of giv */ + rtx reg; /* create insn to set this reg */ + rtx insn; /* where to insert the new insn */ +{ + emit_iv_init_code (biv_add, giv_mult, reg, reg, insn); +} + +/* Test whethen BIV_ADD * GIV_MULT can be computed without + an actual multiply insn. Value is 1 if so. */ + +static int +product_cheap_p (biv_add, giv_mult) + rtx biv_add; + rtx giv_mult; +{ + /* Indicates which of MULT/ADD are constants. */ + int status = 0; + int const_val; + rtx tmp; + + if (GET_CODE (biv_add) == CONST_INT) + status |= 0x1; + if (GET_CODE (giv_mult) == CONST_INT) + status |= 0x2; + + switch (status) + { + case 0: + /* Neither is constant: would need a multiply insn, so fail. */ + return 0; + + case 1: + /* BIV_ADD value is constant */ + /* Equivalent to state 2, just switch values of BIV_ADD and GIV_MULT + and fall through. */ + tmp = biv_add; + biv_add = giv_mult; + giv_mult = tmp; + + case 2: + /* GIV_MULT value is constant. + If it is 1, 0 or -1 then we win. */ + const_val = INTVAL (giv_mult); + if (const_val < -1 || const_val > 1) + { + tmp = gen_iv_mult (GET_MODE (biv_add), biv_add, giv_mult, 0); + /* Don't emit a multiply insn, just fail instead. */ + if ((GET_CODE (tmp) == SET && GET_CODE (SET_SRC (tmp)) == MULT) + /* Also fail if library call (which generates more + then two insn) is needed. */ + || (GET_CODE (tmp) == SEQUENCE && XVECLEN (tmp, 0) > 2)) + return 0; + } + return 1; + + case 3: + /* Both BIV_ADD and GIV_MULT are constant; + can compute the product at compile time. */ + return 1; + + default: + abort (); + } +} + + +/* Check to see if loop can be terminated by a "decrement and branch until + zero" instruction. If so, add a REG_NONNEG note to the branch insn if so. + Also try reversing an increment loop to a decrement loop + to see if the optimization can be performed. + Value is nonzero if optimization was performed. */ + +static int +check_dbra_loop (loop_end, iv_list, insn_count, loop_start) + rtx loop_end; + struct iv_class *iv_list; + int insn_count; + rtx loop_start; +{ + struct iv_class *bl; + rtx reg; + rtx jump_label; + rtx final_value; + rtx start_value; + enum rtx_code branch_code; + rtx new_add_val; + rtx tested_before_loop = 0; + rtx p; + + /* See if the loop is contained in `if (X >= 0)' for some reg X. + If so, then we know X is initially nonnegative even though + we don't know its initial value. + Record X in TESTED_BEFORE_LOOP. */ + + for (p = loop_start; p != 0; p = PREV_INSN (p)) + if (GET_CODE (p) != NOTE) + break; + + /* See if a conditional branch preceeds the loop. + There may be no other insns or labels between it and + the beginning of the loop. */ + if (p != 0 && GET_CODE (p) == JUMP_INSN && condjump_p (p) + && SET_SRC (PATTERN (p)) != pc_rtx + && ((GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == LT + && XEXP (SET_SRC (PATTERN (p)), 2) == pc_rtx) + || + (GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == GE + && XEXP (SET_SRC (PATTERN (p)), 1) == pc_rtx)) + && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)) + { + /* Before the branch should be a test or compare. + See if we are comparing something against zero. */ + p = PREV_INSN (p); + if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET + && SET_DEST (PATTERN (p)) == cc0_rtx) + { + if (GET_CODE (SET_SRC (PATTERN (p))) == REG) + tested_before_loop = SET_SRC (PATTERN (p)); + else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE + && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == REG + && XEXP (SET_SRC (PATTERN (p)), 1) == const0_rtx) + tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 0); + else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE + && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 1)) == REG + && XEXP (SET_SRC (PATTERN (p)), 0) == const0_rtx) + tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 1); + } + } + + /* If last insn is a conditional branch, and the insn before tests a register + value, then try to optimize it. */ + + if (GET_CODE (PREV_INSN (loop_end)) == JUMP_INSN + && GET_CODE (PATTERN (PREV_INSN (loop_end))) == SET + && GET_CODE (SET_SRC (PATTERN (PREV_INSN (loop_end)))) == IF_THEN_ELSE + && GET_CODE (PREV_INSN (PREV_INSN (loop_end))) == INSN + && GET_CODE (PATTERN (PREV_INSN (PREV_INSN (loop_end)))) == SET + && (GET_CODE (SET_DEST (PATTERN (PREV_INSN (PREV_INSN (loop_end))))) == + CC0)) + { + /* Check all of the bivs to see if the compare uses one of them. */ + + for (bl = iv_list; bl; bl = bl->next) + { + if (reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), + PREV_INSN (PREV_INSN (loop_end)))) + break; + } + + /* If biv set more than once, then give up. + We can't guarantee that it will be zero on the last iteration. + Also give up if the biv is used between its update and the test + insn. */ + if (bl && bl->biv_count == 1 + && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn, + PREV_INSN (PREV_INSN (loop_end)))) + { + /* Look for the case where the basic induction variable is always + nonnegative, and equals zero on the last iteration. + In this case, add a reg_note REG_NONNEG, which allows the + m68k DBRA instruction to be used. */ + + /* the decrement case */ + + if (GET_CODE (bl->biv->add_val) == CONST_INT + && INTVAL (bl->biv->add_val) < 0) + { + /* Initial value must be greater than 0, + init_val % -dec_value == 0 to ensure that it equals zero on + the last iteration */ + + if (GET_CODE (bl->initial_value) == CONST_INT + && INTVAL (bl->initial_value) > 0 + && (INTVAL (bl->initial_value) % + (-INTVAL (bl->biv->add_val))) == 0) + { + /* register always nonnegative, add REG_NOTE to branch */ + REG_NOTES (PREV_INSN (loop_end)) + = gen_rtx (EXPR_LIST, REG_NONNEG, 0, + REG_NOTES (PREV_INSN (loop_end))); + bl->nonneg = 1; + + return 1; + } + + /* If the decrement is 1 and the value was tested as >= 0 before + the loop, then we can safely optimize. */ + if (SET_DEST (PATTERN (bl->biv->insn)) == tested_before_loop + && INTVAL (bl->biv->add_val) == -1) + { + REG_NOTES (PREV_INSN (loop_end)) + = gen_rtx (EXPR_LIST, REG_NONNEG, 0, + REG_NOTES (PREV_INSN (loop_end))); + bl->nonneg = 1; + + return 1; + } + } + else if (num_mem_sets <= 1) + { + /* Try to change inc to dec, so can apply above optimization. */ + /* Can do this if: + all registers modified are induction variables or invariant, + all memory references have non-overlapping addresses + (obviously true if only one write) + allow 2 insns for the compare/jump at the end of the loop. */ + int num_nonfixed_reads = 0; + rtx p; + /* 1 if the iteration var is used only to count iterations. */ + int no_use_except_counting = 0; + + for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) + if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN + || GET_CODE (p) == JUMP_INSN) + num_nonfixed_reads += count_nonfixed_reads (PATTERN (p)); + + if (bl->giv_count == 0) + { + rtx bivreg = regno_reg_rtx[bl->regno]; + + /* If there are no givs for this biv, + see if perhaps there are no uses except to count. */ + no_use_except_counting = 1; + for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) + if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN + || GET_CODE (p) == JUMP_INSN) + { + if (GET_CODE (PATTERN (p)) == SET + && GET_CODE (SET_DEST (PATTERN (p))) == REG + && REGNO (SET_DEST (PATTERN (p))) == bl->regno) + /* An insn that sets the biv is okay. */ + ; + else if (p == PREV_INSN (PREV_INSN (loop_end)) + || p == PREV_INSN (loop_end)) + /* Don't bother about the end test. */ + ; + else if (reg_mentioned_p (bivreg, PATTERN (p))) + /* Any other use of the biv is no good. */ + { + no_use_except_counting = 0; + break; + } + } + } + + /* This code only acts for innermost loops. Also it simplifies + the memory address check by only reversing loops with + zero or one memory access. + Two memory accesses could involve parts of the same array, + and that can't be reversed. */ + + if (num_nonfixed_reads <= 1 + && !loop_has_call + && (no_use_except_counting + || (bl->giv_count + bl->biv_count + num_mem_sets + + num_movables + 2 == insn_count))) + { + rtx src_two_before_end; + int constant; + int win; + + /* Loop can be reversed. */ + if (loop_dump_stream) + fprintf (loop_dump_stream, "Can reverse loop\n"); + + /* Now check other conditions: + initial_value must be zero, + final_value % add_val == 0, so that when reversed, the + biv will be zero on the last iteration. */ + + /* Calculating the final value non trivial. + If branch is (LT (CC0) (CONST 0), + then value in compare is final value. + If branch is (LE (CC0) (CONST 0), + then value in compare is final_value - add_val */ + + branch_code + = GET_CODE (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0)); + src_two_before_end + = SET_SRC (PATTERN (PREV_INSN (PREV_INSN (loop_end)))); + + win = 1; + if (GET_CODE (src_two_before_end) == REG) + constant = 0; + else if (GET_CODE (src_two_before_end) == COMPARE + && GET_CODE (XEXP (src_two_before_end, 1)) == CONST_INT) + constant = INTVAL (XEXP (src_two_before_end, 1)); + else + win = 0; + + if (win && bl->initial_value == const0_rtx + && (branch_code == LT || branch_code == LE) + && XEXP (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0), 1) == const0_rtx + && (constant % INTVAL (bl->biv->add_val)) == 0) + { + /* Register will always be nonnegative, with value + 0 on last iteration if loop reversed */ + + /* Save some info needed to produce the new insns. */ + reg = SET_DEST (PATTERN (bl->biv->insn)); + jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1); + new_add_val = gen_rtx (CONST_INT, VOIDmode, + - INTVAL (bl->biv->add_val)); + + + if (branch_code == LT) + { + final_value + = gen_rtx (CONST_INT, VOIDmode, constant); + start_value + = gen_rtx (CONST_INT, VOIDmode, + (constant - INTVAL (bl->biv->add_val))); + } + else /* branch_code == LE */ + { + start_value + = gen_rtx (CONST_INT, VOIDmode, constant); + final_value + = gen_rtx (CONST_INT, VOIDmode, + (constant + INTVAL (bl->biv->add_val))); + } + + /* Initialize biv to start_value before loop start. + The old initializing insn will be deleted as a + dead store by flow.c. */ + emit_insn_before (gen_rtx (SET, VOIDmode, reg, + start_value), + loop_start); + + /* Add insn to decrement register, and delete insn + that incremented the register. */ + emit_insn_before (gen_rtx (SET, VOIDmode, reg, + gen_rtx (PLUS, GET_MODE (reg), reg, + new_add_val)), + bl->biv->insn); + /* Update biv info to reflect its new status. */ + bl->biv->insn = PREV_INSN (bl->biv->insn); + delete_insn (NEXT_INSN (bl->biv->insn)); + + /* Inc LABEL_NUSES so that delete_insn will + not delete the label. */ + LABEL_NUSES (XEXP (jump_label, 0)) ++; + + if (regno_last_uid[bl->regno] != INSN_UID (PREV_INSN (loop_end))) + emit_insn_after (gen_rtx (SET, VOIDmode, reg, + final_value), + loop_end); + + /* Delete compare/branch at end of loop. */ + delete_insn (PREV_INSN (loop_end)); + delete_insn (PREV_INSN (loop_end)); + + /* Add new compare/branch insn at end of loop. */ + emit_insn_before (gen_rtx (SET, VOIDmode, cc0_rtx, reg), + loop_end); + emit_jump_insn_before (gen_rtx (SET, VOIDmode, pc_rtx, + gen_rtx (IF_THEN_ELSE, VOIDmode, + gen_rtx (GE, VOIDmode, cc0_rtx, + const0_rtx), + jump_label, + pc_rtx)), + loop_end); + + JUMP_LABEL (PREV_INSN (loop_end)) = XEXP (jump_label, 0); + /* Increment of LABEL_NUSES done above. */ + + /* Register is now always nonnegative, + so add REG_NONNEG note to the branch. */ + REG_NOTES (PREV_INSN (loop_end)) + = gen_rtx (EXPR_LIST, REG_NONNEG, 0, + REG_NOTES (PREV_INSN (loop_end))); + bl->nonneg = 1; + + /* Update rest of biv info. */ + bl->initial_value = start_value; + bl->biv->add_val = new_add_val; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Reversed loop and added reg_nonneg\n"); + + return 1; + } + } + } + } + } + return 0; +} + +/* Verify whether the biv BL appears to be eliminable, + based on the insns in the loop that refer to it. + LOOP_START is the first insn of the loop, and END is the end insn. */ + +static void +check_eliminate_biv (bl, loop_start, end) + struct iv_class *bl; + rtx loop_start; + rtx end; +{ + /* Get the REG rtx for the biv. */ + rtx reg = SET_DEST (PATTERN (bl->biv->insn)); + rtx p; + struct induction *v; + + bl->eliminable = 0; + + for (p = loop_start; p != end; p = NEXT_INSN (p)) + { + enum rtx_code code = GET_CODE (p); + if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) + && reg_mentioned_p (reg, PATTERN (p))) + { + /* This insn uses the biv. If we can't understand it, + then we can't eliminate the biv. */ + if (GET_CODE (PATTERN (p)) != SET) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Cannot eliminate biv %d: cannot understand insn %d.\n", + bl->regno, INSN_UID (p)); + break; + } + + /* The insns that increment the biv are no problem. */ + if (SET_DEST (PATTERN (p)) == reg) + continue; + + /* If this is an insn which uses the biv ONLY in the + calculation of a giv which is in the family of this + biv, it's ok becuase it will go away when the giv is + reduced. March 14, 1989 -- self@bayes.arc.nasa.gov */ + for (v = bl->giv; v; v = v->family) + if (v->insn == p) + { + if (v->giv_type == DEST_REG + || (v->giv_type == DEST_ADDR + && ! other_reg_use_p (reg, *(v->location), + PATTERN (p)))) + break; + } + if (v) + continue; + + /* If can rewrite this insn not to use the biv, it's ok. */ + if (can_eliminate_biv_p (p, bl)) + continue; + + /* Biv is used in a way we cannot eliminate. */ + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Cannot eliminate biv %d: biv used in insn %d.\n", + bl->regno, INSN_UID (p)); + break; + } + } + + if (p == end) + { + bl->eliminable = 1; + if (loop_dump_stream) + fprintf (loop_dump_stream, "Can eliminate biv %d.\n", + bl->regno); + } +} + +/* Return 1 if INSN, a compare insn which tests the biv described by BL, + can be rewritten to use instead some reduced giv related to that biv. + Does not change the rtl. + + We make the assumption that all the givs depending on this biv + will be reduced, since only in that case will an attempt to eliminate + the biv actually be made. + + The following function is very parallel to this one. */ + +static int +can_eliminate_biv_p (insn, bl) + rtx insn; + struct iv_class *bl; +{ + rtx src; + enum rtx_code code; + struct induction *v, *tv; + rtx arg; + int arg_operand; + /* Mode of this biv. */ + enum machine_mode mode = bl->biv->mode; + + if (SET_DEST (PATTERN (insn)) != cc0_rtx) + return 0; + + src = SET_SRC (PATTERN (insn)); + code = GET_CODE (src); + + switch (code) + { + /* a test insn */ + case REG: + /* Can replace with any giv that has (MULT_VAL != 0) and (ADD_VAL == 0) + Require a constant integer for MULT_VAL, so we know it's nonzero. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx + && v->add_val == const0_rtx + && ! v->ignore + && v->mode == mode) + return 1; + + /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0) + where ADD_VAL is a constant or a register; + can replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). + Require a constant integer for MULT_VAL, so we know it's nonzero. */ + + if (next_insn_tests_no_inequality (insn)) + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx + && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT) + && ! v->ignore + && v->mode == mode) + return 1; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n", + bl->regno, INSN_UID (insn)); + + return 0; + + /* a compare insn */ + case COMPARE: + /* Figure out which operand is the biv. */ + if ((GET_CODE (XEXP (src, 0)) == REG) + && (REGNO (XEXP (src, 0)) == bl->regno)) + { + arg = XEXP (src, 1); + arg_operand = 1; + } + else if ((GET_CODE (XEXP (src, 1)) == REG) + && (REGNO (XEXP (src, 1)) == bl->regno)) + { + arg = XEXP (src, 0); + arg_operand = 0; + } + else + return 0; + + if (GET_CODE (arg) == CONST_INT) + { + /* Can replace with any giv that has constant coefficients. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT + && GET_CODE (v->add_val) == CONST_INT + && ! v->ignore + && v->mode == mode) + { + /* Make sure there's no overflow in the range for the giv. */ + if (INTVAL (v->mult_val) == 0 + || + (INTVAL (arg) * INTVAL (v->mult_val) / INTVAL (v->mult_val) + != INTVAL (arg)) + || + ((0 < (INTVAL (arg) * INTVAL (v->mult_val) + + INTVAL (v->add_val))) + != (0 < INTVAL (arg)))) + return 0; + + return 1; + } + + if (next_insn_tests_no_inequality (insn)) + { + /* Look for giv with constant mult_val and nonconst add_val, + since we can insert add insn before loop + to calculate new compare value. */ + + /* This is not safe if the end-test is not == or !=, + since we can't tell whether the giv will overflow. */ + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT + && ! v->ignore + && v->mode == mode) + return 1; + } + } + else if ((GET_CODE (arg) == REG || GET_CODE (arg) == MEM) + && next_insn_tests_no_inequality (insn)) + { + /* Comparing against invariant register or memref can be handled. */ + + if (invariant_p (arg)) + { + /* Look for giv with constant mult_val and nonconst add_val. + Insert add-insn before loop to compute new compare value. */ + + for (v = bl->giv; v; v = v->family) + if ((GET_CODE (v->mult_val) == CONST_INT) + && ! v->ignore + && v->mode == mode) + return 1; + } + + /* Otherwise, only comparing against a biv can be handled. */ + if (GET_CODE (arg) != REG + || induct_var[REGNO (arg)] != BASIC_INDUCT) + return 0; + + /* Look for a giv for each biv that have identical + values for mult_val and add_val. */ + for (v = bl->giv; v; v = v->family) + if (v->mode == mode + && ! v->ignore) + { + for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) + if ((tv->new_reg != 0) + && rtx_equal_p (tv->mult_val, v->mult_val) + && rtx_equal_p (tv->mult_val, v->mult_val) + && ! tv->ignore + && tv->mode == mode) + return 1; + } + } + return 0; + + default: + return 0; + } +} + +/* Rewrite a compare insn INSN which uses the biv described by BL + so that it doesn't use that biv any more. + Instead it will use some reduced giv related to that biv. + + The preceding function is very parallel to this one. */ + +static void +eliminate_biv (insn, bl, loop_start) + rtx insn; + struct iv_class *bl; + rtx loop_start; +{ + rtx src = SET_SRC (PATTERN (insn)); + enum rtx_code code = GET_CODE (src); + struct induction *v, *tv; + rtx arg, temp; + int arg_operand; + /* Mode of this biv. */ + enum machine_mode mode = bl->biv->mode; + + switch (code) + { + /* a test insn */ + case REG: + /* Can replace with any giv that was reduced and + that has (MULT_VAL != 0) and (ADD_VAL == 0). + Require a constant integer for MULT_VAL, so we know it's nonzero. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx + && v->add_val == const0_rtx + && v->new_reg != 0 + && v->mode == mode) + break; + if (v) + { + /* We can test the sign of that giv's reduced reg. */ + SET_SRC (PATTERN (insn)) = v->new_reg; + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + SET_SRC (PATTERN (insn)) + = gen_rtx (COMPARE, GET_MODE (v->new_reg), + const0_rtx, v->new_reg); + return; + } + + /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0) + where ADD_VAL is a constant or a register; + replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). + Require a constant integer for MULT_VAL, so we know it's nonzero. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx + && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT) + && v->new_reg != 0 + && v->mode == mode) + break; + if (v) + { + /* Replace biv with the giv's reduced register. */ + SET_SRC (PATTERN (insn)) = gen_rtx (COMPARE, GET_MODE (v->new_reg), + v->new_reg, + copy_rtx (v->add_val)); + + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + { + XEXP (SET_SRC (PATTERN (insn)), 0) + = XEXP (SET_SRC (PATTERN (insn)), 1); + XEXP (SET_SRC (PATTERN (insn)), 1) = v->new_reg; + } +#if 0 + /* add_val must be invariant, so don't bother storing in a register */ + /* calculate the appropriate constant to compare against */ + emit_insn_before (gen_rtx (SET, VOIDmode, compare_value, + copy_rtx (v->add_val)), + loop_start); +#endif + return; + } + abort (); + break; + + /* a compare insn */ + case COMPARE: + /* Figure out which operand is the biv. */ + if (GET_CODE (XEXP (src, 0)) == REG + && REGNO (XEXP (src, 0)) == bl->regno) + { + arg = XEXP (src, 1); + arg_operand = 1; + } + else if (GET_CODE (XEXP (src, 1)) == REG + && REGNO (XEXP (src, 1)) == bl->regno) + { + arg = XEXP (src, 0); + arg_operand = 0; + } + else + abort (); + + if (GET_CODE (arg) == CONST_INT) + { + /* Can replace with any giv that has constant mult_val and add_val. + Make sure it was strength reduced by checking new_reg != 0. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT + && GET_CODE (v->add_val) == CONST_INT + && v->new_reg + && v->mode == mode) + { + /* Make sure there's no overflow in the range for the giv. */ + if (! (INTVAL (v->mult_val) == 0 + || + (INTVAL (arg) * INTVAL (v->mult_val) / INTVAL (v->mult_val) + != INTVAL (arg)) + || + ((0 < (INTVAL (arg) * INTVAL (v->mult_val) + + INTVAL (v->add_val))) + != (0 < INTVAL (arg))))) + break; + } + if (v) + { + rtx newval; + /* Replace biv with the giv's reduced reg. */ + XEXP (src, 1-arg_operand) = v->new_reg; + /* Calculate the appropriate constant to compare against. */ + newval = gen_rtx (CONST_INT, VOIDmode, + (INTVAL (arg) * INTVAL (v->mult_val) + + INTVAL (v->add_val))); + XEXP (src, arg_operand) = newval; + /* If that constant is no good in a compare, + put it in a register. */ + if (recog (PATTERN (insn), insn) < 0) + { + temp = gen_reg_rtx (mode); + emit_iv_init_code (arg, v->mult_val, v->add_val, + temp, loop_start); + XEXP (src, arg_operand) = temp; + } + + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + { + temp = XEXP (src, 0); + XEXP (src, 0) = XEXP (src, 1); + XEXP (src, 1) = temp; + } + return; + } + + /* Look for giv with constant mult_val and nonconst add_val. + Insert add insn before loop to calculate new compare value. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT + && v->new_reg + && v->mode == mode) + break; + if (v) + { + rtx compare_value = gen_reg_rtx (mode); + + /* Replace biv with giv's reduced register. */ + XEXP (src, 1-arg_operand) = v->new_reg; + + /* At start of loop, compute value to compare against. */ + emit_iv_init_code (arg, v->mult_val, v->add_val, + compare_value, loop_start); + /* Use it in this insn. */ + XEXP (src, arg_operand) = compare_value; + + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + { + temp = XEXP (src, 0); + XEXP (src, 0) = XEXP (src, 1); + XEXP (src, 1) = temp; + } + return; + } + abort (); + } + else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) + { + if (invariant_p (arg)) + { + /* Look for giv with constant mult_val and nonconst add_val. + Insert add-insn before loop to compute new compare value. */ + + for (v = bl->giv; v; v = v->family) + if (GET_CODE (v->mult_val) == CONST_INT + && v->new_reg + && v->mode == mode) + break; + if (v) + { + rtx compare_value = gen_reg_rtx (mode); + + /* Replace biv with giv's reduced register. */ + XEXP (src, 1-arg_operand) = v->new_reg; + + /* At start of loop, compute value to compare against. */ + emit_iv_init_code (arg, v->mult_val, v->add_val, + compare_value, loop_start); + XEXP (src, arg_operand) = compare_value; + + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + { + temp = XEXP (src, 0); + XEXP (src, 0) = XEXP (src, 1); + XEXP (src, 1) = temp; + } + return; + } + } + + /* Otherwise the reg compared with had better be a biv. */ + if (GET_CODE (arg) != REG + || induct_var[REGNO (arg)] != BASIC_INDUCT) + abort (); + + /* Look for a pair of givs, one for each biv, + with identical coefficients. */ + for (v = bl->giv; v; v = v->family) + { + if (!v->new_reg && v->mode == mode) + continue; + for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) + if ((tv->new_reg != 0) + && rtx_equal_p (tv->mult_val, v->mult_val) + && rtx_equal_p (tv->add_val, v->add_val) + && tv->mode == mode) + break; + if (tv) + break; + } + if (v) + { + /* Replace biv with its giv's reduced reg. */ + XEXP (src, 1-arg_operand) = v->new_reg; + /* Replace other operand with the other giv's reduced reg. */ + XEXP (src, arg_operand) = tv->new_reg; + + /* If the giv has the opposite direction of change, + then reverse the comparison. */ + if (INTVAL (v->mult_val) < 0) + { + temp = XEXP (src, 0); + XEXP (src, 0) = XEXP (src, 1); + XEXP (src, 1) = temp; + } + return; + } + } + abort (); + + default: + abort (); + } +} + +/* Try to calculate the final value of the biv, + the value it will have at the end of the loop. + If we can do it, return that value. */ + +/* ??? One case that should be simple to handle + is when the biv is incremented by an invariant + exactly once each time around the loop, + and when the number of iterations can be determined + (as the value of some invariant). + Then the final value would be BIV + (INCREMENT * NUM_ITERATIONS). + + Once that case is handled, it would become desirable to detect empty + loops and delete them, since this optimization could make empty loops. */ + +static rtx +final_biv_value (bl, loop_end) + struct iv_class *bl; + rtx loop_end; +{ + /* wimpy, but guaranteed to work */ + return 0; +} + +/* Return nonzero if the last use of reg REGNO + is in an insn following INSN in the same basic block. */ + +static int +last_use_this_basic_block (regno, insn) + int regno; + rtx insn; +{ + rtx n; + for (n = insn; + n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN; + n = NEXT_INSN (n)) + { + if (regno_last_uid[regno] == INSN_UID (n)) + return 1; + } + return 0; +} |