shift_cost et al

shift_cost et al

[Richard Henderson]

What we're doing is generating some random rtl, trying to recognize it,
and if we get a match then we accept the result of rtx_cost.
The Problem is that if the target wants to generate rtl a bit different
than what we built, then we leave the cost of a shift at "infinity".

Which brings me to the object lesson:

	int foo(int x) { return x << 6; }

on a target that does not implement an SImode shift, but does implement
DImode shifts (e.g. alpha), will result in a series of 6 additions, 
never invoking the lshr_optab at all.  Similar would be true of any
target that needed clobbers to recognize the shift.

I'm of a mind to simply take the call to recog out.  If the rtx_cost
hook for the target is written well, then the shiftadd/shiftsub bits
will be handled correctly.  And the rest can be fixed.

Thoughts?


r~



Index: expmed.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expmed.c,v
retrieving revision 1.180
diff -c -p -d -r1.180 expmed.c
*** expmed.c	10 Jul 2004 08:04:56 -0000	1.180
--- expmed.c	10 Jul 2004 09:34:33 -0000
*************** init_expmed (void)
*** 196,213 ****
  	  {
  	    shift_cost[mode][m] = 32000;
  	    XEXP (SET_SRC (shift_pat), 1) = cint[m];
! 	    if (recog (shift_pat, shift_insn, &dummy) >= 0)
! 	      shift_cost[mode][m] = rtx_cost (SET_SRC (shift_pat), SET);
  
  	    shiftadd_cost[mode][m] = 32000;
  	    XEXP (XEXP (SET_SRC (shiftadd_pat), 0), 1) = pow2[m];
! 	    if (recog (shiftadd_pat, shiftadd_insn, &dummy) >= 0)
! 	      shiftadd_cost[mode][m] = rtx_cost (SET_SRC (shiftadd_pat), SET);
  
  	    shiftsub_cost[mode][m] = 32000;
  	    XEXP (XEXP (SET_SRC (shiftsub_pat), 0), 1) = pow2[m];
! 	    if (recog (shiftsub_pat, shiftsub_insn, &dummy) >= 0)
! 	      shiftsub_cost[mode][m] = rtx_cost (SET_SRC (shiftsub_pat), SET);
  	  }
      }
  
--- 196,210 ----
  	  {
  	    shift_cost[mode][m] = 32000;
  	    XEXP (SET_SRC (shift_pat), 1) = cint[m];
! 	    shift_cost[mode][m] = rtx_cost (SET_SRC (shift_pat), SET);
  
  	    shiftadd_cost[mode][m] = 32000;
  	    XEXP (XEXP (SET_SRC (shiftadd_pat), 0), 1) = pow2[m];
! 	    shiftadd_cost[mode][m] = rtx_cost (SET_SRC (shiftadd_pat), SET);
  
  	    shiftsub_cost[mode][m] = 32000;
  	    XEXP (XEXP (SET_SRC (shiftsub_pat), 0), 1) = pow2[m];
! 	    shiftsub_cost[mode][m] = rtx_cost (SET_SRC (shiftsub_pat), SET);
  	  }
      }
  

Re: shift_cost et al

[Roger Sayle]

On Sat, 10 Jul 2004, Richard Henderson wrote:
> What we're doing is generating some random rtl, trying to recognize it,
> and if we get a match then we accept the result of rtx_cost.
>
> I'm of a mind to simply take the call to recog out.  If the rtx_cost
> hook for the target is written well, then the shiftadd/shiftsub bits
> will be handled correctly.  And the rest can be fixed.
>
> Thoughts?

Sounds reasonable.  These calls to recog date back to 1993, but I think
that the quality of TARGET_RTX_COSTS have come a long way since then.

With this change, init_expmed can be cleaned up even further: there's
no need to call init_recog (unless some other code is incorrectly
relying on it), then we don't have to call emit_insn for the
shift_insn, shiftadd_insn and shiftsub_insn as its only the SHIFT/PLUS
RTX that we care about.  This avoids calls to gen_rtx_SET, extracting
patterns for shift_pat et al., and all the dinking through SET_SRC.
I think we can also get rid of start_sequence() and end_sequence().


My only worry is that we'll need to check the various rtx_costs
implementations.  Many backends incorrectly assume that they're only
ever passed "recognized" RTL, so often check for a top-level PLUS
and return true, which won't account for a shift/multiplication
operand.  These problematic backends should be easy enough to fix.

Roger
--

Re: shift_cost et al

[Richard Henderson]

