[MSP430,4/4] Implement 64-bit shifts in assembly code

Message ID 20190604141750.42210082@jozef-kubuntu
State New
Headers show
Series
  • Reduce code size when performing bit shifts
Related show

Commit Message

Jozef Lawrynowicz June 4, 2019, 1:17 p.m.
This patch implements 64-bit shifts in assembly code. Previously, generic C
library code from libgcc would be used to perform the shifts, which was much
more costly in terms of code size.

I observed 700 PASS->FAIL regressions from the GCC testsuite alone when these
64-bit shifts were implemented incorrectly, hence I've assumed there is
already adequate test coverage that shifts operate correctly, and I have not
added new tests to verify their correct execution.

For the following program, the below code size reduction is observed:
  long long a;

  int
  main (void)
  {
    a = a >> 4;
    return 0;
  }

With shift patch 3:
   text    data     bss     dec     hex filename
    670      12      26     708     2c4 a.out
With new patch:
   text    data     bss     dec     hex filename
    512      12      26     550     226 a.out

Ok for trunk?

Comments

Jeff Law June 5, 2019, 10:35 p.m. | #1
On 6/4/19 7:17 AM, Jozef Lawrynowicz wrote:
> This patch implements 64-bit shifts in assembly code. Previously, generic C

> library code from libgcc would be used to perform the shifts, which was much

> more costly in terms of code size.

> 

> I observed 700 PASS->FAIL regressions from the GCC testsuite alone when these

> 64-bit shifts were implemented incorrectly, hence I've assumed there is

> already adequate test coverage that shifts operate correctly, and I have not

> added new tests to verify their correct execution.

> 

> For the following program, the below code size reduction is observed:

>   long long a;

> 

>   int

>   main (void)

>   {

>     a = a >> 4;

>     return 0;

>   }

> 

> With shift patch 3:

>    text    data     bss     dec     hex filename

>     670      12      26     708     2c4 a.out

> With new patch:

>    text    data     bss     dec     hex filename

>     512      12      26     550     226 a.out

> 

> Ok for trunk?

> 

> 

> 0004-MSP430-Implement-64-bit-shifts-in-assembly-code.patch

> 

> From 3b34b3d005ea63b37cf6a277395a048e55d854b2 Mon Sep 17 00:00:00 2001

> From: Jozef Lawrynowicz <jozef.l@mittosystems.com>

> Date: Mon, 13 May 2019 17:55:27 +0100

> Subject: [PATCH 4/4] MSP430: Implement 64-bit shifts in assembly code

> 

> gcc/ChangeLog

> 

> 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

> 

> 	* config/msp430/msp430.c (msp430_expand_helper): Setup arguments which

> 	describe how to perform MSPABI compliant 64-bit shift.

> 	* config/msp430/msp430.md (ashldi3): New define_expand.

> 	(ashrdi3): New define_expand.

> 	(lshrdi3): New define_expand.

> 

> libgcc/ChangeLog

> 

> 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

> 

> 	* config/msp430/slli.S (__mspabi_sllll): New library function for

> 	performing a logical left shift of a 64-bit value.

> 	(__mspabi_srall): New library function for

> 	performing a arithmetic right shift of a 64-bit value.

> 	(__mspabi_srlll): New library function for

> 	performing a logical right shift of a 64-bit value.

> 

> gcc/testsuite/ChangeLog

> 

> 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

> 

> 	* gcc.target/msp430/mspabi_sllll.c: New test.

> 	* gcc.target/msp430/mspabi_srall.c: New test.

> 	* gcc.target/msp430/mspabi_srlll.c: New test.

Going to assume your assembly routines are correct :-)

OK
jeff
Jozef Lawrynowicz June 6, 2019, 12:42 p.m. | #2
On Wed, 5 Jun 2019 16:35:14 -0600
Jeff Law <law@redhat.com> wrote:

> On 6/4/19 7:17 AM, Jozef Lawrynowicz wrote:

> > libgcc/ChangeLog

> > 

> > 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

> > 

