-
- for (j = 0; j < giv_count; j++)
- {
- rtx this_combine;
-
- g2 = giv_array[j];
- if (g1 != g2
- && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
- {
- can_combine[i * giv_count + j] = this_combine;
- this_benefit += g2->benefit + extra_benefit;
- }
- }
- stats[i].total_benefit = this_benefit;
- }
-
- /* Iterate, combining until we can't. */
-restart:
- qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
-
- if (loop_dump_stream)
- {
- fprintf (loop_dump_stream, "Sorted combine statistics:\n");
- for (k = 0; k < giv_count; k++)
- {
- g1 = giv_array[stats[k].giv_number];
- if (!g1->combined_with && !g1->same)
- fprintf (loop_dump_stream, " {%d, %d}",
- INSN_UID (giv_array[stats[k].giv_number]->insn),
- stats[k].total_benefit);
- }
- putc ('\n', loop_dump_stream);
- }
-
- for (k = 0; k < giv_count; k++)
- {
- int g1_add_benefit = 0;
-
- i = stats[k].giv_number;
- g1 = giv_array[i];
-
- /* If it has already been combined, skip. */
- if (g1->combined_with || g1->same)
- continue;
-
- for (j = 0; j < giv_count; j++)
- {
- g2 = giv_array[j];
- if (g1 != g2 && can_combine[i * giv_count + j]
- /* If it has already been combined, skip. */
- && ! g2->same && ! g2->combined_with)
- {
- int l;
-
- g2->new_reg = can_combine[i * giv_count + j];
- g2->same = g1;
- g1->combined_with++;
- g1->lifetime += g2->lifetime;
-
- g1_add_benefit += g2->benefit;
-
- /* ??? The new final_[bg]iv_value code does a much better job
- of finding replaceable giv's, and hence this code may no
- longer be necessary. */
- if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
- g1_add_benefit -= copy_cost;
-
- /* To help optimize the next set of combinations, remove
- this giv from the benefits of other potential mates. */
- for (l = 0; l < giv_count; ++l)
- {
- int m = stats[l].giv_number;
- if (can_combine[m * giv_count + j])
- stats[l].total_benefit -= g2->benefit + extra_benefit;
- }
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
- INSN_UID (g2->insn), INSN_UID (g1->insn),
- g1->benefit, g1_add_benefit, g1->lifetime);
- }
- }
-
- /* To help optimize the next set of combinations, remove
- this giv from the benefits of other potential mates. */
- if (g1->combined_with)
- {
- for (j = 0; j < giv_count; ++j)
- {
- int m = stats[j].giv_number;
- if (can_combine[m * giv_count + i])
- stats[j].total_benefit -= g1->benefit + extra_benefit;
- }
-
- g1->benefit += g1_add_benefit;
-
- /* We've finished with this giv, and everything it touched.
- Restart the combination so that proper weights for the
- rest of the givs are properly taken into account. */
- /* ??? Ideally we would compact the arrays at this point, so
- as to not cover old ground. But sanely compacting
- can_combine is tricky. */
- goto restart;
- }
- }
-
- /* Clean up. */
- free (stats);
- free (can_combine);
-}
-\f
-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 (xp, yp)
- const PTR xp;
- const PTR yp;
-{
- const struct recombine_givs_stats * const x =
- (const struct recombine_givs_stats *) xp;
- const struct recombine_givs_stats * const y =
- (const struct recombine_givs_stats *) yp;
- 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 (loop, x, stats, insn, biv)
- const struct loop *loop;
- rtx x, insn, biv;
- struct recombine_givs_stats *stats;
-{
- struct loop_ivs *ivs = LOOP_IVS (loop);
- enum rtx_code code;
- const 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 (ivs, regno);
-
- if (REG_IV_TYPE (ivs, 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 (loop, 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 (loop, SET_SRC (x), stats, insn, biv);
- }
- break;
- }
- case REG:
- {
- int regno = REGNO (x);
- struct induction *v = REG_IV_INFO (ivs, regno);
-
- if (REG_IV_TYPE (ivs, 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 (loop, XEXP (x, i), stats, insn, biv);
-
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- retval += find_life_end (loop, 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 (loop, bl, unroll_p)
- const struct loop *loop;
- struct iv_class *bl;
- int unroll_p;
-{
- struct loop_regs *regs = LOOP_REGS (loop);
- 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 **) xmalloc (giv_count * sizeof (struct induction *));
- stats = (struct recombine_givs_stats *) xmalloc (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);
- i++;
- }
-
- qsort (stats, giv_count, sizeof (*stats), cmp_recombine_givs_stats);
-
- /* Set up the ix field for each giv in stats to name
- the corresponding index into stats, and
- 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];
- v->ix = i;
- 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. */
-
- if (loop_dump_stream)
- {
- fprintf (loop_dump_stream,
- "giv at %d recombined with giv at %d as ",
- INSN_UID (v->insn), INSN_UID (last_giv->insn));
- print_rtl (loop_dump_stream, v->new_reg);
- putc ('\n', loop_dump_stream);
- }
- 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 = giv_count - 1; i >= 0; i--)
- {
- v = giv_array[stats[i].giv_number];
- 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 */