On Sat, Jul 10, 2004 at 07:28:13AM -0600, Roger Sayle wrote:
> With this change, init_expmed can be cleaned up even further: there's
> no need to call init_recog (unless some other code is incorrectly
> relying on it), then we don't have to call emit_insn for the
> shift_insn, shiftadd_insn and shiftsub_insn as its only the SHIFT/PLUS
> RTX that we care about.  This avoids calls to gen_rtx_SET, extracting
> patterns for shift_pat et al., and all the dinking through SET_SRC.
> I think we can also get rid of start_sequence() and end_sequence().

Indeed.  Here's what I checked in.

Anyone care to volunteer to audit all the target rtx_cost functions?


r~


        * expmed.c (init_expmed): Use stack-local structures for
        temporary rtl.  Don't recognize shifts.

Index: expmed.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expmed.c,v
retrieving revision 1.180
diff -u -p -r1.180 expmed.c
--- expmed.c	10 Jul 2004 08:04:56 -0000	1.180
+++ expmed.c	11 Jul 2004 07:54:27 -0000
@@ -106,112 +106,144 @@ static int mul_highpart_cost[NUM_MACHINE
 void
 init_expmed (void)
 {
-  rtx reg, shift_insn, shiftadd_insn, shiftsub_insn;
-  rtx shift_pat, shiftadd_pat, shiftsub_pat;
+  struct
+  {
+    struct rtx_def reg;
+    struct rtx_def plus;	rtunion plus_fld1;
+    struct rtx_def neg;
+    struct rtx_def udiv;	rtunion udiv_fld1;
+    struct rtx_def mult;	rtunion mult_fld1;
+    struct rtx_def div;		rtunion div_fld1;
+    struct rtx_def mod;		rtunion mod_fld1;
+    struct rtx_def zext;
+    struct rtx_def wide_mult;	rtunion wide_mult_fld1;
+    struct rtx_def wide_lshr;	rtunion wide_lshr_fld1;
+    struct rtx_def wide_trunc;
+    struct rtx_def shift;	rtunion shift_fld1;
+    struct rtx_def shift_mult;	rtunion shift_mult_fld1;
+    struct rtx_def shift_add;	rtunion shift_add_fld1;
+    struct rtx_def shift_sub;	rtunion shift_sub_fld1;
+  } all;
+
   rtx pow2[MAX_BITS_PER_WORD];
   rtx cint[MAX_BITS_PER_WORD];
-  int dummy;
   int m, n;
   enum machine_mode mode, wider_mode;
 
-  start_sequence ();
-
   zero_cost = rtx_cost (const0_rtx, 0);
 
-  init_recog ();
-
   for (m = 1; m < MAX_BITS_PER_WORD; m++)
     {
       pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
       cint[m] = GEN_INT (m);
     }
 
+  memset (&all, 0, sizeof all);
+
+  PUT_CODE (&all.reg, REG);
+  REGNO (&all.reg) = 10000;
+
+  PUT_CODE (&all.plus, PLUS);
+  XEXP (&all.plus, 0) = &all.reg;
+  XEXP (&all.plus, 1) = &all.reg;
+
+  PUT_CODE (&all.neg, NEG);
+  XEXP (&all.neg, 0) = &all.reg;
+
+  PUT_CODE (&all.udiv, UDIV);
+  XEXP (&all.udiv, 0) = &all.reg;
+  XEXP (&all.udiv, 1) = &all.reg;
+
+  PUT_CODE (&all.mult, MULT);
+  XEXP (&all.mult, 0) = &all.reg;
+  XEXP (&all.mult, 1) = &all.reg;
+
+  PUT_CODE (&all.div, DIV);
+  XEXP (&all.div, 0) = &all.reg;
+  XEXP (&all.div, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32);
+
+  PUT_CODE (&all.mod, MOD);
+  XEXP (&all.mod, 0) = &all.reg;
+  XEXP (&all.mod, 1) = XEXP (&all.div, 1);
+
+  PUT_CODE (&all.zext, ZERO_EXTEND);
+  XEXP (&all.zext, 0) = &all.reg;
+
+  PUT_CODE (&all.wide_mult, MULT);
+  XEXP (&all.wide_mult, 0) = &all.zext;
+  XEXP (&all.wide_mult, 1) = &all.zext;
+
+  PUT_CODE (&all.wide_lshr, LSHIFTRT);
+  XEXP (&all.wide_lshr, 0) = &all.wide_mult;
+
+  PUT_CODE (&all.wide_trunc, TRUNCATE);
+  XEXP (&all.wide_trunc, 0) = &all.wide_lshr;
+
+  PUT_CODE (&all.shift, ASHIFT);
+  XEXP (&all.shift, 0) = &all.reg;
+
+  PUT_CODE (&all.shift_mult, MULT);
+  XEXP (&all.shift_mult, 0) = &all.reg;
+
+  PUT_CODE (&all.shift_add, PLUS);
+  XEXP (&all.shift_add, 0) = &all.shift_mult;
+  XEXP (&all.shift_add, 1) = &all.reg;
+
+  PUT_CODE (&all.shift_sub, MINUS);
+  XEXP (&all.shift_sub, 0) = &all.shift_mult;
+  XEXP (&all.shift_sub, 1) = &all.reg;
+
   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
        mode != VOIDmode;
        mode = GET_MODE_WIDER_MODE (mode))
     {
-      reg = gen_rtx_REG (mode, 10000);
-      add_cost[mode] = rtx_cost (gen_rtx_PLUS (mode, reg, reg), SET);
-      neg_cost[mode] = rtx_cost (gen_rtx_NEG (mode, reg), SET);
-      div_cost[mode] = rtx_cost (gen_rtx_UDIV (mode, reg, reg), SET);
-      mul_cost[mode] = rtx_cost (gen_rtx_MULT (mode, reg, reg), SET);
-
-      sdiv_pow2_cheap[mode]
-	= (rtx_cost (gen_rtx_DIV (mode, reg, GEN_INT (32)), SET)
-	   <= 2 * add_cost[mode]);
-      smod_pow2_cheap[mode]
-	= (rtx_cost (gen_rtx_MOD (mode, reg, GEN_INT (32)), SET)
-	   <= 2 * add_cost[mode]);
+      PUT_MODE (&all.reg, mode);
+      PUT_MODE (&all.plus, mode);
+      PUT_MODE (&all.neg, mode);
+      PUT_MODE (&all.udiv, mode);
+      PUT_MODE (&all.mult, mode);
+      PUT_MODE (&all.div, mode);
+      PUT_MODE (&all.mod, mode);
+      PUT_MODE (&all.wide_trunc, mode);
+      PUT_MODE (&all.shift, mode);
+      PUT_MODE (&all.shift_mult, mode);
+      PUT_MODE (&all.shift_add, mode);
+      PUT_MODE (&all.shift_sub, mode);
+
+      add_cost[mode] = rtx_cost (&all.plus, SET);
+      neg_cost[mode] = rtx_cost (&all.neg, SET);
+      div_cost[mode] = rtx_cost (&all.udiv, SET);
+      mul_cost[mode] = rtx_cost (&all.mult, SET);
+
+      sdiv_pow2_cheap[mode] = (rtx_cost (&all.div, SET) <= 2 * add_cost[mode]);
+      smod_pow2_cheap[mode] = (rtx_cost (&all.mod, SET) <= 2 * add_cost[mode]);
 
       wider_mode = GET_MODE_WIDER_MODE (mode);
       if (wider_mode != VOIDmode)
 	{
-	  mul_widen_cost[wider_mode]
-	    = rtx_cost (gen_rtx_MULT (wider_mode,
-				      gen_rtx_ZERO_EXTEND (wider_mode, reg),
-				      gen_rtx_ZERO_EXTEND (wider_mode, reg)),
-			SET);
-	  mul_highpart_cost[mode]
-	    = rtx_cost (gen_rtx_TRUNCATE
-			(mode,
-			 gen_rtx_LSHIFTRT (wider_mode,
-					   gen_rtx_MULT (wider_mode,
-							 gen_rtx_ZERO_EXTEND
-							 (wider_mode, reg),
-							 gen_rtx_ZERO_EXTEND
-							 (wider_mode, reg)),
-					   GEN_INT (GET_MODE_BITSIZE (mode)))),
-			SET);
-	}
-
-	shift_insn = emit_insn (gen_rtx_SET (VOIDmode, reg,
-					     gen_rtx_ASHIFT (mode, reg,
-							     const0_rtx)));
-
-	shiftadd_insn
-	  = emit_insn (gen_rtx_SET (VOIDmode, reg,
-				    gen_rtx_PLUS (mode,
-						  gen_rtx_MULT (mode,
-								reg,
-								const0_rtx),
-						  reg)));
-
-	shiftsub_insn
-	  = emit_insn (gen_rtx_SET (VOIDmode, reg,
-				    gen_rtx_MINUS (mode,
-						   gen_rtx_MULT (mode,
-								 reg,
-								 const0_rtx),
-						   reg)));
-
-	shift_pat = PATTERN (shift_insn);
-	shiftadd_pat = PATTERN (shiftadd_insn);
-	shiftsub_pat = PATTERN (shiftsub_insn);
+	  PUT_MODE (&all.zext, wider_mode);
+	  PUT_MODE (&all.wide_mult, wider_mode);
+	  PUT_MODE (&all.wide_lshr, wider_mode);
+	  XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode));
+
+	  mul_widen_cost[wider_mode] = rtx_cost (&all.wide_mult, SET);
+	  mul_highpart_cost[mode] = rtx_cost (&all.wide_trunc, SET);
+	}
 
