[go] cmd/compile: fold shift through AND for slice operations

7 views
Skip to first unread message

Alexander Musman (Gerrit)

unread,
Jun 7, 2025, 5:12:16 AMJun 7
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com

Alexander Musman has uploaded the change for review

Commit message

cmd/compile: fold shift through AND for slice operations

Fold a shift through AND when the AND gets a zero-or-one operand (e.g.
from arithmetic shift by 63 of a 64-bit value) for a common case with
slice operations:

    ASR     $63, R2, R2
    AND     R3<<3, R2, R2
    ADD     R2, R0, R2

As the operands are 64-bit, we can transform it to:

    AND     R2->63, R3, R2
    ADD     R2<<3, R0, R2

Code size improvement:
compile: .text:     9088004 ->  9086292 (-0.02%)
etcd:    .text:    10500276 -> 10498964 (-0.01%)
Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5

Change diff

diff --git a/src/cmd/compile/internal/ssa/_gen/ARM64.rules b/src/cmd/compile/internal/ssa/_gen/ARM64.rules
index 01fe3a7..6034d67 100644
--- a/src/cmd/compile/internal/ssa/_gen/ARM64.rules
+++ b/src/cmd/compile/internal/ssa/_gen/ARM64.rules
@@ -1658,6 +1658,10 @@
 (SRLconst [rc] (MOVHUreg x)) && rc >= 16 => (MOVDconst [0])
 (SRLconst [rc] (MOVBUreg x)) && rc >= 8 => (MOVDconst [0])
 
+// Special cases for slice operations
+(ADD x0 x1:(ANDshiftRA x2:(SLLconst [sl] y) z [63])) && x1.Uses == 1 && x2.Uses == 1 => (ADDshiftLL x0 (ANDshiftRA <y.Type> y z [63]) [sl])
+(ADD x0 x1:(ANDshiftLL x2:(SRAconst [63] z) y [sl])) && x1.Uses == 1 && x2.Uses == 1 => (ADDshiftLL x0 (ANDshiftRA <y.Type> y z [63]) [sl])
+
 // bitfield ops
 
 // sbfiz
diff --git a/src/cmd/compile/internal/ssa/rewriteARM64.go b/src/cmd/compile/internal/ssa/rewriteARM64.go
index 792967c..1bd759d 100644
--- a/src/cmd/compile/internal/ssa/rewriteARM64.go
+++ b/src/cmd/compile/internal/ssa/rewriteARM64.go
@@ -1592,6 +1592,66 @@
 		}
 		break
 	}
+	// match: (ADD x0 x1:(ANDshiftRA x2:(SLLconst [sl] y) z [63]))
+	// cond: x1.Uses == 1 && x2.Uses == 1
+	// result: (ADDshiftLL x0 (ANDshiftRA <y.Type> y z [63]) [sl])
+	for {
+		for _i0 := 0; _i0 <= 1; _i0, v_0, v_1 = _i0+1, v_1, v_0 {
+			x0 := v_0
+			x1 := v_1
+			if x1.Op != OpARM64ANDshiftRA || auxIntToInt64(x1.AuxInt) != 63 {
+				continue
+			}
+			z := x1.Args[1]
+			x2 := x1.Args[0]
+			if x2.Op != OpARM64SLLconst {
+				continue
+			}
+			sl := auxIntToInt64(x2.AuxInt)
+			y := x2.Args[0]
+			if !(x1.Uses == 1 && x2.Uses == 1) {
+				continue
+			}
+			v.reset(OpARM64ADDshiftLL)
+			v.AuxInt = int64ToAuxInt(sl)
+			v0 := b.NewValue0(v.Pos, OpARM64ANDshiftRA, y.Type)
+			v0.AuxInt = int64ToAuxInt(63)
+			v0.AddArg2(y, z)
+			v.AddArg2(x0, v0)
+			return true
+		}
+		break
+	}
+	// match: (ADD x0 x1:(ANDshiftLL x2:(SRAconst [63] z) y [sl]))
+	// cond: x1.Uses == 1 && x2.Uses == 1
+	// result: (ADDshiftLL x0 (ANDshiftRA <y.Type> y z [63]) [sl])
+	for {
+		for _i0 := 0; _i0 <= 1; _i0, v_0, v_1 = _i0+1, v_1, v_0 {
+			x0 := v_0
+			x1 := v_1
+			if x1.Op != OpARM64ANDshiftLL {
+				continue
+			}
+			sl := auxIntToInt64(x1.AuxInt)
+			y := x1.Args[1]
+			x2 := x1.Args[0]
+			if x2.Op != OpARM64SRAconst || auxIntToInt64(x2.AuxInt) != 63 {
+				continue
+			}
+			z := x2.Args[0]
+			if !(x1.Uses == 1 && x2.Uses == 1) {
+				continue
+			}
+			v.reset(OpARM64ADDshiftLL)
+			v.AuxInt = int64ToAuxInt(sl)
+			v0 := b.NewValue0(v.Pos, OpARM64ANDshiftRA, y.Type)
+			v0.AuxInt = int64ToAuxInt(63)
+			v0.AddArg2(y, z)
+			v.AddArg2(x0, v0)
+			return true
+		}
+		break
+	}
 	return false
 }
 func rewriteValueARM64_OpARM64ADDSflags(v *Value) bool {
diff --git a/test/codegen/slices.go b/test/codegen/slices.go
index 9e8990c..a00c878 100644
--- a/test/codegen/slices.go
+++ b/test/codegen/slices.go
@@ -418,6 +418,15 @@
 }
 
 // --------------------------------------- //