> > 	* config/msp430/slli.S (__mspabi_sllll): New library function for

> > 	performing a logical left shift of a 64-bit value.

> > 	(__mspabi_srall): New library function for

> > 	performing a arithmetic right shift of a 64-bit value.

> > 	(__mspabi_srlll): New library function for

> > 	performing a logical right shift of a 64-bit value.

> > 

> Going to assume your assembly routines are correct :-)

> 

> OK

> jeff


I assume I implemented them correctly based on the clean regtest of
GCC/G++ testsuites. But in case there might be a gap in the coverage
somewhere, how about the attached new torture test to explicitly check 64-bit
shifts work as expected?
Passes for x86_64-linux-gnu and msp430-elf.

Thanks for the reviews.
Jozef
diff --git a/gcc/testsuite/gcc.c-torture/execute/shiftdi-2.c b/gcc/testsuite/gcc.c-torture/execute/shiftdi-2.c
new file mode 100644
index 00000000000..63d1fe90830
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/shiftdi-2.c
@@ -0,0 +1,23 @@
+__INT64_TYPE__ a = 568513516876543756;
+__INT64_TYPE__ b = -754324895235774564;
+__UINT64_TYPE__ c = 156789543257562457;
+
+__INT64_TYPE__ expected_a[64] = {568513516876543756, 1137027033753087512, 2274054067506175024, 4548108135012350048, 9096216270024700096, -254311533660151424, -508623067320302848, -1017246134640605696, -2034492269281211392, -4068984538562422784, -8137969077124845568, 2170805919459860480, 4341611838919720960, 8683223677839441920, -1080296718030667776, -2160593436061335552, -4321186872122671104, -8642373744245342208, 1161996585218867200, 2323993170437734400, 4647986340875468800, -9150771391958614016, 145201289792323584, 290402579584647168, 580805159169294336, 1161610318338588672, 2323220636677177344, 4646441273354354688, -9153861527000842240, 139021019707867136, 278042039415734272, 556084078831468544, 1112168157662937088, 2224336315325874176, 4448672630651748352, 8897345261303496704, -652053551102558208, -1304107102205116416, -2608214204410232832, -5216428408820465664, 8013887256068620288, -2418969561572311040, -4837939123144622080, 8770865827420307456, -905012418868936704, -1810024837737873408, -3620049675475746816, -7240099350951493632, 3966545371806564352, 7933090743613128704, -2580562586483294208, -5161125172966588416, 8124493727776374784, -2197756618156802048, -4395513236313604096, -8791026472627208192, 864691128455135232, 1729382256910270464, 3458764513820540928, 6917529027641081856, -4611686018427387904, -9223372036854775808ULL, 0, 0};
+__INT64_TYPE__ expected_b[64] = {-754324895235774564, -377162447617887282, -188581223808943641, -94290611904471821, -47145305952235911, -23572652976117956, -11786326488058978, -5893163244029489, -2946581622014745, -1473290811007373, -736645405503687, -368322702751844, -184161351375922, -92080675687961, -46040337843981, -23020168921991, -11510084460996, -5755042230498, -2877521115249, -1438760557625, -719380278813, -359690139407, -179845069704, -89922534852, -44961267426, -22480633713, -11240316857, -5620158429, -2810079215, -1405039608, -702519804, -351259902, -175629951, -87814976, -43907488, -21953744, -10976872, -5488436, -2744218, -1372109, -686055, -343028, -171514, -85757, -42879, -21440, -10720, -5360, -2680, -1340, -670, -335, -168, -84, -42, -21, -11, -6, -3, -2, -1, -1, -1, -1};
+__UINT64_TYPE__ expected_c[64] = {156789543257562457, 78394771628781228, 39197385814390614, 19598692907195307, 9799346453597653, 4899673226798826, 2449836613399413, 1224918306699706, 612459153349853, 306229576674926, 153114788337463, 76557394168731, 38278697084365, 19139348542182, 9569674271091, 4784837135545, 2392418567772, 1196209283886, 598104641943, 299052320971, 149526160485, 74763080242, 37381540121, 18690770060, 9345385030, 4672692515, 2336346257, 1168173128, 584086564, 292043282, 146021641, 73010820, 36505410, 18252705, 9126352, 4563176, 2281588, 1140794, 570397, 285198, 142599, 71299, 35649, 17824, 8912, 4456, 2228, 1114, 557, 278, 139, 69, 34, 17, 8, 4, 2, 1, 0, 0, 0, 0, 0, 0};
+
+int
+main (void)
+{
+  int i;
+  for (i = 0; i < 64; i++)
+  {
+    if ((a << i) != expected_a[i])
+      __builtin_abort ();
+    else if ((b >> i) != expected_b[i])
+      __builtin_abort ();
+    else if ((c >> i) != expected_c[i])
+      __builtin_abort ();
+  }
+  return 0;
+}
Jeff Law June 6, 2019, 5:32 p.m. | #3
On 6/6/19 6:42 AM, Jozef Lawrynowicz wrote:
> On Wed, 5 Jun 2019 16:35:14 -0600