-	shift_cost[mode][0] = 0;
-	shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode];
+      shift_cost[mode][0] = 0;
+      shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode];
 
-	n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode));
-	for (m = 1; m < n; m++)
-	  {
-	    shift_cost[mode][m] = 32000;
-	    XEXP (SET_SRC (shift_pat), 1) = cint[m];
-	    if (recog (shift_pat, shift_insn, &dummy) >= 0)
-	      shift_cost[mode][m] = rtx_cost (SET_SRC (shift_pat), SET);
-
-	    shiftadd_cost[mode][m] = 32000;
-	    XEXP (XEXP (SET_SRC (shiftadd_pat), 0), 1) = pow2[m];
-	    if (recog (shiftadd_pat, shiftadd_insn, &dummy) >= 0)
-	      shiftadd_cost[mode][m] = rtx_cost (SET_SRC (shiftadd_pat), SET);
-
-	    shiftsub_cost[mode][m] = 32000;
-	    XEXP (XEXP (SET_SRC (shiftsub_pat), 0), 1) = pow2[m];
-	    if (recog (shiftsub_pat, shiftsub_insn, &dummy) >= 0)
-	      shiftsub_cost[mode][m] = rtx_cost (SET_SRC (shiftsub_pat), SET);
-	  }
-    }
+      n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode));
+      for (m = 1; m < n; m++)
+	{
+	  XEXP (&all.shift, 1) = cint[m];
+	  XEXP (&all.shift_mult, 1) = pow2[m];
 
-  end_sequence ();
+	  shift_cost[mode][m] = rtx_cost (&all.shift, SET);
+	  shiftadd_cost[mode][m] = rtx_cost (&all.shift_add, SET);
+	  shiftsub_cost[mode][m] = rtx_cost (&all.shift_sub, SET);
+	}
+    }
 }
 
 /* Return an rtx representing minus the value of X.

[PATCH] Fix shift-and-add costs in rs6000_rtx_costs

[Roger Sayle]

On Sun, 11 Jul 2004, Richard Henderson wrote:
> Anyone care to volunteer to audit all the target rtx_cost functions?

The following patch tweaks the rs6000's TARGET_RTX_COST function to
indicate that it doesn't have shift-and-add or shift-and-sub insns.
The middle-end's expmed_init calls rtx_cost on the RTL pattern
(plus (mult (reg) (const_int)) (reg)), to determine whether the backend
has shift-and-add or shift-and-sub instructions that can be used to
efficiently implement synthetic multiply.  Historically, the rs6000
backend would always return COSTS_N_INSNS(1) for any expression containing
a PLUS at the top-level, which hides the fact that the rs6000 doesn't
have these instructions (as far as I know!).

The correct longer term fix is probably to transition rs6000_rtx_costs
to return false more often, to account for the costs of subexpressions
and operands.  The problem is that such a (BURG-like?) top-down tree
matcher requires knowledge of all of a backends patterns, for example
(ior (not X) (not Y)) if an architecture has a "nand" instruction, to
correctly determine how many ply can be implemented by a single pattern.
Alas Rome wasn't built in a day.

The fix (workaround) below operates the opposite way.  Rather than bring
forward the timeline for teaching rs6000_rtx_costs about all of its
instruction patterns, we instead intercept the middle-end "probes"
that we know aren't valid instructions.  This should avoid any immediate
performance degradation, and allow rs6000_rtx_costs to continue to
evolve at its own rate.


The following patch has been tested on powerpc-apple-darwin7.4.0 with
a full "make bootstrap", all default languages, and regression tested
with a top-level "make -k check" with no new failures.

Ok for mainline?


2004-07-11  Roger Sayle  <roger@eyesopen.com>

	* config/rs6000/rs6000.c (rs6000_rtx_costs): Indicate that the
	rs6000 doesn't have shift-and-add or shift-and-sub instructions
	by returning a cost of a multiplication plus an addition.


Index: config/rs6000/rs6000.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/rs6000/rs6000.c,v
retrieving revision 1.663
diff -c -3 -p -r1.663 rs6000.c
*** config/rs6000/rs6000.c	11 Jul 2004 14:32:49 -0000	1.663
--- config/rs6000/rs6000.c	11 Jul 2004 20:11:55 -0000
*************** rs6000_rtx_costs (rtx x, int code, int o
*** 16535,16540 ****
--- 16535,16546 ----
  		 : rs6000_cost->fp;
        else if (mode == SFmode)
  	*total = rs6000_cost->fp;
+       else if (GET_CODE (XEXP (x, 0)) == MULT)
+ 	{
+ 	  /* The rs6000 doesn't have shift-and-add instructions.  */
+ 	  rs6000_rtx_costs (XEXP (x, 0), MULT, PLUS, total);
+ 	  *total += COSTS_N_INSNS (1);
+ 	}
        else
  	*total = ((GET_CODE (XEXP (x, 1)) == CONST_INT
  		  && ((unsigned HOST_WIDE_INT) (INTVAL (XEXP (x, 1))
*************** rs6000_rtx_costs (rtx x, int code, int o
*** 16551,16556 ****
--- 16557,16568 ----
  		 : rs6000_cost->fp;
        else if (mode == SFmode)
  	*total = rs6000_cost->fp;
+       else if (GET_CODE (XEXP (x, 0)) == MULT)
+ 	{
+ 	  /* The rs6000 doesn't have shift-and-sub instructions.  */
+ 	  rs6000_rtx_costs (XEXP (x, 0), MULT, MINUS, total);
+ 	  *total += COSTS_N_INSNS (1);
+ 	}
        else
          *total = COSTS_N_INSNS (1);
        return true;


Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833

Re: [PATCH] Fix shift-and-add costs in rs6000_rtx_costs

[David Edelsohn]

>>>>> Roger Sayle writes:

> The following patch tweaks the rs6000's TARGET_RTX_COST function to
> indicate that it doesn't have shift-and-add or shift-and-sub insns.
> The middle-end's expmed_init calls rtx_cost on the RTL pattern
> (plus (mult (reg) (const_int)) (reg)), to determine whether the backend
> has shift-and-add or shift-and-sub instructions that can be used to
> efficiently implement synthetic multiply.

	Is this change going to disable shift-and-add for all multiplies?
We do want to use shift-and-add where the cost for the two instructions is
less than the cost of a multiply.

David

Re: [PATCH] Fix shift-and-add costs in rs6000_rtx_costs

[Roger Sayle]

On Sun, 11 Jul 2004, David Edelsohn wrote:
> >>>>> Roger Sayle writes:
> > The following patch tweaks the rs6000's TARGET_RTX_COST function to
> > indicate that it doesn't have shift-and-add or shift-and-sub insns.
> > The middle-end's expmed_init calls rtx_cost on the RTL pattern
> > (plus (mult (reg) (const_int)) (reg)), to determine whether the backend
> > has shift-and-add or shift-and-sub instructions that can be used to
> > efficiently implement synthetic multiply.
>
> 	Is this change going to disable shift-and-add for all multiplies?
> We do want to use shift-and-add where the cost for the two instructions
> is less than the cost of a multiply.

No, we'll still generate individual shifts and adds, we're just trying
to disable the middle-end thinking it has an extremely cheap single-cycle
shift-and-add instruction.  The relevant code in expmed.c is:

>>         cost = add_cost[mode] + shift_cost[mode][m];
>>         if (shiftadd_cost[mode][m] < cost)
>>           cost = shiftadd_cost[mode][m];

On most PPC targets add_cost and shift_cost are each COSTS_N_INSNS(1).
The problem is that we currently also return COSTS_N_INSNS(1) for a
mythical "lea"-like instruction, so synth_mult underestimates the cost
of a shift followed by an addition.

For this patch, it isn't important that the multiplication subexpressions
are powers of two and can therefore be implemented by a single cycle shift.
All that's required is that the value must be at least COSTS_N_INSNS(2).

Roger
--

Re: [PATCH] Fix shift-and-add costs in rs6000_rtx_costs

[David Edelsohn]

	Okay, go ahead with the patch.

David