From 4de66875545233a2fadca8768d100efbcd110f67 Mon Sep 17 00:00:00 2001
From: Nigel Tao <nigeltao@golang.org>
Date: Tue, 2 Apr 2013 21:14:34 +1100
Subject: [PATCH] cmd/gc: recognize (a.b[0]<<1 | a.b[0]>>31) as a rotate, not
 just (x<<1 | x>>31).

Fixes #5084.

On the SHA3 benchmark proposals at
https://golang.org/cl/7760044/

benchmark                       old ns/op    new ns/op    delta
BenchmarkPermutationFunction         1288         1191   -7.53%
BenchmarkSingleByteWrite             5795         5811   +0.28%
BenchmarkBlockWrite512                178          179   +0.56%
BenchmarkBlockWrite384                230          233   +1.30%
BenchmarkBlockWrite256                282          286   +1.42%
BenchmarkBlockWrite224                301          306   +1.66%
BenchmarkBulkHashSHA3_512          326885       304548   -6.83%
BenchmarkBulkHashSHA3_384          234839       220074   -6.29%
BenchmarkBulkHashSHA3_256          186969       175790   -5.98%
BenchmarkBulkHashSHA3_224          178133       167489   -5.98%

For a function like

func g() {
        x = a[3]<<20 | a[3]>>12
}

the asm goes from

0006 (main.go:10) TEXT    g+0(SB),$0-0
0007 (main.go:10) MOVL    a+12(SB),BP
0008 (main.go:10) LOCALS  ,$0
0009 (main.go:11) MOVL    BP,BX
0010 (main.go:11) SHLL    $20,BX
0011 (main.go:11) SHRL    $12,BP
0012 (main.go:11) ORL     BP,BX
0013 (main.go:11) MOVL    BX,x+0(SB)
0014 (main.go:12) RET     ,

to

0006 (main.go:10) TEXT    g+0(SB),$0-0
0007 (main.go:10) LOCALS  ,$0
0008 (main.go:11) MOVL    a+12(SB),BX
0009 (main.go:11) ROLL    $20,BX
0010 (main.go:11) MOVL    BX,x+0(SB)
0011 (main.go:12) RET     ,

R=rsc, iant, remyoudompheng
CC=golang-dev, jcb
https://golang.org/cl/7944043
---
 src/cmd/gc/walk.c | 31 +++++++++++++++++++++++--------
 1 file changed, 23 insertions(+), 8 deletions(-)

diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c
index 4e42b182fe..d9c6341b43 100644
--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -2897,14 +2897,29 @@ hard:
 static int
 samecheap(Node *a, Node *b)
 {
-	if(a == N || b == N || a->op != b->op)
-		return 0;
-	
-	switch(a->op) {
-	case ONAME:
-		return a == b;
-	// TODO: Could do more here, but maybe this is enough.
-	// It's all cheapexpr does.
+	Node *ar, *br;
+	while(a != N && b != N && a->op == b->op) {
+		switch(a->op) {
+		default:
+			return 0;
+		case ONAME:
+			return a == b;
+		case ODOT:
+		case ODOTPTR:
+			ar = a->right;
+			br = b->right;
+			if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym)
+				return 0;
+			break;
+		case OINDEX:
+			ar = a->right;
+			br = b->right;
+			if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0)
+				return 0;
+			break;
+		}
+		a = a->left;
+		b = b->left;
 	}
 	return 0;
 }
-- 
2.50.0