diff options
Diffstat (limited to 'gcc/loop.c')
| -rwxr-xr-x | gcc/loop.c | 430 |
1 files changed, 0 insertions, 430 deletions
@@ -325,9 +325,6 @@ static int check_dbra_loop (rtx, int, rtx, struct loop_info *); static rtx express_from_1 (rtx, rtx, rtx); static rtx combine_givs_p (struct induction *, struct induction *); static void combine_givs (struct iv_class *); -struct recombine_givs_stats; -static int find_life_end (rtx, struct recombine_givs_stats *, rtx, rtx); -static void recombine_givs (struct iv_class *, rtx, rtx, int); static int product_cheap_p (rtx, rtx); static int maybe_eliminate_biv (struct iv_class *, rtx, rtx, int, int, int); static int maybe_eliminate_biv_1 (rtx, rtx, struct iv_class *, int, rtx); @@ -4625,27 +4622,6 @@ strength_reduce (scan_start, end, loop_top, insn_count, } } -#if 0 - /* Now that we know which givs will be reduced, try to rearrange the - combinations to reduce register pressure. - recombine_givs calls find_life_end, which needs reg_iv_type and - reg_iv_info to be valid for all pseudos. We do the necessary - reallocation here since it allows to check if there are still - more bivs to process. */ - nregs = max_reg_num (); - if (nregs > reg_iv_type->num_elements) - { - /* If there are still more bivs to process, allocate some slack - space so that we're not constantly reallocating these arrays. */ - if (bl->next) - nregs += nregs / 4; - /* Reallocate reg_iv_type and reg_iv_info. */ - VARRAY_GROW (reg_iv_type, nregs); - VARRAY_GROW (reg_iv_info, nregs); - } - recombine_givs (bl, loop_start, loop_end, unroll_p); -#endif - /* Reduce each giv that we decided to reduce. */ for (v = bl->giv; v; v = v->next_iv) @@ -6976,413 +6952,7 @@ restart: } } } - -struct recombine_givs_stats -{ - int giv_number; - int start_luid, end_luid; -}; - -/* Used below as comparison function for qsort. We want a ascending luid - when scanning the array starting at the end, thus the arguments are - used in reverse. */ -static int -cmp_recombine_givs_stats (x, y) - struct recombine_givs_stats *x, *y; -{ - int d; - d = y->start_luid - x->start_luid; - /* Stabilize the sort. */ - if (!d) - d = y->giv_number - x->giv_number; - return d; -} - -/* Scan X, which is a part of INSN, for the end of life of a giv. Also - look for the start of life of a giv where the start has not been seen - yet to unlock the search for the end of its life. - Only consider givs that belong to BIV. - Return the total number of lifetime ends that have been found. */ -static int -find_life_end (x, stats, insn, biv) - rtx x, insn, biv; - struct recombine_givs_stats *stats; -{ - enum rtx_code code; - char *fmt; - int i, j; - int retval; - - code = GET_CODE (x); - switch (code) - { - case SET: - { - rtx reg = SET_DEST (x); - if (GET_CODE (reg) == REG) - { - int regno = REGNO (reg); - struct induction *v = REG_IV_INFO (regno); - - if (REG_IV_TYPE (regno) == GENERAL_INDUCT - && ! v->ignore - && v->src_reg == biv - && stats[v->ix].end_luid <= 0) - { - /* If we see a 0 here for end_luid, it means that we have - scanned the entire loop without finding any use at all. - We must not predicate this code on a start_luid match - since that would make the test fail for givs that have - been hoisted out of inner loops. */ - if (stats[v->ix].end_luid == 0) - { - stats[v->ix].end_luid = stats[v->ix].start_luid; - return 1 + find_life_end (SET_SRC (x), stats, insn, biv); - } - else if (stats[v->ix].start_luid == INSN_LUID (insn)) - stats[v->ix].end_luid = 0; - } - return find_life_end (SET_SRC (x), stats, insn, biv); - } - break; - } - case REG: - { - int regno = REGNO (x); - struct induction *v = REG_IV_INFO (regno); - - if (REG_IV_TYPE (regno) == GENERAL_INDUCT - && ! v->ignore - && v->src_reg == biv - && stats[v->ix].end_luid == 0) - { - while (INSN_UID (insn) >= max_uid_for_loop) - insn = NEXT_INSN (insn); - stats[v->ix].end_luid = INSN_LUID (insn); - return 1; - } - return 0; - } - case LABEL_REF: - case CONST_DOUBLE: - case CONST_INT: - case CONST: - return 0; - default: - break; - } - fmt = GET_RTX_FORMAT (code); - retval = 0; - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - retval += find_life_end (XEXP (x, i), stats, insn, biv); - - else if (fmt[i] == 'E') - for (j = XVECLEN (x, i) - 1; j >= 0; j--) - retval += find_life_end (XVECEXP (x, i, j), stats, insn, biv); - } - return retval; -} - -/* For each giv that has been combined with another, look if - we can combine it with the most recently used one instead. - This tends to shorten giv lifetimes, and helps the next step: - try to derive givs from other givs. */ -static void -recombine_givs (bl, loop_start, loop_end, unroll_p) - struct iv_class *bl; - rtx loop_start, loop_end; - int unroll_p; -{ - struct induction *v, **giv_array, *last_giv; - struct recombine_givs_stats *stats; - int giv_count; - int i, rescan; - int ends_need_computing; - - for (giv_count = 0, v = bl->giv; v; v = v->next_iv) - { - if (! v->ignore) - giv_count++; - } - giv_array - = (struct induction **) alloca (giv_count * sizeof (struct induction *)); - stats = (struct recombine_givs_stats *) alloca (giv_count * sizeof *stats); - - /* Initialize stats and set up the ix field for each giv in stats to name - the corresponding index into stats. */ - for (i = 0, v = bl->giv; v; v = v->next_iv) - { - rtx p; - - if (v->ignore) - continue; - giv_array[i] = v; - stats[i].giv_number = i; - /* If this giv has been hoisted out of an inner loop, use the luid of - the previous insn. */ - for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; ) - p = PREV_INSN (p); - stats[i].start_luid = INSN_LUID (p); - v->ix = i; - i++; - } - - qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats); - - /* Do the actual most-recently-used recombination. */ - for (last_giv = 0, i = giv_count - 1; i >= 0; i--) - { - v = giv_array[stats[i].giv_number]; - if (v->same) - { - struct induction *old_same = v->same; - rtx new_combine; - - /* combine_givs_p actually says if we can make this transformation. - The other tests are here only to avoid keeping a giv alive - that could otherwise be eliminated. */ - if (last_giv - && ((old_same->maybe_dead && ! old_same->combined_with) - || ! last_giv->maybe_dead - || last_giv->combined_with) - && (new_combine = combine_givs_p (last_giv, v))) - { - old_same->combined_with--; - v->new_reg = new_combine; - v->same = last_giv; - last_giv->combined_with++; - /* No need to update lifetimes / benefits here since we have - already decided what to reduce. */ - continue; - } - v = v->same; - } - else if (v->giv_type != DEST_REG) - continue; - if (! last_giv - || (last_giv->maybe_dead && ! last_giv->combined_with) - || ! v->maybe_dead - || v->combined_with) - last_giv = v; - } - - ends_need_computing = 0; - /* For each DEST_REG giv, compute lifetime starts, and try to compute - lifetime ends from regscan info. */ - for (i = 0, v = bl->giv; v; v = v->next_iv) - { - if (v->ignore) - continue; - if (v->giv_type == DEST_ADDR) - { - /* Loop unrolling of an inner loop can even create new DEST_REG - givs. */ - rtx p; - for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; ) - p = PREV_INSN (p); - stats[i].start_luid = stats[i].end_luid = INSN_LUID (p); - if (p != v->insn) - stats[i].end_luid++; - } - else /* v->giv_type == DEST_REG */ - { - if (v->last_use) - { - stats[i].start_luid = INSN_LUID (v->insn); - stats[i].end_luid = INSN_LUID (v->last_use); - } - else if (INSN_UID (v->insn) >= max_uid_for_loop) - { - rtx p; - /* This insn has been created by loop optimization on an inner - loop. We don't have a proper start_luid that will match - when we see the first set. But we do know that there will - be no use before the set, so we can set end_luid to 0 so that - we'll start looking for the last use right away. */ - for (p = PREV_INSN (v->insn); INSN_UID (p) >= max_uid_for_loop; ) - p = PREV_INSN (p); - stats[i].start_luid = INSN_LUID (p); - stats[i].end_luid = 0; - ends_need_computing++; - } - else - { - int regno = REGNO (v->dest_reg); - int count = VARRAY_INT (n_times_set, regno) - 1; - rtx p = v->insn; - - /* Find the first insn that sets the giv, so that we can verify - if this giv's lifetime wraps around the loop. We also need - the luid of the first setting insn in order to detect the - last use properly. */ - while (count) - { - p = prev_nonnote_insn (p); - if (reg_set_p (v->dest_reg, p)) - count--; - } - stats[i].start_luid = INSN_LUID (p); - if (stats[i].start_luid > uid_luid[REGNO_FIRST_UID (regno)]) - { - stats[i].end_luid = -1; - ends_need_computing++; - } - else - { - stats[i].end_luid = uid_luid[REGNO_LAST_UID (regno)]; - if (stats[i].end_luid > INSN_LUID (loop_end)) - { - stats[i].end_luid = -1; - ends_need_computing++; - } - } - } - } - i++; - } - - /* If the regscan information was unconclusive for one or more DEST_REG - givs, scan the all insn in the loop to find out lifetime ends. */ - if (ends_need_computing) - { - rtx biv = bl->biv->src_reg; - rtx p = loop_end; - - do - { - if (p == loop_start) - p = loop_end; - p = PREV_INSN (p); - if (GET_RTX_CLASS (GET_CODE (p)) != 'i') - continue; - ends_need_computing -= find_life_end (PATTERN (p), stats, p, biv); - } - while (ends_need_computing); - } - - /* Set start_luid back to the last insn that sets the giv. This allows - more combinations. */ - for (i = 0, v = bl->giv; v; v = v->next_iv) - { - if (v->ignore) - continue; - if (INSN_UID (v->insn) < max_uid_for_loop) - stats[i].start_luid = INSN_LUID (v->insn); - i++; - } - - /* Now adjust lifetime ends by taking combined givs into account. */ - for (i = 0, v = bl->giv; v; v = v->next_iv) - { - unsigned luid; - int j; - - if (v->ignore) - continue; - if (v->same && ! v->same->ignore) - { - j = v->same->ix; - luid = stats[i].start_luid; - /* Use unsigned arithmetic to model loop wrap-around. */ - if (luid - stats[j].start_luid - > (unsigned) stats[j].end_luid - stats[j].start_luid) - stats[j].end_luid = luid; - } - i++; - } - - qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats); - - /* Try to derive DEST_REG givs from previous DEST_REG givs with the - same mult_val and non-overlapping lifetime. This reduces register - pressure. - Once we find a DEST_REG giv that is suitable to derive others from, - we set last_giv to this giv, and try to derive as many other DEST_REG - givs from it without joining overlapping lifetimes. If we then - encounter a DEST_REG giv that we can't derive, we set rescan to the - index for this giv (unless rescan is already set). - When we are finished with the current LAST_GIV (i.e. the inner loop - terminates), we start again with rescan, which then becomes the new - LAST_GIV. */ - for (i = giv_count - 1; i >= 0; i = rescan) - { - int life_start, life_end; - - for (last_giv = 0, rescan = -1; i >= 0; i--) - { - rtx sum; - - v = giv_array[stats[i].giv_number]; - if (v->giv_type != DEST_REG || v->derived_from || v->same) - continue; - if (! last_giv) - { - /* Don't use a giv that's likely to be dead to derive - others - that would be likely to keep that giv alive. */ - if (! v->maybe_dead || v->combined_with) - { - last_giv = v; - life_start = stats[i].start_luid; - life_end = stats[i].end_luid; - } - continue; - } - /* Use unsigned arithmetic to model loop wrap around. */ - if (((unsigned) stats[i].start_luid - life_start - >= (unsigned) life_end - life_start) - && ((unsigned) stats[i].end_luid - life_start - > (unsigned) life_end - life_start) - /* Check that the giv insn we're about to use for deriving - precedes all uses of that giv. Note that initializing the - derived giv would defeat the purpose of reducing register - pressure. - ??? We could arrange to move the insn. */ - && ((unsigned) stats[i].end_luid - INSN_LUID (loop_start) - > (unsigned) stats[i].start_luid - INSN_LUID (loop_start)) - && rtx_equal_p (last_giv->mult_val, v->mult_val) - /* ??? Could handle libcalls, but would need more logic. */ - && ! find_reg_note (v->insn, REG_RETVAL, NULL_RTX) - /* We would really like to know if for any giv that v - is combined with, v->insn or any intervening biv increment - dominates that combined giv. However, we - don't have this detailed control flow information. - N.B. since last_giv will be reduced, it is valid - anywhere in the loop, so we don't need to check the - validity of last_giv. - We rely here on the fact that v->always_executed implies that - there is no jump to someplace else in the loop before the - giv insn, and hence any insn that is executed before the - giv insn in the loop will have a lower luid. */ - && (v->always_executed || ! v->combined_with) - && (sum = express_from (last_giv, v)) - /* Make sure we don't make the add more expensive. ADD_COST - doesn't take different costs of registers and constants into - account, so compare the cost of the actual SET_SRCs. */ - && (rtx_cost (sum, SET) - <= rtx_cost (SET_SRC (single_set (v->insn)), SET)) - /* ??? unroll can't understand anything but reg + const_int - sums. It would be cleaner to fix unroll. */ - && ((GET_CODE (sum) == PLUS - && GET_CODE (XEXP (sum, 0)) == REG - && GET_CODE (XEXP (sum, 1)) == CONST_INT) - || ! unroll_p) - && validate_change (v->insn, &PATTERN (v->insn), - gen_rtx_SET (GET_MODE (v->dest_reg), - v->dest_reg, sum), 0)) - { - v->derived_from = last_giv; - v->new_reg = v->dest_reg; - life_end = stats[i].end_luid; - } - else if (rescan < 0) - rescan = i; - } - } -} - /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */ void |