This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Re: infinite loop in loop.c with -O2
- To: mrs at wrs dot com (Mike Stump), law at cygnus dot com
- Subject: Re: infinite loop in loop.c with -O2
- From: Joern Rennecke <amylaar at cygnus dot co dot uk>
- Date: Mon, 21 Jun 1999 18:00:18 +0100 (BST)
- Cc: egcs-bugs at egcs dot cygnus dot com, amylaar at cygnus dot com, egcs-patches at egcs dot cygnus dot com
> I too am seeing an infinite loop when bootstrapping. This is on
> x86-linux. I was compiling regclass.o with stage1, 18hr of CPU time
> later... I was using:
>
> File: loop.c Status: Up-to-date
>
> Working revision: 1.165
> Repository revision: 1.165 /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
>
> stage1/xgcc -Bstage1/ -c -DIN_GCC -DUSE_GNULIBC_1 -O2 -DHAVE_CONFIG_H -I. -I../../egcs/gcc -I../../egcs/gcc/config -I../../egcs/gcc/../include ../../egcs/gcc/regclass.c
>
> was the command. It loops while compiling init_reg_sets_1.
The code using find_life_end was bogus. I've replaced it some time ago,
but the patch hasn't been reviewed yet.
Tue Jun 15 21:12:19 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* loop.c (strength_reduce): Move processing of biv increments
that we derive from here...
(recombine_givs): To here. Fix it for DEST_ADDR givs. Don't
ignore single biv increments; instead, skip ones that are
known to be outside the giv lifetime.
Don't move DEST_ADDR givs for leading_combined.
Wed May 12 21:49:04 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* loop.h (struct induction): New members live_after_loop,
leading_combined.
* loop.c (recombine_givs): Remove bogus index / giv lockstep looping.
Use leading_combined to determine if giv must be moved.
* (recombine_givs): Allocate new_reg for derived givs.
(strength_reduce): Simplify code dealing with derived givs knowing
that the new_reg is allocated early now.
* loop.c (find_life_end): Deleted.
(find_giv_uses, note_giv_use, cmp_giv_by_value_and_insn): New functions.
(strength_reduce): Set new fields in struct induction for givs.
(recombine_givs): New parameters. Changed caller.
(record_giv): Set new fields in struct induction.
(recombine_givs): Givs life only from their first use to their
last use if there is no intervening label; we then move the
set just before the use if the giv gets derived.
Allow DEST_ADDR giv to be derived.
Index: loop.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.h,v
retrieving revision 1.18
diff -p -r1.18 loop.h
*** loop.h 1999/02/24 11:50:49 1.18
--- loop.h 1999/06/21 16:18:09
*************** struct induction
*** 101,106 ****
--- 101,114 ----
initialized in unrolled loop. */
unsigned shared : 1;
unsigned no_const_addval : 1; /* 1 if add_val does not contain a const. */
+ unsigned live_after_loop : 1; /* Used inside recombine_givs to keep track
+ of which givs have already been included
+ in an array of givs live after the loop. */
+ unsigned leading_combined : 1;/* In recombine_givs, set if this giv has been
+ combined with one or more other givs that
+ precede the giv insn of this giv.
+ Giv derivation then requires to move the
+ giv insn before the first use. */
int lifetime; /* Length of life of this giv */
rtx derive_adjustment; /* If nonzero, is an adjustment to be
subtracted from add_val when this giv
Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.165
diff -p -r1.165 loop.c
*** loop.c 1999/06/17 13:35:59 1.165
--- loop.c 1999/06/21 16:18:12
*************** static rtx express_from_1 PROTO((rtx, rt
*** 330,337 ****
static rtx combine_givs_p PROTO((struct induction *, struct induction *));
static void combine_givs PROTO((struct iv_class *));
struct recombine_givs_stats;
! static int find_life_end PROTO((rtx, struct recombine_givs_stats *, rtx, rtx));
! static void recombine_givs PROTO((struct iv_class *, rtx, rtx, int));
static int product_cheap_p PROTO((rtx, rtx));
static int maybe_eliminate_biv PROTO((struct iv_class *, rtx, rtx, int, int, int));
static int maybe_eliminate_biv_1 PROTO((rtx, rtx, struct iv_class *, int, rtx));
--- 330,340 ----
static rtx combine_givs_p PROTO((struct induction *, struct induction *));
static void combine_givs PROTO((struct iv_class *));
struct recombine_givs_stats;
! static void find_giv_uses PROTO((rtx, struct recombine_givs_stats *, rtx,
! rtx));
! static void note_giv_use PROTO((struct induction *, rtx, int,
! struct recombine_givs_stats *));
! static void recombine_givs PROTO((struct iv_class *, rtx, rtx, rtx, rtx, int));
static int product_cheap_p PROTO((rtx, rtx));
static int maybe_eliminate_biv PROTO((struct iv_class *, rtx, rtx, int, int, int));
static int maybe_eliminate_biv_1 PROTO((rtx, rtx, struct iv_class *, int, rtx));
*************** strength_reduce (scan_start, end, loop_t
*** 4063,4068 ****
--- 4059,4070 ----
if (loop_dump_stream)
fprintf (loop_dump_stream, "is giv of biv %d\n", bl2->regno);
+
+ /* If the changed insn carries a REG_EQUAL note, update it. */
+ note = find_reg_note (bl->biv->insn, REG_EQUAL, NULL_RTX);
+ if (note)
+ XEXP (note, 0) = copy_rtx (src);
+
/* Let this giv be discovered by the generic code. */
REG_IV_TYPE (bl->regno) = UNKNOWN_INDUCT;
reg_biv_class[bl->regno] = NULL_PTR;
*************** strength_reduce (scan_start, end, loop_t
*** 4220,4225 ****
--- 4219,4226 ----
add_val = plus_constant (next->add_val, offset);
old_reg = v->dest_reg;
dest_reg = gen_reg_rtx (v->mode);
+ old_regno = REGNO (old_reg);
+ new_regno = REGNO (dest_reg);
/* Unlike reg_iv_type / reg_iv_info, the other three arrays
have been allocated with some slop space, so we may not
*************** strength_reduce (scan_start, end, loop_t
*** 4233,4238 ****
--- 4234,4240 ----
VARRAY_GROW (may_not_optimize, nregs);
VARRAY_GROW (reg_single_usage, nregs);
}
+ VARRAY_CHAR (may_not_optimize, new_regno) = 0;
if (! validate_change (next->insn, next->location, add_val, 0))
{
*************** strength_reduce (scan_start, end, loop_t
*** 4257,4266 ****
}
}
! /* If we can't get the LUIDs for the insns, we can't
! calculate the lifetime. This is likely from unrolling
! of an inner loop, so there is little point in making this
! a DEST_REG giv anyways. */
if (INSN_UID (v->insn) >= max_uid_for_loop
|| INSN_UID (last_use_insn) >= max_uid_for_loop
|| ! validate_change (v->insn, &SET_DEST (set), dest_reg, 0))
--- 4259,4271 ----
}
}
! /* We'd like to make this a DEST_REG
! giv. However, after loop unrolling, V->INSN or LAST_USE_INSN
! might have no valid luid. We need these not only for
! calculating the lifetime now, but also in recombine_givs when
! doing giv derivation, to find givs with non-overlapping
! lifetimes. So if we don't have LUIDs available, or if we
! can't calculate the giv, leave the biv increment alone. */
if (INSN_UID (v->insn) >= max_uid_for_loop
|| INSN_UID (last_use_insn) >= max_uid_for_loop
|| ! validate_change (v->insn, &SET_DEST (set), dest_reg, 0))
*************** strength_reduce (scan_start, end, loop_t
*** 4272,4278 ****
--- 4277,4296 ----
vp = &v->next_iv;
continue;
}
+
+ /* If next_insn has a REG_EQUAL note that mentiones OLD_REG,
+ it must be replaced. */
+ note = find_reg_note (next->insn, REG_EQUAL, NULL_RTX);
+ if (note && reg_mentioned_p (old_reg, XEXP (note, 0)))
+ XEXP (note, 0) = copy_rtx (SET_SRC (single_set (next->insn)));
+
+ /* Remove the increment from the list of biv increments. */
+ *vp = next;
+ bl->biv_count--;
+ VARRAY_INT (set_in_loop, old_regno)--;
+ VARRAY_INT (n_times_set, old_regno)--;
next->add_val = add_val;
+
v->dest_reg = dest_reg;
v->giv_type = DEST_REG;
v->location = &SET_SRC (set);
*************** strength_reduce (scan_start, end, loop_t
*** 4293,4320 ****
v->always_executed = 1;
v->replaceable = 1;
v->no_const_addval = 0;
- old_regno = REGNO (old_reg);
- new_regno = REGNO (dest_reg);
- VARRAY_INT (set_in_loop, old_regno)--;
VARRAY_INT (set_in_loop, new_regno) = 1;
- VARRAY_INT (n_times_set, old_regno)--;
VARRAY_INT (n_times_set, new_regno) = 1;
- VARRAY_CHAR (may_not_optimize, new_regno) = 0;
REG_IV_TYPE (new_regno) = GENERAL_INDUCT;
REG_IV_INFO (new_regno) = v;
!
! /* If next_insn has a REG_EQUAL note that mentiones OLD_REG,
! it must be replaced. */
! note = find_reg_note (next->insn, REG_EQUAL, NULL_RTX);
! if (note && reg_mentioned_p (old_reg, XEXP (note, 0)))
! XEXP (note, 0) = copy_rtx (SET_SRC (single_set (next->insn)));
!
! /* Remove the increment from the list of biv increments,
! and record it as a giv. */
! *vp = next;
! bl->biv_count--;
v->next_iv = bl->giv;
bl->giv = v;
bl->giv_count++;
--- 4311,4325 ----
v->always_executed = 1;
v->replaceable = 1;
v->no_const_addval = 0;
+ v->leading_combined = 0;
VARRAY_INT (set_in_loop, new_regno) = 1;
VARRAY_INT (n_times_set, new_regno) = 1;
REG_IV_TYPE (new_regno) = GENERAL_INDUCT;
REG_IV_INFO (new_regno) = v;
!
! /* Record V as a giv. */
v->next_iv = bl->giv;
bl->giv = v;
bl->giv_count++;
*************** strength_reduce (scan_start, end, loop_t
*** 4745,4751 ****
/* 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. */
--- 4750,4756 ----
/* Now that we know which givs will be reduced, try to rearrange the
combinations to reduce register pressure.
! recombine_givs calls find_giv_uses, 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. */
*************** strength_reduce (scan_start, end, loop_t
*** 4760,4766 ****
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
}
! recombine_givs (bl, loop_start, loop_end, unroll_p);
/* Reduce each giv that we decided to reduce. */
--- 4765,4771 ----
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
}
! recombine_givs (bl, scan_start, loop_start, loop_end, loop_top, unroll_p);
/* Reduce each giv that we decided to reduce. */
*************** strength_reduce (scan_start, end, loop_t
*** 4771,4819 ****
{
int auto_inc_opt = 0;
! /* If the code for derived givs immediately below has already
allocated a new_reg, we must keep it. */
if (! v->new_reg)
v->new_reg = gen_reg_rtx (v->mode);
if (v->derived_from)
! {
! struct induction *d = v->derived_from;
!
! /* In case d->dest_reg is not replaceable, we have
! to replace it in v->insn now. */
! if (! d->new_reg)
! d->new_reg = gen_reg_rtx (d->mode);
! PATTERN (v->insn)
! = replace_rtx (PATTERN (v->insn), d->dest_reg, d->new_reg);
! PATTERN (v->insn)
! = replace_rtx (PATTERN (v->insn), v->dest_reg, v->new_reg);
! /* For each place where the biv is incremented, add an
! insn to set the new, reduced reg for the giv.
! We used to do this only for biv_count != 1, but
! this fails when there is a giv after a single biv
! increment, e.g. when the last giv was expressed as
! pre-decrement. */
! for (tv = bl->biv; tv; tv = tv->next_iv)
! {
! /* We always emit reduced giv increments before the
! biv increment when bl->biv_count != 1. So by
! emitting the add insns for derived givs after the
! biv increment, they pick up the updated value of
! the reduced giv.
! If the reduced giv is processed with
! auto_inc_opt == 1, then it is incremented earlier
! than the biv, hence we'll still pick up the right
! value.
! If it's processed with auto_inc_opt == -1,
! that implies that the biv increment is before the
! first reduced giv's use. The derived giv's lifetime
! is after the reduced giv's lifetime, hence in this
! case, the biv increment doesn't matter. */
! emit_insn_after (copy_rtx (PATTERN (v->insn)), tv->insn);
! }
! continue;
! }
#ifdef AUTO_INC_DEC
/* If the target has auto-increment addressing modes, and
--- 4776,4788 ----
{
int auto_inc_opt = 0;
! /* If the code for derived givs in recombine_givs has already
allocated a new_reg, we must keep it. */
if (! v->new_reg)
v->new_reg = gen_reg_rtx (v->mode);
if (v->derived_from)
! continue;
#ifdef AUTO_INC_DEC
/* If the target has auto-increment addressing modes, and
*************** record_giv (v, insn, src_reg, dest_reg,
*** 5422,5427 ****
--- 5391,5397 ----
v->auto_inc_opt = 0;
v->unrolled = 0;
v->shared = 0;
+ v->leading_combined = 0;
v->derived_from = 0;
v->last_use = 0;
*************** combine_givs (bl)
*** 6968,6973 ****
--- 6938,6944 ----
this_benefit += g2->benefit + extra_benefit;
}
}
+ stats[i].giv_number = i;
stats[i].total_benefit = this_benefit;
}
*************** struct recombine_givs_stats
*** 7066,7071 ****
--- 7037,7045 ----
{
int giv_number;
int start_luid, end_luid;
+ rtx start_insn; /* First insn in loop order in which the giv (including
+ combinations) is used; Initialized to NULL_RTX; set
+ to a NOTE when invalid. */
};
/* Used below as comparison function for qsort. We want a ascending luid
*************** cmp_recombine_givs_stats (x, y)
*** 7083,7095 ****
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;
{
--- 7057,7108 ----
return d;
}
! /* The last label we encountered while scanning forward for giv uses.
! Is initialized to SCAN_START (not necessarily a label) in recombine_givs. */
! static rtx loop_last_label;
!
! /* V, a giv, is used in INSN.
! FROM_COMBINED is set if the use comes (possibly) from a combined giv.
! It must not be set if there are no combined givs for this giv, since
! this can confuse giv derivation to move the giv insn to the wrong place.
! Update start_insn / end_luid in STATS accordingly. */
! static void
! note_giv_use (v, insn, from_combined, stats)
! struct induction *v;
! rtx insn;
! int from_combined;
! struct recombine_givs_stats *stats;
! {
! if (stats[v->ix].start_insn)
! {
! if (loop_insn_first_p (stats[v->ix].start_insn, loop_last_label)
! && (loop_insn_first_p (loop_last_label, insn)
! || loop_insn_first_p (insn, stats[v->ix].start_insn)))
! stats[v->ix].start_insn = loop_number_loop_starts[0];
! }
! else
! {
! rtx p;
!
! stats[v->ix].start_insn = insn;
! if (from_combined)
! v->leading_combined = 1;
!
! /* Update start_luid now so that we won't loose this information it
! when we invalidate start_insn. */
! for (p = insn; INSN_UID (p) >= max_uid_for_loop; )
! p = PREV_INSN (p);
! stats[v->ix].start_luid = INSN_LUID (p);
! }
! while (INSN_UID (insn) >= max_uid_for_loop)
! insn = NEXT_INSN (insn);
! stats[v->ix].end_luid = INSN_LUID (insn);
! }
!
! /* Scan X, which is a part of INSN, for uses of givs.
! Only consider givs that belong to BIV. */
! static void
! find_giv_uses (x, stats, insn, biv)
rtx x, insn, biv;
struct recombine_givs_stats *stats;
{
*************** find_life_end (x, stats, insn, biv)
*** 7111,7158 ****
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;
}
--- 7124,7199 ----
if (REG_IV_TYPE (regno) == GENERAL_INDUCT
&& ! v->ignore
! && v->src_reg == biv)
! {
! /* Since we are setting a non-ignored general induction
! variable, this insn will be changed or go away, hence
! we don't have to consider uses in the SET_SRC. */
! return;
! }
! find_giv_uses (SET_SRC (x), stats, insn, biv);
! return;
! }
! break;
! }
! /* If this is a reduced DEST_ADDR giv, the original address doesn't
! count; but if the giv has been combined with another one, we must
! count the use there. */
! case MEM:
! {
! rtx src_reg;
! rtx add_val;
! rtx mult_val;
! int benefit;
! struct induction *v;
!
! if (general_induction_var (XEXP (x, 0), &src_reg, &add_val,
! &mult_val, 1, &benefit)
! && src_reg == biv)
! {
! for (v = reg_biv_class[REGNO (biv)]->giv; v; v = v->next_iv)
{
! if (v->location == &XEXP (x, 0))
{
! int from_combined = 0;
!
! if (v->same)
! {
! v = v->same;
! from_combined = 1;
! }
! if (v->ignore)
! break;
! note_giv_use (v, insn, from_combined, stats);
! return;
}
}
}
break;
}
case REG:
{
int regno = REGNO (x);
! if (REG_IV_TYPE (regno) == GENERAL_INDUCT)
{
! struct induction *v = REG_IV_INFO (regno);
! int from_combined = 0;
!
! if (v->same)
! {
! v = v->same;
! from_combined = 1;
! }
! if (! v->ignore && v->src_reg == biv)
! note_giv_use (v, insn, from_combined, stats);
}
! return;
}
case LABEL_REF:
case CONST_DOUBLE:
case CONST_INT:
case CONST:
! return;
default:
break;
}
*************** find_life_end (x, stats, insn, biv)
*** 7161,7173 ****
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
--- 7202,7214 ----
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
! find_giv_uses (XEXP (x, i), stats, insn, biv);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
! find_giv_uses (XVECEXP (x, i, j), stats, insn, biv);
}
! return;
}
/* For each giv that has been combined with another, look if
*************** find_life_end (x, stats, insn, biv)
*** 7175,7190 ****
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)
{
--- 7216,7234 ----
This tends to shorten giv lifetimes, and helps the next step:
try to derive givs from other givs. */
static void
! recombine_givs (bl, scan_start, loop_start, loop_end, loop_top, unroll_p)
struct iv_class *bl;
! rtx scan_start, loop_start, loop_end, loop_top;
int unroll_p;
{
struct induction *v, **giv_array, *last_giv;
struct recombine_givs_stats *stats;
int giv_count;
int i, rescan;
! int n_giv_live_after_loop;
! struct induction **giv_live_after_loop;
! rtx biv_use_start, biv_use_end;
! int life_start, life_end;
for (giv_count = 0, v = bl->giv; v; v = v->next_iv)
{
*************** recombine_givs (bl, loop_start, loop_end
*** 7195,7208 ****
= (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
--- 7239,7259 ----
= (struct induction **) alloca (giv_count * sizeof (struct induction *));
stats = (struct recombine_givs_stats *) alloca (giv_count * sizeof *stats);
! /* Initialize stats, and clear the live_after_loop fields.
! Also note where the biv is used by unreduced givs. */
! for (i = 0, biv_use_start = biv_use_end = 0, v = bl->giv; v; v = v->next_iv)
{
rtx p;
if (v->ignore)
! {
! if (! biv_use_start || loop_insn_first_p (v->insn, biv_use_start))
! biv_use_start = v->insn;
! if (! biv_use_end || loop_insn_first_p (biv_use_end, v->insn))
! biv_use_end = v->insn;
! continue;
! }
! v->live_after_loop = 0;
giv_array[i] = v;
stats[i].giv_number = i;
/* If this giv has been hoisted out of an inner loop, use the luid of
*************** recombine_givs (bl, loop_start, loop_end
*** 7210,7215 ****
--- 7261,7267 ----
for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; )
p = PREV_INSN (p);
stats[i].start_luid = INSN_LUID (p);
+ stats[i].start_insn = NULL_RTX;
i++;
}
*************** recombine_givs (bl, loop_start, loop_end
*** 7264,7393 ****
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);
--- 7316,7408 ----
last_giv = v;
}
! /* Set up the giv_live_after_loop array. */
! n_giv_live_after_loop = 0;
! giv_live_after_loop = NULL_PTR;
! for (v = bl->giv; v; v = v->next_iv)
{
! struct induction *same;
!
! if (v->giv_type != DEST_REG || v->last_use)
continue;
! if ((uid_luid[REGNO_FIRST_UID (REGNO (v->dest_reg))]
! > INSN_LUID (loop_start))
! && (uid_luid[REGNO_LAST_UID (REGNO (v->dest_reg))]
! < INSN_LUID (loop_end)))
! continue;
! same = v->same ? v->same : v;
! if (! same->ignore
! && ! same->live_after_loop)
! {
! same->live_after_loop = 1;
! if (! giv_live_after_loop)
! giv_live_after_loop
! = (struct induction **) alloca (sizeof (struct induction *)
! * giv_count);
! giv_live_after_loop[n_giv_live_after_loop++] = same;
}
}
! /* Scan all the insns in the loop to find out lifetime starts and ends. */
! {
! rtx biv = bl->biv->src_reg;
! rtx p = loop_end;
! for (loop_last_label = scan_start, p = scan_start; p;
! p = next_insn_in_loop (p, scan_start, loop_end, loop_top))
! {
! if (GET_CODE (p) == CODE_LABEL)
! loop_last_label = p;
! else if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
! {
! find_giv_uses (PATTERN (p), stats, p, biv);
! /* If this is a jump, we have to consider uses outside the loop. */
! if (GET_CODE (p) == JUMP_INSN && GET_CODE (PATTERN (p)) != RETURN)
! {
! int is_loop_exit = 1;
! rtx label;
! if (condjump_p (p) || condjump_in_parallel_p (p))
! {
! label = XEXP (condjump_label (p), 0);
! /* If the destination is within the loop, and this
! is not a conditional branch at the loop end, this
! is not a loop exit. */
! if (loop_insn_first_p (loop_start, label)
! && loop_insn_first_p (label, loop_end)
! && (simplejump_p (p)
! /* Shortcut for forward branches - by definition,
! they can't be the end of the loop */
! || loop_insn_first_p (p, label)
! || ! no_labels_between_p (p, loop_end)))
! is_loop_exit = 0;
! }
! if (is_loop_exit)
! {
! for (i = n_giv_live_after_loop -1; i >= 0; i--)
! /* We don't have recorded which givs are life after the
! loop only because their giv register is life, or
! (also) because a combined giv is life after the loop,
! so just pretend it is the latter if any other givs
! have been combined with this one. */
! note_giv_use (giv_live_after_loop[i], p,
! giv_live_after_loop[i]->combined_with,
! stats);
! }
! }
! }
! }
! }
! /* Ignore givs that are not used at all. */
! for (i = giv_count - 1; i >= 0; i--)
! {
! v = giv_array[stats[i].giv_number];
! if (v->ignore || v->same)
continue;
! if (! stats[i].start_insn)
! v->ignore = 1;
}
qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
*************** recombine_givs (bl, loop_start, loop_end
*** 7403,7419 ****
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
--- 7418,7441 ----
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. */
+
+ last_giv = 0;
+
for (i = giv_count - 1; i >= 0; i = rescan)
{
! rtx add_insn, trial_add_insn = NULL_RTX;
! for (rescan = -1; i >= 0; i--)
{
rtx sum;
v = giv_array[stats[i].giv_number];
! if (v->derived_from || v->same || v->ignore)
continue;
+
+ if (! v->new_reg)
+ v->new_reg = gen_reg_rtx (v->mode);
+
if (! last_giv)
{
/* Don't use a giv that's likely to be dead to derive
*************** recombine_givs (bl, loop_start, loop_end
*** 7426,7443 ****
}
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)
--- 7448,7475 ----
}
continue;
}
+
+ /* ??? We would save some time by setting up add_insn only
+ immediately before it is going to be used, but that would
+ make the multi-line conditional below even harder to read. */
+ if (v->giv_type == DEST_REG)
+ add_insn = v->insn;
+ else
+ {
+ if (! trial_add_insn)
+ {
+ trial_add_insn = make_insn_raw (NULL_RTX);
+ PREV_INSN (trial_add_insn) = NULL_RTX;
+ NEXT_INSN (trial_add_insn) = NULL_RTX;
+ }
+ add_insn = trial_add_insn;
+ }
+
/* 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)
&& 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)
*************** recombine_givs (bl, loop_start, loop_end
*** 7447,7475 ****
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 (VOIDmode, v->dest_reg, sum), 0))
{
v->derived_from = last_giv;
life_end = stats[i].end_luid;
if (loop_dump_stream)
{
--- 7479,7557 ----
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. */
! && (GET_CODE (stats[i].start_insn) != NOTE
! || ! v->combined_with
! /* 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->giv_type == DEST_REG
! && v->always_executed
! && ! v->leading_combined
! /* 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. */
! && ((unsigned) stats[i].end_luid - INSN_LUID (scan_start)
! > ((unsigned) stats[i].start_luid
! - INSN_LUID (scan_start)))))
&& (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. */
! && (v->giv_type != DEST_REG
! || (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 (add_insn, &PATTERN (add_insn),
! gen_rtx_SET (VOIDmode, v->new_reg, sum), 0))
{
+ struct induction *tv;
+
v->derived_from = last_giv;
life_end = stats[i].end_luid;
+ if (v->giv_type == DEST_ADDR)
+ {
+ trial_add_insn = NULL_RTX;
+ reorder_insns (add_insn, add_insn,
+ PREV_INSN (stats[i].start_insn));
+ }
+ /* Check if we want / have to move this giv. */
+ else if (v->leading_combined)
+ {
+ rtx insert_after = PREV_INSN (stats[i].start_insn);
+ rtx prev = PREV_INSN (v->insn);
+ rtx next = NEXT_INSN (v->insn);
+
+ #ifdef HAVE_cc0
+ if (GET_RTX_CLASS (GET_CODE (insert_after)) == 'i'
+ && sets_cc0_p (PATTERN (insert_after)))
+ insert_after = PREV_INSN (insert_after);
+ #endif
+ if (v->insn == insert_after
+ || prev == insert_after)
+ ; /* do nothing */
+ else if (loop_insn_first_p (v->insn, insert_after))
+ {
+ reorder_insns (v->insn, v->insn, insert_after);
+ while (INSN_UID (prev) >= max_uid_for_loop)
+ prev = PREV_INSN (prev);
+ compute_luids (next, v->insn, INSN_LUID (prev));
+ }
+ else
+ {
+ reorder_insns (v->insn, v->insn, insert_after);
+ while (INSN_UID (insert_after) >= max_uid_for_loop)
+ insert_after = PREV_INSN (insert_after);
+ compute_luids (v->insn, prev, INSN_LUID (insert_after));
+ }
+ }
if (loop_dump_stream)
{
*************** recombine_givs (bl, loop_start, loop_end
*** 7479,7488 ****
--- 7561,7617 ----
print_rtl (loop_dump_stream, sum);
putc ('\n', loop_dump_stream);
}
+
+ /* In case LAST_GIV->dest_reg is not replaceable, we have
+ to replace it in ADD_INSN now. */
+ PATTERN (add_insn)
+ = replace_rtx (PATTERN (add_insn), last_giv->dest_reg,
+ last_giv->new_reg);
+
+ /* For each place where the biv is incremented, add an
+ insn to set the new, reduced reg for the giv.
+ We used to do this only for biv_count != 1, but
+ this fails when there is a giv after a single biv
+ increment, e.g. when the last giv was expressed as
+ pre-decrement.
+ We do this here (rather than at giv derivation time) because
+ we want to copy ADD_INSN - which is not the same as V->insn
+ for DEST_ADDR givs - and to exploit the lifetime
+ information we have. */
+ for (tv = bl->biv; tv; tv = tv->next_iv)
+ {
+ /* If the biv increment precedes ADD_INSN, we can ignore it.
+ Only handle the most common case here. */
+ if (loop_insn_first_p (tv->insn, add_insn)
+ && (loop_insn_first_p (scan_start, tv->insn)
+ || loop_insn_first_p (add_insn, scan_start)))
+ continue;
+ /* Likewise if the biv increment is after the last giv use.
+ Only handle the most common case here. */
+ if (INSN_UID (tv->insn) < max_uid_for_loop
+ && stats[i].end_luid < INSN_LUID (tv->insn)
+ && INSN_LUID (scan_start) < stats[i].end_luid)
+ continue;
+
+ /* We always emit reduced giv increments before the biv
+ increment when bl->biv_count != 1. So by emitting
+ the add insns for derived givs after the biv increment,
+ they pick up the updated value of the reduced giv.
+ If the reduced giv is processed with auto_inc_opt == 1,
+ then it is incremented earlier than the biv, hence we'll
+ still pick up the right value.
+ If it's processed with auto_inc_opt == -1,
+ that implies that the biv increment is before the
+ first reduced giv's use. The derived giv's lifetime
+ is after the reduced giv's lifetime, hence in this
+ case, the biv increment doesn't matter. */
+ emit_insn_after (copy_rtx (PATTERN (add_insn)), tv->insn);
+ }
}
else if (rescan < 0)
rescan = i;
}
+ last_giv = 0;
}
}