> Jeff Law <law@redhat.com> wrote:

> 

>> On 6/4/19 7:17 AM, Jozef Lawrynowicz wrote:

>>> libgcc/ChangeLog

>>>

>>> 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

>>>

>>> 	* config/msp430/slli.S (__mspabi_sllll): New library function for

>>> 	performing a logical left shift of a 64-bit value.

>>> 	(__mspabi_srall): New library function for

>>> 	performing a arithmetic right shift of a 64-bit value.

>>> 	(__mspabi_srlll): New library function for

>>> 	performing a logical right shift of a 64-bit value.

>>>

>> Going to assume your assembly routines are correct :-)

>>

>> OK

>> jeff

> I assume I implemented them correctly based on the clean regtest of

> GCC/G++ testsuites. But in case there might be a gap in the coverage

> somewhere, how about the attached new torture test to explicitly check 64-bit

> shifts work as expected?

> Passes for x86_64-linux-gnu and msp430-elf.

I suspect this needs to be conditional on 64bit integer support (check
either at runtime with sizeof or via dejagnu effective target stuff).
With that fixed this is OK.

jeff
Jozef Lawrynowicz June 16, 2019, 9:42 p.m. | #4
On Thu, 6 Jun 2019 11:32:49 -0600
Jeff Law <law@redhat.com> wrote:

> On 6/6/19 6:42 AM, Jozef Lawrynowicz wrote:

> > On Wed, 5 Jun 2019 16:35:14 -0600

> > Jeff Law <law@redhat.com> wrote:

> >   

> >> On 6/4/19 7:17 AM, Jozef Lawrynowicz wrote:  

> >>> libgcc/ChangeLog

> >>>

> >>> 2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

> >>>

> >>> 	* config/msp430/slli.S (__mspabi_sllll): New library function for

> >>> 	performing a logical left shift of a 64-bit value.

> >>> 	(__mspabi_srall): New library function for

> >>> 	performing a arithmetic right shift of a 64-bit value.

> >>> 	(__mspabi_srlll): New library function for

> >>> 	performing a logical right shift of a 64-bit value.

> >>>  

> >> Going to assume your assembly routines are correct :-)

> >>

> >> OK

> >> jeff  

> > I assume I implemented them correctly based on the clean regtest of

> > GCC/G++ testsuites. But in case there might be a gap in the coverage

> > somewhere, how about the attached new torture test to explicitly check 64-bit

> > shifts work as expected?

> > Passes for x86_64-linux-gnu and msp430-elf.  

> I suspect this needs to be conditional on 64bit integer support (check

> either at runtime with sizeof or via dejagnu effective target stuff).

> With that fixed this is OK.

> 

> jeff


Since it seems that the use of long long when a 64-bit type is required is much
more prevalent in the testsuite that __INT64_TYPE__ (which may not be supported
on all systems), I changed the types to use long long, and made the test
require the longlong64 effective target keyword. Committed.

Thanks,
Jozef

Patch

