infinite loop in loop.c with -O2

Chris Faylor cgf@cygnus.com
Thu Jul 15 19:15:00 GMT 1999


This patch still seems to be necessary to compile cygwin or gcc will
loop.  Is it going to be applied any time soon or is something else in
the works?

-chris

In article <199906220458.FAA04133@phal.cygnus.co.uk>,
Joern Rennecke  <amylaar@cygnus.co.uk> wrote:
>> Can you extract out just the changes necessary to deal with the fine_life_end
>> problems.
>
>It doesn't get much smaller this way, since the bulk is really replacing
>find_life_end with find_giv_uses and the associated changes in
>recombine_givs.  Well, anyways, here it goes:
>
>Tue Jun 22 05:53:44 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 can't be derived.
>
>	* 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.
>
>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/22 04:55:27
>*************** 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/22 04:55:30
>*************** 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
>*** 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))
>--- 4260,4272 ----
>  		    }
>  		}
>  
>! 	      /* 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
>*** 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.  */
>--- 4751,4757 ----
>  
>        /* 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.  */
>  
>--- 4766,4772 ----
>  	  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.  */
>  
>*************** record_giv (v, insn, src_reg, dest_reg, 
>*** 5422,5427 ****
>--- 5428,5434 ----
>    v->auto_inc_opt = 0;
>    v->unrolled = 0;
>    v->shared = 0;
>+   v->leading_combined = 0;
>    v->derived_from = 0;
>    v->last_use = 0;
>  
>*************** struct recombine_givs_stats
>*** 7066,7071 ****
>--- 7073,7081 ----
>  {
>    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;
>  {
>--- 7093,7144 ----
>    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;
>      }
>--- 7160,7235 ----
>  
>  	    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
>--- 7238,7250 ----
>    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)
>      {
>--- 7252,7269 ----
>     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;
>!   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
>--- 7274,7287 ----
>      = (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.  */
>    for (i = 0, v = bl->giv; v; v = v->next_iv)
>      {
>        rtx p;
>  
>        if (v->ignore)
>  	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 ****
>--- 7289,7295 ----
>        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);
>--- 7344,7436 ----
>  	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,7418 ****
>       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)
>  	    {
>--- 7446,7462 ----
>       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)
>      {
>!       for (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 || v->ignore)
>  	    continue;
>  	  if (! last_giv)
>  	    {
>*************** 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)
>--- 7470,7481 ----
>  		}
>  	      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)
>  	      && 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,7458 ****
>  		 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
>--- 7485,7507 ----
>  		 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.  */
>! 	      && (! 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.  */
>! 		  /* ??? If leading_combined is set and stats[i].start_insn
>! 		     is a set to a non-note insn, we could move the insn.  */ 
>! 		  || (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
>*************** recombine_givs (bl, loop_start, loop_end
>*** 7483,7488 ****
>--- 7532,7538 ----
>  	  else if (rescan < 0)
>  	    rescan = i;
>  	}
>+       last_giv = 0;
>      }
>  }
>  


-- 
cgf@cygnus.com
http://www.cygnus.com/


More information about the Gcc-patches mailing list