+//   ARM64 folding for slice masks         //
+// --------------------------------------- //
+
+func SliceAndIndex(a []int, b int) int {
+	// arm64:"AND\tR[0-9]+->63","ADD\tR[0-9]+<<3"
+	return a[b:][b]
+}
+
+// --------------------------------------- //
 //   Code generation for unsafe.Slice      //
 // --------------------------------------- //

Change information

Files:
  • M src/cmd/compile/internal/ssa/_gen/ARM64.rules
  • M src/cmd/compile/internal/ssa/rewriteARM64.go
  • M test/codegen/slices.go
Change size: M
Delta: 3 files changed, 73 insertions(+), 0 deletions(-)
Open in Gerrit

Related details

Attention set is empty
Submit Requirements:
  • requirement is not satisfiedCode-Review
  • requirement satisfiedNo-Unresolved-Comments
  • requirement is not satisfiedReview-Enforcement
  • requirement is not satisfiedTryBots-Pass
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: newchange
Gerrit-Project: go
Gerrit-Branch: master
Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
Gerrit-Change-Number: 679895
Gerrit-PatchSet: 1
Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
unsatisfied_requirement
satisfied_requirement
open
diffy

Keith Randall (Gerrit)

unread,
Jun 9, 2025, 12:47:43 PMJun 9
to Alexander Musman, goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Alexander Musman and Martin Möhrmann

Keith Randall voted and added 1 comment

Votes added by Keith Randall

Code-Review+2
Commit-Queue+1

1 comment

Patchset-level comments
File-level comment, Patchset 1 (Latest):
Keith Randall . resolved
Is there something we can do for non-powers-of-two-sized element types?
```
type T struct {
	a, b, c int
}
func f(x []T, i int) []T {
	return x[i:]
}
```
Open in Gerrit

Related details

Attention is currently required from:
  • Alexander Musman
  • Martin Möhrmann
Submit Requirements:
  • requirement satisfiedCode-Review
  • requirement satisfiedNo-Unresolved-Comments
  • requirement is not satisfiedReview-Enforcement
  • requirement is not satisfiedTryBots-Pass
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: comment
Gerrit-Project: go
Gerrit-Branch: master
Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
Gerrit-Change-Number: 679895
Gerrit-PatchSet: 1
Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
Gerrit-Reviewer: Keith Randall <k...@golang.org>
Gerrit-Reviewer: Martin Möhrmann <moeh...@google.com>
Gerrit-CC: Gopher Robot <go...@golang.org>
Gerrit-Attention: Alexander Musman <alexande...@gmail.com>
Gerrit-Attention: Martin Möhrmann <moeh...@google.com>
Gerrit-Comment-Date: Mon, 09 Jun 2025 16:47:37 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: Yes
satisfied_requirement
unsatisfied_requirement
open
diffy

Alexander Musman (Gerrit)

unread,
Jun 9, 2025, 4:40:04 PMJun 9
to goph...@pubsubhelper.golang.org, Go LUCI, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Martin Möhrmann