From 3b34b3d005ea63b37cf6a277395a048e55d854b2 Mon Sep 17 00:00:00 2001
From: Jozef Lawrynowicz <jozef.l@mittosystems.com>
Date: Mon, 13 May 2019 17:55:27 +0100
Subject: [PATCH 4/4] MSP430: Implement 64-bit shifts in assembly code

gcc/ChangeLog

2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

	* config/msp430/msp430.c (msp430_expand_helper): Setup arguments which
	describe how to perform MSPABI compliant 64-bit shift.
	* config/msp430/msp430.md (ashldi3): New define_expand.
	(ashrdi3): New define_expand.
	(lshrdi3): New define_expand.

libgcc/ChangeLog

2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

	* config/msp430/slli.S (__mspabi_sllll): New library function for
	performing a logical left shift of a 64-bit value.
	(__mspabi_srall): New library function for
	performing a arithmetic right shift of a 64-bit value.
	(__mspabi_srlll): New library function for
	performing a logical right shift of a 64-bit value.

gcc/testsuite/ChangeLog

2019-06-04  Jozef Lawrynowicz  <jozef.l@mittosystems.com>

	* gcc.target/msp430/mspabi_sllll.c: New test.
	* gcc.target/msp430/mspabi_srall.c: New test.
	* gcc.target/msp430/mspabi_srlll.c: New test.
---
 gcc/config/msp430/msp430.c                    | 13 +++++--
 gcc/config/msp430/msp430.md                   | 36 +++++++++++++++++++
 .../gcc.target/msp430/mspabi_sllll.c          | 10 ++++++
 .../gcc.target/msp430/mspabi_srall.c          | 10 ++++++
 .../gcc.target/msp430/mspabi_srlll.c          | 10 ++++++
 libgcc/config/msp430/slli.S                   | 33 +++++++++++++++++
 libgcc/config/msp430/srai.S                   | 34 ++++++++++++++++++
 libgcc/config/msp430/srli.S                   | 35 ++++++++++++++++++
 8 files changed, 179 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/msp430/mspabi_sllll.c
 create mode 100644 gcc/testsuite/gcc.target/msp430/mspabi_srall.c
 create mode 100644 gcc/testsuite/gcc.target/msp430/mspabi_srlll.c

