Re: combine_givs_p address cost

[Richard Henderson <rth at cygnus dot com>]

On Tue, Nov 24, 1998 at 11:04:35AM +1300, Michael Hayes wrote:
> In my example, combine_givs concludes that the GIV with the highest
> benefit is in the insn (25) that explicitly multiples a BIV by a
> constant.  However, this is a poor choice for GIV combination since
> this insn can usually be optimised away.

Oh, I see now.  Your problem is with those occasionally irritating
intermediate values.

Here's a possible approach.  It happens to work for your testcase;
I would be interested to find out what happens on other tests.

Toon, I'd like for you to be able to try this out as well.  I didn't
know you were still having problems with the mainline though.  I 
think Jeff has an old m68k somewhere -- I'll see about trying a build
and see if I can find the problem.



r~



Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.97
diff -c -p -d -r1.97 loop.c
*** loop.c	1998/11/21 21:14:46	1.97
--- loop.c	1998/11/24 00:00:49
*************** static int check_dbra_loop PROTO((rtx, i
*** 331,336 ****
--- 331,340 ----
  static rtx express_from_1 PROTO((rtx, rtx, rtx));
  static rtx express_from PROTO((struct induction *, struct induction *));
  static rtx combine_givs_p PROTO((struct induction *, struct induction *));
+ static int combine_givs_used_once PROTO((struct induction *,
+ 					 struct induction *));
+ static int combine_givs_benefit_from PROTO((struct induction *,
+ 					    struct induction *, rtx));
  static void combine_givs PROTO((struct iv_class *));
  static int product_cheap_p PROTO((rtx, rtx));
  static int maybe_eliminate_biv PROTO((struct iv_class *, rtx, rtx, int, int, int));
*************** combine_givs_p (g1, g2)
*** 6272,6287 ****
    if (tem != NULL_RTX
        && g2->giv_type == DEST_ADDR
        && memory_address_p (g2->mem_mode, tem)
-       /* ??? Looses, especially with -fforce-addr, where *g2->location
- 	 will always be a register, and so anything more complicated
- 	 gets discarded.  */
- #if 0
- #ifdef ADDRESS_COST
-       && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
- #else
-       && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
- #endif
- #endif
        )
      {
        return tem;
--- 6276,6281 ----
*************** combine_givs_used_once (g1, g2)
*** 6330,6345 ****
  }
   
  static int
! combine_givs_benefit_from (g1, g2)
       struct induction *g1, *g2;
  {
    int tmp = combine_givs_used_once (g1, g2);
    if (tmp < 0)
      return 0;
    else if (tmp > 0)
      return g2->benefit - g1->benefit;
!   else
!     return g2->benefit;
  }
  
  /* Check all pairs of givs for iv_class BL and see if any can be combined with
--- 6324,6360 ----
  }
   
  static int
! combine_givs_benefit_from (g1, g2, new_pattern)
       struct induction *g1, *g2;
+      rtx new_pattern;
  {
    int tmp = combine_givs_used_once (g1, g2);
    if (tmp < 0)
      return 0;
    else if (tmp > 0)
      return g2->benefit - g1->benefit;
! 
!   /* Attempt to compensate for the change to combine_givs_p that no longer
!      rejects combination possibilities based on cost.  The issue is with
!      intermediate non-address givs being combined with address givs in
!      remarkably non-optimal ways. 
! 
!      So when combining address with non-address, reduce the benefit by
!      the difference in address costs.  */
! 
!   tmp = g2->benefit;
!   if ((g1->giv_type == DEST_ADDR) != (g2->giv_type == DEST_ADDR))
!     {
! #ifdef ADDRESS_COST
!       tmp -= ADDRESS_COST (new_pattern);
!       tmp += ADDRESS_COST (*g2->location);
! #else
!       tmp -= rtx_code (new_pattern, MEM);
!       tmp += rtx_cost (*g2->location, MEM);
! #endif
!     }
! 
!   return tmp;
  }
  
  /* Check all pairs of givs for iv_class BL and see if any can be combined with
*************** combine_givs (bl)
*** 6394,6400 ****
  	      && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
  	    {
  	      can_combine[i*giv_count + j] = this_combine;
! 	      this_benefit += combine_givs_benefit_from (g1, g2);
  	      /* Add an additional weight for being reused more times.  */
  	      this_benefit += 3;
  	    }
--- 6409,6415 ----
  	      && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
  	    {
  	      can_combine[i*giv_count + j] = this_combine;
! 	      this_benefit += combine_givs_benefit_from (g1, g2, this_combine);
  	      /* Add an additional weight for being reused more times.  */
  	      this_benefit += 3;
  	    }
*************** restart:
*** 6448,6454 ****
  		g1->times_used += 1;
  	      g1->lifetime += g2->lifetime;
  
! 	      g1_add_benefit += combine_givs_benefit_from (g1, g2);
  
  	      /* ??? The new final_[bg]iv_value code does a much better job
  		 of finding replaceable giv's, and hence this code may no
--- 6463,6469 ----
  		g1->times_used += 1;
  	      g1->lifetime += g2->lifetime;
  
! 	      g1_add_benefit += combine_givs_benefit_from (g1, g2, g2->new_reg);
  
  	      /* ??? The new final_[bg]iv_value code does a much better job
  		 of finding replaceable giv's, and hence this code may no
*************** restart:
*** 6465,6471 ****
  		    {
  		      /* Remove additional weight for being reused.  */
  		      stats[l].total_benefit -= 3 + 
! 			combine_givs_benefit_from (giv_array[m], g2);
  		    }
  		}
  
--- 6480,6487 ----
  		    {
  		      /* Remove additional weight for being reused.  */
  		      stats[l].total_benefit -= 3 + 
! 			combine_givs_benefit_from (giv_array[m], g2,
! 						   can_combine[m*giv_count+j]);
  		    }
  		}
  
*************** restart:
*** 6487,6493 ****
  		{
  		  /* Remove additional weight for being reused.  */
  		  stats[j].total_benefit -= 3 + 
! 		    combine_givs_benefit_from (giv_array[m], g1);
  		}
  	    }
  
--- 6503,6510 ----
  		{
  		  /* Remove additional weight for being reused.  */
  		  stats[j].total_benefit -= 3 + 
! 		    combine_givs_benefit_from (giv_array[m], g1,
! 					       can_combine[m*giv_count + j]);
  		}
  	    }