commit 135389d0ff6d06646170ca10b432cddaac22a121
author Keith Randall <khr@golang.org> Thu Apr 30 10:41:57 2015 -0700
committer Keith Randall <khr@golang.org> Tue May 05 02:17:55 2015 +0000
tree fae20ab69529442e1f79bf072efda1c6596aed6e
parent 71274e48571581fa39aae105ebdf8e5f54e6c236

cmd/internal/gc: Use shifts for powers-of-two indexing

Fixes #10638

Change-Id: I7bbaad7e5a599aa94d1d158e903596231c7e9897
Reviewed-on: https://go-review.googlesource.com/9535
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

src/cmd/internal/gc/cgen.go

diff --git a/src/cmd/internal/gc/cgen.go b/src/cmd/internal/gc/cgen.go
index 15dca37..501cdcb 100644
--- a/src/cmd/internal/gc/cgen.go
+++ b/src/cmd/internal/gc/cgen.go
@@ -1132,12 +1132,18 @@
 			} else if w == 1 {
 				Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
 			} else {
-				Regalloc(&n4, Types[TUINT32], nil)
-				Nodconst(&n1, Types[TUINT32], int64(w))
-				Thearch.Gmove(&n1, &n4)
-				Thearch.Gins(Thearch.Optoas(OMUL, Types[TUINT32]), &n4, &n2)
+				if w&(w-1) == 0 {
+					// Power of 2.  Use shift.
+					Thearch.Ginscon(Thearch.Optoas(OLSH, Types[TUINT32]), int64(log2(uint64(w))), &n2)
+				} else {
+					// Not a power of 2.  Use multiply.
+					Regalloc(&n4, Types[TUINT32], nil)
+					Nodconst(&n1, Types[TUINT32], int64(w))
+					Thearch.Gmove(&n1, &n4)
+					Thearch.Gins(Thearch.Optoas(OMUL, Types[TUINT32]), &n4, &n2)
+					Regfree(&n4)
+				}
 				Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
-				Regfree(&n4)
 			}
 			*a = n3
 			Regfree(&n2)
@@ -1292,8 +1298,13 @@
 			} else if w == 1 {
 				Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
 			} else {
-				Nodconst(&tmp, Types[TUINT32], int64(w))
-				Thearch.Gins(Thearch.Optoas(OMUL, Types[TUINT32]), &tmp, &n2)
+				if w&(w-1) == 0 {
+					// Power of 2.  Use shift.
+					Thearch.Ginscon(Thearch.Optoas(OLSH, Types[TUINT32]), int64(log2(uint64(w))), &n2)
+				} else {
+					// Not a power of 2.  Use multiply.
+					Thearch.Ginscon(Thearch.Optoas(OMUL, Types[TUINT32]), int64(w), &n2)
+				}
 				Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
 			}
 
@@ -1485,7 +1496,13 @@
 		} else if w == 1 {
 			Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
 		} else {
-			Thearch.Ginscon(Thearch.Optoas(OMUL, t), int64(w), &n2)
+			if w&(w-1) == 0 {
+				// Power of 2.  Use shift.
+				Thearch.Ginscon(Thearch.Optoas(OLSH, t), int64(log2(w)), &n2)
+			} else {
+				// Not a power of 2.  Use multiply.
+				Thearch.Ginscon(Thearch.Optoas(OMUL, t), int64(w), &n2)
+			}
 			Thearch.Gins(Thearch.Optoas(OADD, Types[Tptr]), &n2, &n3)
 		}
 
@@ -1502,6 +1519,15 @@
 	}
 }
 
+// log2 returns the logarithm base 2 of n.  n must be a power of 2.
+func log2(n uint64) int {
+	x := 0
+	for n>>uint(x) != 1 {
+		x++
+	}
+	return x
+}
+
 /*
  * generate:
  *	res = &n;