Re: PATCH: PR target/44588: Very inefficient 8bit mod/div

["H.J. Lu" <hjl.tools@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2812 bytes --]

On Wed, Jun 23, 2010 at 4:50 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 06/24/2010 01:13 AM, H.J. Lu wrote:
>>>
>>> I don't understand exactly what the problem was; clearly it couldn't work
>>> as
>>> long as this pattern was cheating blatantly:
>>
>> Upper 8bit registers aren't real registers. You can't
>> do RA with them.
>
> Please read what other people write.  I'm saying that you should have used a
> HI destination just like you did with your new UNSPEC, which is acceptable.
>
> The pattern I quoted below used a QI destination; then magically you
> attempted to extract bit 8..15 of it with an unspec, or something like that.
>  For anything like that the optimizers are going to bite back sooner or
> later.  And you'd deserve it.
>
>>> (define_insn "*<u>divqi3"
>>>  [(set (match_operand:QI 0 "register_operand" "=a")
>>>        (any_div:QI
>>>          (match_operand:HI 1 "register_operand" "0")
>>>          (match_operand:QI 2 "nonimmediate_operand" "qm")))
>>>
>>> Anyway this patch is IMO much nicer than the first ones, so if Uros is
>>> okay
>>> I don't think it's useful to pursue a more accurate representation.  Just
>>> make sure that REG_EQUAL notes are added to the two extractions.
>>>
>>
>> What are REG_EQUAL notes used for?
>> As far as the rest of gcc is concerned, there are no upper 8bit
>> registers. But you can access bits 8-15 of HI, SI,
>> DI registers via XXX_extract.
>
> Understood.  Using an unspec is fine for me, even though it's not an
> approval.  But that's completely orthogonal to putting a REG_EQUAL note _on
> the two regs that you extract out of AX_.  The notes' value should be one of
>
>   (subreg:QI (udiv:HI (...) (zero_extend (...))))
>   (subreg:QI (div:HI (...) (sign_extend (...))))
>   (subreg:QI (umod:HI (...) (zero_extend (...))))
>   (subreg:QI (mod:HI (...) (sign_extend (...))))
>
> But I think that with over ten years of GCC experience you do not need
> anyone to tell you this.  In fact, regarding "what are REG_EQUAL notes used
> for?" my first thought was RTFM, but anyway: they are used by CSE, fwprop,
> GCSE and combine to simplify and eliminate redundant expressions.

I am learning new things all the time. Thanks for the pointer.

Here is a new patch without UNSPEC.  OK for trunk?

Thanks.

-- 
H.J.
---
gcc/

2010-06-24  H.J. Lu  <hongjiu.lu@intel.com>

	PR target/44588
	* config/i386/i386.md (extract_code): New.
	(<u>divmodqi4): Likewise.
	(divmodhiqi3): Likewise.
	(udivmodhiqi3): Likewise.
	(<u>divqi3): Remvoved.

gcc/testsuite/

2010-06-24  H.J. Lu  <hongjiu.lu@intel.com>

	PR target/44588
	* gcc.target/i386/mod-1.c: New.
	* gcc.target/i386/umod-1.c: Likewise.
	* gcc.target/i386/umod-2.c: Likewise.
	* gcc.target/i386/umod-3.c: Likewise.

[-- Attachment #2: gcc-pr44588-10.patch --]
[-- Type: text/plain, Size: 6496 bytes --]

gcc/

2010-06-24  H.J. Lu  <hongjiu.lu@intel.com>

	PR target/44588
	* config/i386/i386.md (extract_code): New.
	(<u>divmodqi4): Likewise.
	(divmodhiqi3): Likewise.
	(udivmodhiqi3): Likewise.
	(<u>divqi3): Remvoved.

gcc/testsuite/

2010-06-24  H.J. Lu  <hongjiu.lu@intel.com>

	PR target/44588
	* gcc.target/i386/mod-1.c: New.
	* gcc.target/i386/umod-1.c: Likewise.
	* gcc.target/i386/umod-2.c: Likewise.
	* gcc.target/i386/umod-3.c: Likewise.

diff --git a/gcc/config/i386/i386.md b/gcc/config/i386/i386.md
index 1f7369b..6514ee4 100644
--- a/gcc/config/i386/i386.md
+++ b/gcc/config/i386/i386.md
@@ -760,6 +760,8 @@
 
 ;; Used in signed and unsigned divisions.
 (define_code_iterator any_div [div udiv])
+(define_code_attr extract_code
+  [(div "SIGN_EXTRACT") (udiv "ZERO_EXTRACT")])
 
 ;; Instruction prefix for signed and unsigned operations.
 (define_code_attr sgnprefix [(sign_extend "i") (zero_extend "")
@@ -7269,17 +7271,6 @@
 \f
 ;; Divide instructions
 
-(define_insn "<u>divqi3"
-  [(set (match_operand:QI 0 "register_operand" "=a")
-	(any_div:QI
-	  (match_operand:HI 1 "register_operand" "0")
-	  (match_operand:QI 2 "nonimmediate_operand" "qm")))
-   (clobber (reg:CC FLAGS_REG))]
-  "TARGET_QIMODE_MATH"
-  "<sgnprefix>div{b}\t%2"
-  [(set_attr "type" "idiv")
-   (set_attr "mode" "QI")])
-
 ;; The patterns that match these are at the end of this file.
 
 (define_expand "divxf3"
@@ -7316,6 +7307,92 @@
 \f
 ;; Divmod instructions.
 
+(define_expand "<u>divmodqi4"
+  [(parallel [(set (match_operand:QI 0 "register_operand" "")
+		   (any_div:QI
+		     (match_operand:QI 1 "register_operand" "")
+		     (match_operand:QI 2 "nonimmediate_operand" "")))
+	      (set (match_operand:QI 3 "register_operand" "")
+		   (mod:QI (match_dup 1) (match_dup 2)))
+	      (clobber (reg:CC FLAGS_REG))])]
+  "TARGET_QIMODE_MATH"
+{
+  rtx div, mod, insn;
+  rtx operand0, operand1;
+  
+  operand0 = gen_reg_rtx (HImode);
+  operand1 = gen_reg_rtx (HImode);
+
+  /* Extend operands[1] to HImode.  Generate 8bit divide.  Result is
+     in AX.  */
+  if (<extract_code> == SIGN_EXTRACT)
+    {
+      emit_insn (gen_extendqihi2 (operand1, operands[1]));
+      emit_insn (gen_divmodhiqi3 (operand0, operand1, operands[2]));
+
+      div = gen_rtx_DIV (QImode, operands[1], operands[2]);
+      mod = gen_rtx_MOD (QImode, operands[1], operands[2]);
+
+      operand1 = gen_rtx_<extract_code> (QImode, operand0,
+					 GEN_INT (8), GEN_INT (8));
+    }
+  else
+    {
+      emit_insn (gen_zero_extendqihi2 (operand1, operands[1]));
+      emit_insn (gen_udivmodhiqi3 (operand0, operand1, operands[2]));
+
+      div = gen_rtx_UDIV (QImode, operands[1], operands[2]);
+      mod = gen_rtx_UMOD (QImode, operands[1], operands[2]);
+
+      operand1 = gen_rtx_<extract_code> (SImode, operand0,
+					 GEN_INT (8), GEN_INT (8));
+      operand1 = simplify_gen_subreg (QImode, operand1, SImode, 0);
+    }
+
+  /* Extract remainder from AH.  */
+  insn = emit_move_insn (operands[3], operand1);
+  set_unique_reg_note (insn, REG_EQUAL, mod);
+
+  /* Extract quotient from AL.  */
+  insn = emit_move_insn (operands[0], gen_lowpart (QImode, operand0));
+  set_unique_reg_note (insn, REG_EQUAL, div);
+
+  DONE;
+})
+
+;; Divide AX by r/m8, with result stored in
+;; AL <- Quotient
+;; AH <- Remainder
+(define_insn "divmodhiqi3"
+  [(set (match_operand:HI 0 "register_operand" "=a")
+	(ior:HI
+	  (ashift:HI
+	    (zero_extend:HI
+	      (mod:QI (match_operand:HI 1 "register_operand" "0")
+		      (match_operand:QI 2 "nonimmediate_operand" "qm")))
+	    (const_int 8))
+	  (zero_extend:HI (div:QI (match_dup 1) (match_dup 2)))))
+   (clobber (reg:CC FLAGS_REG))]
+  "TARGET_QIMODE_MATH"
+  "idiv{b}\t%2"
+  [(set_attr "type" "idiv")
+   (set_attr "mode" "QI")])
+
+(define_insn "udivmodhiqi3"
+  [(set (match_operand:HI 0 "register_operand" "=a")
+	(ior:HI
+	  (ashift:HI
+	    (zero_extend:HI
+	      (umod:QI (match_operand:HI 1 "register_operand" "0")
+		       (match_operand:QI 2 "nonimmediate_operand" "qm")))
+	    (const_int 8))
+	  (zero_extend:HI (udiv:QI (match_dup 1) (match_dup 2)))))
+   (clobber (reg:CC FLAGS_REG))]
+  "TARGET_QIMODE_MATH"
+  "div{b}\t%2"
+  [(set_attr "type" "idiv")
+   (set_attr "mode" "QI")])
+
 (define_expand "divmod<mode>4"
   [(parallel [(set (match_operand:SWIM248 0 "register_operand" "")
 		   (div:SWIM248
--- /dev/null	2010-06-16 10:11:06.602750711 -0700
+++ gcc/gcc/testsuite/gcc.target/i386/mod-1.c	2010-06-24 09:41:47.401923084 -0700
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-Os -mtune=atom" } */
+
+typedef struct {
+  int a;
+} VCR;
+
+typedef struct {
+  VCR vcr[8];
+} VCRC;
+
+typedef struct {
+  char vcr;
+} OWN;
+
+OWN Own[16];
+
+void
+f (VCRC *x, OWN *own)
+{
+  x[own->vcr / 8].vcr[own->vcr % 8].a--;
+  x[own->vcr / 8].vcr[own->vcr % 8].a = x[own->vcr / 8].vcr[own->vcr % 8].a;
+}
+
+/* { dg-final { scan-assembler-times "idivb" 1 } } */
+/* { dg-final { scan-assembler-not "incl" } } */
+/* { dg-final { scan-assembler-not "orl" } } */
+/* { dg-final { scan-assembler-not "andb" } } */
+/* { dg-final { scan-assembler-not "jns" } } */
--- /dev/null	2010-06-16 10:11:06.602750711 -0700
+++ gcc/gcc/testsuite/gcc.target/i386/umod-1.c	2010-06-21 12:01:25.705950180 -0700
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=atom" } */
+
+unsigned char
+foo (unsigned char x, unsigned char y)
+{
+  return x % y;
+}
+
+/* { dg-final { scan-assembler-times "divb" 1 } } */
+/* { dg-final { scan-assembler-not "divw" } } */
--- /dev/null	2010-06-16 10:11:06.602750711 -0700
+++ gcc/gcc/testsuite/gcc.target/i386/umod-2.c	2010-06-21 12:01:17.857932744 -0700
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=atom" } */
+
+extern unsigned char z;
+
+unsigned char
+foo (unsigned char x, unsigned char y)
+{
+  z = x/y;
+  return x % y;
+}
+
+/* { dg-final { scan-assembler-times "divb" 1 } } */
+/* { dg-final { scan-assembler-not "divw" } } */
--- /dev/null	2010-06-16 10:11:06.602750711 -0700
+++ gcc/gcc/testsuite/gcc.target/i386/umod-3.c	2010-06-21 12:02:36.809962702 -0700
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=atom" } */
+
+extern void abort (void);
+extern void exit (int);
+
+unsigned char cx = 7;
+
+int
+main ()
+{
+  unsigned char cy;
+  
+  cy = cx / 6; if (cy != 1) abort ();
+  cy = cx % 6; if (cy != 1) abort ();
+
+  exit(0);
+}
+
+/* { dg-final { scan-assembler-times "divb" 1 } } */
+/* { dg-final { scan-assembler-not "divw" } } */