Alexander Musman added 1 comment

Patchset-level comments
Keith Randall . resolved
Is there something we can do for non-powers-of-two-sized element types?
```
type T struct {
	a, b, c int
}
func f(x []T, i int) []T {
	return x[i:]
}
```
Alexander Musman

Interesting, it seems we can reorder `shift` instruction after `add` because it's used only by `add`, and more likely to be matched with some subsequent instructions (than `add`):
```
LSL $3, R3, R3
ADD R3<<1, R3, R3
AND R5->63, R3, R3
ADD R3, R0, R0
```
At least the following rule seems to work together with this CL:
```
(ADDshiftLL [c1] x:(SLLconst [c2] y) x) && x.Uses == 2 => (SLLconst [c2] (ADDshiftLL <y.Type> [c1] y y))
```
it leads to the following sequence:
```
ADD R3<<1, R3, R3
AND R5->63, R3, R3
ADD R3<<3, R0, R0
```
(maybe such reordering could help with some other shifts besides SLLconst too, for other patterns)

Open in Gerrit

Related details

Attention is currently required from:
  • Martin Möhrmann
Submit Requirements:
    • requirement satisfiedCode-Review
    • requirement satisfiedNo-Unresolved-Comments
    • requirement is not satisfiedNo-Wait-Release
    • requirement is not satisfiedReview-Enforcement
    • requirement satisfiedTryBots-Pass
    Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
    Gerrit-MessageType: comment
    Gerrit-Project: go
    Gerrit-Branch: master
    Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
    Gerrit-Change-Number: 679895
    Gerrit-PatchSet: 1
    Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
    Gerrit-Reviewer: Keith Randall <k...@golang.org>
    Gerrit-Reviewer: Martin Möhrmann <moeh...@google.com>
    Gerrit-CC: Gopher Robot <go...@golang.org>
    Gerrit-Attention: Martin Möhrmann <moeh...@google.com>
    Gerrit-Comment-Date: Mon, 09 Jun 2025 20:39:56 +0000
    Gerrit-HasComments: Yes
    Gerrit-Has-Labels: No
    Comment-In-Reply-To: Keith Randall <k...@golang.org>
    satisfied_requirement
    unsatisfied_requirement
    open
    diffy

    Michael Knyszek (Gerrit)

    unread,
    Jul 24, 2025, 3:40:05 PMJul 24
    to Alexander Musman, goph...@pubsubhelper.golang.org, Go LUCI, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
    Attention needed from Alexander Musman and Martin Möhrmann

    Michael Knyszek voted Code-Review+1

    Code-Review+1
    Open in Gerrit

    Related details

    Attention is currently required from:
    • Alexander Musman
    • Martin Möhrmann
    Submit Requirements:
      • requirement satisfiedCode-Review
      • requirement satisfiedNo-Unresolved-Comments
      • requirement is not satisfiedReview-Enforcement
      • requirement satisfiedTryBots-Pass
      Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
      Gerrit-MessageType: comment
      Gerrit-Project: go
      Gerrit-Branch: master
      Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
      Gerrit-Change-Number: 679895
      Gerrit-PatchSet: 1
      Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
      Gerrit-Reviewer: Keith Randall <k...@golang.org>
      Gerrit-Reviewer: Martin Möhrmann <moeh...@google.com>
      Gerrit-Reviewer: Michael Knyszek <mkny...@google.com>
      Gerrit-CC: Gopher Robot <go...@golang.org>
      Gerrit-Attention: Alexander Musman <alexande...@gmail.com>
      Gerrit-Attention: Martin Möhrmann <moeh...@google.com>
      Gerrit-Comment-Date: Thu, 24 Jul 2025 19:40:01 +0000
      Gerrit-HasComments: No
      Gerrit-Has-Labels: Yes
      satisfied_requirement
      unsatisfied_requirement
      open
      diffy

      Mark Freeman (Gerrit)

      unread,
      Jul 24, 2025, 3:48:18 PMJul 24
      to Alexander Musman, goph...@pubsubhelper.golang.org, Go LUCI, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
      Attention needed from Alexander Musman and Martin Möhrmann

      Mark Freeman voted Code-Review+1

      Code-Review+1
      Open in Gerrit

      Related details

      Attention is currently required from:
      • Alexander Musman
      • Martin Möhrmann
      Submit Requirements:
        • requirement satisfiedCode-Review
        • requirement satisfiedNo-Unresolved-Comments
        • requirement satisfiedReview-Enforcement
        • requirement satisfiedTryBots-Pass
        Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
        Gerrit-MessageType: comment
        Gerrit-Project: go
        Gerrit-Branch: master
        Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
        Gerrit-Change-Number: 679895
        Gerrit-PatchSet: 1
        Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
        Gerrit-Reviewer: Keith Randall <k...@golang.org>
        Gerrit-Reviewer: Mark Freeman <ma...@golang.org>
        Gerrit-Reviewer: Martin Möhrmann <moeh...@google.com>
        Gerrit-Reviewer: Michael Knyszek <mkny...@google.com>
        Gerrit-CC: Gopher Robot <go...@golang.org>
        Gerrit-Attention: Alexander Musman <alexande...@gmail.com>
        Gerrit-Attention: Martin Möhrmann <moeh...@google.com>
        Gerrit-Comment-Date: Thu, 24 Jul 2025 19:48:14 +0000
        Gerrit-HasComments: No
        Gerrit-Has-Labels: Yes
        satisfied_requirement
        open
        diffy

        Michael Knyszek (Gerrit)

        unread,
        Jul 24, 2025, 4:44:45 PMJul 24
        to Alexander Musman, goph...@pubsubhelper.golang.org, Mark Freeman, Go LUCI, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
        Attention needed from Alexander Musman and Martin Möhrmann

        Michael Knyszek voted Auto-Submit+1

        Auto-Submit+1
        Gerrit-Comment-Date: Thu, 24 Jul 2025 20:44:39 +0000
        Gerrit-HasComments: No
        Gerrit-Has-Labels: Yes
        satisfied_requirement
        open
        diffy

        Gopher Robot (Gerrit)

        unread,
        Jul 24, 2025, 4:47:30 PMJul 24
        to Alexander Musman, goph...@pubsubhelper.golang.org, golang-...@googlegroups.com, Michael Knyszek, Mark Freeman, Go LUCI, Keith Randall, Martin Möhrmann, golang-co...@googlegroups.com

        Gopher Robot submitted the change

        Change information

        Commit message:
        cmd/compile: fold shift through AND for slice operations

        Fold a shift through AND when the AND gets a zero-or-one operand (e.g.
        from arithmetic shift by 63 of a 64-bit value) for a common case with
        slice operations:

            ASR     $63, R2, R2
            AND     R3<<3, R2, R2
            ADD     R2, R0, R2

        As the operands are 64-bit, we can transform it to:

            AND     R2->63, R3, R2
            ADD     R2<<3, R0, R2

        Code size improvement:
        compile: .text:     9088004 ->  9086292 (-0.02%)
        etcd:    .text:    10500276 -> 10498964 (-0.01%)
        Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
        Reviewed-by: Keith Randall <k...@golang.org>
        Reviewed-by: Mark Freeman <ma...@golang.org>
        Auto-Submit: Michael Knyszek <mkny...@google.com>
        Reviewed-by: Michael Knyszek <mkny...@google.com>
        Files:
        • M src/cmd/compile/internal/ssa/_gen/ARM64.rules
        • M src/cmd/compile/internal/ssa/rewriteARM64.go
        • M test/codegen/slices.go
        Change size: M
        Delta: 3 files changed, 73 insertions(+), 0 deletions(-)
        Branch: refs/heads/master
        Submit Requirements:
        • requirement satisfiedCode-Review: +1 by Mark Freeman, +2 by Keith Randall, +1 by Michael Knyszek
        • requirement satisfiedTryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
        Open in Gerrit
        Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
        Gerrit-MessageType: merged
        Gerrit-Project: go
        Gerrit-Branch: master
        Gerrit-Change-Id: Ibcd5e67173da39b77ceff77ca67812fb8be5a7b5
        Gerrit-Change-Number: 679895
        Gerrit-PatchSet: 2
        Gerrit-Owner: Alexander Musman <alexande...@gmail.com>
        Gerrit-Reviewer: Gopher Robot <go...@golang.org>
        open
        diffy
        satisfied_requirement
        Reply all
        Reply to author
        Forward
        0 new messages