diff --git a/gcc/config/msp430/msp430.c b/gcc/config/msp430/msp430.c
index 020e980b8cc..365e9eba747 100644
--- a/gcc/config/msp430/msp430.c
+++ b/gcc/config/msp430/msp430.c
@@ -3046,6 +3046,7 @@  msp430_expand_helper (rtx *operands, const char *helper_name, bool const_variant
 {
   rtx c, f;
   char *helper_const = NULL;
+  int arg1 = 12;
   int arg2 = 13;
   int arg1sz = 1;
   machine_mode arg0mode = GET_MODE (operands[0]);
@@ -3079,6 +3080,13 @@  msp430_expand_helper (rtx *operands, const char *helper_name, bool const_variant
       arg2 = 14;
       arg1sz = 2;
     }
+  else if (arg1mode == DImode)
+    {
+      /* Shift value in R8:R11, shift amount in R12.  */
+      arg1 = 8;
+      arg1sz = 4;
+      arg2 = 12;
+    }
 
   if (const_variants
       && CONST_INT_P (operands[2])
@@ -3091,7 +3099,7 @@  msp430_expand_helper (rtx *operands, const char *helper_name, bool const_variant
       snprintf (helper_const, len, "%s_%d", helper_name, (int) INTVAL (operands[2]));
     }
 
-  emit_move_insn (gen_rtx_REG (arg1mode, 12),
+  emit_move_insn (gen_rtx_REG (arg1mode, arg1),
 		  operands[1]);
   if (!helper_const)
     emit_move_insn (gen_rtx_REG (arg2mode, arg2),
@@ -3104,12 +3112,13 @@  msp430_expand_helper (rtx *operands, const char *helper_name, bool const_variant
   RTL_CONST_CALL_P (c) = 1;
 
   f = 0;
-  use_regs (&f, 12, arg1sz);
+  use_regs (&f, arg1, arg1sz);
   if (!helper_const)
     use_regs (&f, arg2, 1);
   add_function_usage_to (c, f);
 
   emit_move_insn (operands[0],
+		  /* Return value will always start in R12.  */
 		  gen_rtx_REG (arg0mode, 12));
 }
 
diff --git a/gcc/config/msp430/msp430.md b/gcc/config/msp430/msp430.md
index 76296a2f317..f6d688950cb 100644
--- a/gcc/config/msp430/msp430.md
+++ b/gcc/config/msp430/msp430.md
@@ -822,6 +822,18 @@ 
    DONE;"
 )
 
+(define_expand "ashldi3"
+  [(set (match_operand:DI	     0 "nonimmediate_operand")
+	(ashift:DI (match_operand:DI 1 "general_operand")
+		   (match_operand:DI 2 "general_operand")))]
+  ""
+  {
+    /* No const_variant for 64-bit shifts.  */
+    msp430_expand_helper (operands, \"__mspabi_sllll\", false);
+    DONE;
+  }
+)
+
 ;;----------
 
 ;; signed A >> C
@@ -911,6 +923,18 @@ 
    DONE;"
 )
 
+(define_expand "ashrdi3"
+  [(set (match_operand:DI	     0 "nonimmediate_operand")
+	(ashift:DI (match_operand:DI 1 "general_operand")
+		   (match_operand:DI 2 "general_operand")))]
+  ""
+  {
+    /* No const_variant for 64-bit shifts.  */
+    msp430_expand_helper (operands, \"__mspabi_srall\", false);
+    DONE;
+  }
+)
+
 ;;----------
 
 ;; unsigned A >> C
@@ -990,6 +1014,18 @@ 
    DONE;"
 )
 
+(define_expand "lshrdi3"
+  [(set (match_operand:DI	     0 "nonimmediate_operand")
+	(ashift:DI (match_operand:DI 1 "general_operand")
+		   (match_operand:DI 2 "general_operand")))]
+  ""
+  {
+    /* No const_variant for 64-bit shifts.  */
+    msp430_expand_helper (operands, \"__mspabi_srlll\", false);
+    DONE;
+  }
+)
+
 ;;------------------------------------------------------------
 ;; Function Entry/Exit
 
diff --git a/gcc/testsuite/gcc.target/msp430/mspabi_sllll.c b/gcc/testsuite/gcc.target/msp430/mspabi_sllll.c
new file mode 100644
index 00000000000..b88a8be73ff
--- /dev/null
+++ b/gcc/testsuite/gcc.target/msp430/mspabi_sllll.c
@@ -0,0 +1,10 @@ 
+/* { dg-do compile } */
+/* { dg-final { scan-assembler-not "ashldi3" } } */
+/* { dg-final { scan-assembler "__mspabi_sllll" } } */
+
+long long
+foo (long long a)
+{
+  return a << 4;
+}
+
diff --git a/gcc/testsuite/gcc.target/msp430/mspabi_srall.c b/gcc/testsuite/gcc.target/msp430/mspabi_srall.c
new file mode 100644
index 00000000000..a0aba3d43d7
--- /dev/null
+++ b/gcc/testsuite/gcc.target/msp430/mspabi_srall.c
@@ -0,0 +1,10 @@ 
+/* { dg-do compile } */
+/* { dg-final { scan-assembler-not "ashrdi3" } } */
+/* { dg-final { scan-assembler "__mspabi_srall" } } */
+
+long long
+foo (long long a)
+{
+  return a >> 4;
+}
+
diff --git a/gcc/testsuite/gcc.target/msp430/mspabi_srlll.c b/gcc/testsuite/gcc.target/msp430/mspabi_srlll.c
new file mode 100644
index 00000000000..cb9a3744b77
--- /dev/null
+++ b/gcc/testsuite/gcc.target/msp430/mspabi_srlll.c
@@ -0,0 +1,10 @@ 
+/* { dg-do compile } */
+/* { dg-final { scan-assembler-not "lshrdi3" } } */
+/* { dg-final { scan-assembler "__mspabi_srlll" } } */
+
+unsigned long long
+foo (unsigned long long a)
+{
+  return a >> 4;
+}
+
diff --git a/libgcc/config/msp430/slli.S b/libgcc/config/msp430/slli.S
index 89ca35a9304..9210fe6e934 100644
--- a/libgcc/config/msp430/slli.S
+++ b/libgcc/config/msp430/slli.S
@@ -110,3 +110,36 @@  __mspabi_slll:
 	RET
 #endif
 
+/* Logical Left Shift - R8:R11 -> R12:R15
+   A 64-bit argument would normally be passed in R12:R15, but __mspabi_sllll has
+   special conventions, so the 64-bit value to shift is passed in R8:R11.
+   According to the MSPABI, the shift amount is a 64-bit value in R12:R15, but
+   we only use the low word in R12.  */
+
+	.section	.text.__mspabi_sllll
+	.global __mspabi_sllll
+__mspabi_sllll:
+	MOV R11, R15 ; Free up R11 first
+	MOV R12, R11 ; Save the shift amount in R11
+	MOV R10, R14
+	MOV R9, R13
+	MOV R8, R12
+	CMP #0,R11
+	JNZ 1f
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
+1:
+	RLA R12
+	RLC R13
+	RLC R14
+	RLC R15
+	ADD #-1,R11
+	JNZ 1b
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
diff --git a/libgcc/config/msp430/srai.S b/libgcc/config/msp430/srai.S
index 564f7989a8c..ed5c6a5ad7c 100644
--- a/libgcc/config/msp430/srai.S
+++ b/libgcc/config/msp430/srai.S
@@ -108,3 +108,37 @@  __mspabi_sral:
 #else
 	RET
 #endif
+
+/* Arithmetic Right Shift - R8:R11 -> R12:R15
+   A 64-bit argument would normally be passed in R12:R15, but __mspabi_srall has
+   special conventions, so the 64-bit value to shift is passed in R8:R11.
+   According to the MSPABI, the shift amount is a 64-bit value in R12:R15, but
+   we only use the low word in R12.  */
+
+	.section	.text.__mspabi_srall
+	.global __mspabi_srall
+__mspabi_srall:
+	MOV R11, R15 ; Free up R11 first
+	MOV R12, R11 ; Save the shift amount in R11
+	MOV R10, R14
+	MOV R9, R13
+	MOV R8, R12
+	CMP #0, R11
+	JNZ 1f
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
+1:
+	RRA R15
+	RRC R14
+	RRC R13
+	RRC R12
+	ADD #-1,R11
+	JNZ 1b
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
diff --git a/libgcc/config/msp430/srli.S b/libgcc/config/msp430/srli.S
index 4dd32ea4002..bc1b034e4b9 100644
--- a/libgcc/config/msp430/srli.S
+++ b/libgcc/config/msp430/srli.S
@@ -112,3 +112,38 @@  __mspabi_srll:
 #else
 	RET
 #endif
+
+/* Logical Right Shift - R8:R11 -> R12:R15
+   A 64-bit argument would normally be passed in R12:R15, but __mspabi_srlll has
+   special conventions, so the 64-bit value to shift is passed in R8:R11.
+   According to the MSPABI, the shift amount is a 64-bit value in R12:R15, but
+   we only use the low word in R12.  */
+
+	.section	.text.__mspabi_srlll
+	.global __mspabi_srlll
+__mspabi_srlll:
+	MOV R11, R15 ; Free up R11 first
+	MOV R12, R11 ; Save the shift amount in R11
+	MOV R10, R14
+	MOV R9, R13
+	MOV R8, R12
+	CMP #0,R11
+	JNZ 1f
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
+1:
+	CLRC
+	RRC R15
+	RRC R14
+	RRC R13
+	RRC R12
+	ADD #-1,R11
+	JNZ 1b
+#ifdef __MSP430X_LARGE__
+	RETA
+#else
+	RET
+#endif
-- 
2.17.1