cmd/compile: insert complicated x86 addressing modes as a separate pass

Use a separate compiler pass to introduce complicated x86 addressing
modes.  Loads in the normal architecture rules (for x86 and all other
platforms) can have constant offsets (AuxInt values) and symbols (Aux
values), but no more.

The complex addressing modes (x+y, x+2*y, etc.) are introduced in a
separate pass that combines loads with LEAQx ops.

Organizing rewrites this way simplifies the number of rewrites
required, as there are lots of different rule orderings that have to
be specified to ensure these complex addressing modes are always found
if they are possible.

Update #36468

Change-Id: I5b4bf7b03a1e731d6dfeb9ef19b376175f3b4b44
Reviewed-on: https://go-review.googlesource.com/c/go/+/217097
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

1 files changed, 154 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/addressingmodes.go b/src/cmd/compile/internal/ssa/addressingmodes.go
new file mode 100644
index 0000000000..8874b56a9b
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/addressingmodes.go
@@ -0,0 +1,154 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ssa
+
+// addressingModes combines address calculations into memory operations
+// that can perform complicated addressing modes.
+func addressingModes(f *Func) {
+	switch f.Config.arch {
+	default:
+		// Most architectures can't do this.
+		return
+	case "amd64":
+		// TODO: 386, s390x?
+	}
+
+	var tmp []*Value
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if !combineFirst[v.Op] {
+				continue
+			}
+			p := v.Args[0]
+			c, ok := combine[[2]Op{v.Op, p.Op}]
+			if !ok {
+				continue
+			}
+			// See if we can combine the Aux/AuxInt values.
+			switch [2]auxType{opcodeTable[v.Op].auxType, opcodeTable[p.Op].auxType} {
+			case [2]auxType{auxSymOff, auxInt32}:
+				// TODO: introduce auxSymOff32
+				if !is32Bit(v.AuxInt + p.AuxInt) {
+					continue
+				}
+				v.AuxInt += p.AuxInt
+			case [2]auxType{auxSymOff, auxSymOff}:
+				if v.Aux != nil && p.Aux != nil {
+					continue
+				}
+				if !is32Bit(v.AuxInt + p.AuxInt) {
+					continue
+				}
+				if p.Aux != nil {
+					v.Aux = p.Aux
+				}
+				v.AuxInt += p.AuxInt
+			case [2]auxType{auxSymValAndOff, auxInt32}:
+				vo := ValAndOff(v.AuxInt)
+				if !vo.canAdd(p.AuxInt) {
+					continue
+				}
+				v.AuxInt = vo.add(p.AuxInt)
+			case [2]auxType{auxSymValAndOff, auxSymOff}:
+				vo := ValAndOff(v.AuxInt)
+				if v.Aux != nil && p.Aux != nil {
+					continue
+				}
+				if !vo.canAdd(p.AuxInt) {
+					continue
+				}
+				if p.Aux != nil {
+					v.Aux = p.Aux
+				}
+				v.AuxInt = vo.add(p.AuxInt)
+			case [2]auxType{auxSymOff, auxNone}:
+				// nothing to do
+			case [2]auxType{auxSymValAndOff, auxNone}:
+				// nothing to do
+			default:
+				f.Fatalf("unknown aux combining for %s and %s\n", v.Op, p.Op)
+			}
+			// Combine the operations.
+			tmp = append(tmp[:0], v.Args[1:]...)
+			v.resetArgs()
+			v.Op = c
+			v.AddArgs(p.Args...)
+			v.AddArgs(tmp...)
+		}
+	}
+}
+
+// combineFirst contains ops which appear in combine as the
+// first part of the key.
+var combineFirst = map[Op]bool{}
+
+func init() {
+	for k := range combine {
+		combineFirst[k[0]] = true
+	}
+}
+
+// For each entry k, v in this map, if we have a value x with:
+//   x.Op == k[0]
+//   x.Args[0].Op == k[1]
+// then we can set x.Op to v and set x.Args like this:
+//   x.Args[0].Args + x.Args[1:]
+// Additionally, the Aux/AuxInt from x.Args[0] is merged into x.
+var combine = map[[2]Op]Op{
+	[2]Op{OpAMD64MOVBload, OpAMD64ADDQ}:  OpAMD64MOVBloadidx1,
+	[2]Op{OpAMD64MOVWload, OpAMD64ADDQ}:  OpAMD64MOVWloadidx1,
+	[2]Op{OpAMD64MOVLload, OpAMD64ADDQ}:  OpAMD64MOVLloadidx1,
+	[2]Op{OpAMD64MOVQload, OpAMD64ADDQ}:  OpAMD64MOVQloadidx1,
+	[2]Op{OpAMD64MOVSSload, OpAMD64ADDQ}: OpAMD64MOVSSloadidx1,
+	[2]Op{OpAMD64MOVSDload, OpAMD64ADDQ}: OpAMD64MOVSDloadidx1,
+
+	[2]Op{OpAMD64MOVBstore, OpAMD64ADDQ}:  OpAMD64MOVBstoreidx1,
+	[2]Op{OpAMD64MOVWstore, OpAMD64ADDQ}:  OpAMD64MOVWstoreidx1,
+	[2]Op{OpAMD64MOVLstore, OpAMD64ADDQ}:  OpAMD64MOVLstoreidx1,
+	[2]Op{OpAMD64MOVQstore, OpAMD64ADDQ}:  OpAMD64MOVQstoreidx1,
+	[2]Op{OpAMD64MOVSSstore, OpAMD64ADDQ}: OpAMD64MOVSSstoreidx1,
+	[2]Op{OpAMD64MOVSDstore, OpAMD64ADDQ}: OpAMD64MOVSDstoreidx1,
+
+	[2]Op{OpAMD64MOVBstoreconst, OpAMD64ADDQ}: OpAMD64MOVBstoreconstidx1,
+	[2]Op{OpAMD64MOVWstoreconst, OpAMD64ADDQ}: OpAMD64MOVWstoreconstidx1,
+	[2]Op{OpAMD64MOVLstoreconst, OpAMD64ADDQ}: OpAMD64MOVLstoreconstidx1,
+	[2]Op{OpAMD64MOVQstoreconst, OpAMD64ADDQ}: OpAMD64MOVQstoreconstidx1,
+
+	[2]Op{OpAMD64MOVBload, OpAMD64LEAQ1}:  OpAMD64MOVBloadidx1,
+	[2]Op{OpAMD64MOVWload, OpAMD64LEAQ1}:  OpAMD64MOVWloadidx1,
+	[2]Op{OpAMD64MOVWload, OpAMD64LEAQ2}:  OpAMD64MOVWloadidx2,
+	[2]Op{OpAMD64MOVLload, OpAMD64LEAQ1}:  OpAMD64MOVLloadidx1,
+	[2]Op{OpAMD64MOVLload, OpAMD64LEAQ4}:  OpAMD64MOVLloadidx4,
+	[2]Op{OpAMD64MOVLload, OpAMD64LEAQ8}:  OpAMD64MOVLloadidx8,
+	[2]Op{OpAMD64MOVQload, OpAMD64LEAQ1}:  OpAMD64MOVQloadidx1,
+	[2]Op{OpAMD64MOVQload, OpAMD64LEAQ8}:  OpAMD64MOVQloadidx8,
+	[2]Op{OpAMD64MOVSSload, OpAMD64LEAQ1}: OpAMD64MOVSSloadidx1,
+	[2]Op{OpAMD64MOVSSload, OpAMD64LEAQ4}: OpAMD64MOVSSloadidx4,
+	[2]Op{OpAMD64MOVSDload, OpAMD64LEAQ1}: OpAMD64MOVSDloadidx1,
+	[2]Op{OpAMD64MOVSDload, OpAMD64LEAQ8}: OpAMD64MOVSDloadidx8,
+
+	[2]Op{OpAMD64MOVBstore, OpAMD64LEAQ1}:  OpAMD64MOVBstoreidx1,
+	[2]Op{OpAMD64MOVWstore, OpAMD64LEAQ1}:  OpAMD64MOVWstoreidx1,
+	[2]Op{OpAMD64MOVWstore, OpAMD64LEAQ2}:  OpAMD64MOVWstoreidx2,
+	[2]Op{OpAMD64MOVLstore, OpAMD64LEAQ1}:  OpAMD64MOVLstoreidx1,
+	[2]Op{OpAMD64MOVLstore, OpAMD64LEAQ4}:  OpAMD64MOVLstoreidx4,
+	[2]Op{OpAMD64MOVLstore, OpAMD64LEAQ8}:  OpAMD64MOVLstoreidx8,
+	[2]Op{OpAMD64MOVQstore, OpAMD64LEAQ1}:  OpAMD64MOVQstoreidx1,
+	[2]Op{OpAMD64MOVQstore, OpAMD64LEAQ8}:  OpAMD64MOVQstoreidx8,
+	[2]Op{OpAMD64MOVSSstore, OpAMD64LEAQ1}: OpAMD64MOVSSstoreidx1,
+	[2]Op{OpAMD64MOVSSstore, OpAMD64LEAQ4}: OpAMD64MOVSSstoreidx4,
+	[2]Op{OpAMD64MOVSDstore, OpAMD64LEAQ1}: OpAMD64MOVSDstoreidx1,
+	[2]Op{OpAMD64MOVSDstore, OpAMD64LEAQ8}: OpAMD64MOVSDstoreidx8,
+
+	[2]Op{OpAMD64MOVBstoreconst, OpAMD64LEAQ1}: OpAMD64MOVBstoreconstidx1,
+	[2]Op{OpAMD64MOVWstoreconst, OpAMD64LEAQ1}: OpAMD64MOVWstoreconstidx1,
+	[2]Op{OpAMD64MOVWstoreconst, OpAMD64LEAQ2}: OpAMD64MOVWstoreconstidx2,
+	[2]Op{OpAMD64MOVLstoreconst, OpAMD64LEAQ1}: OpAMD64MOVLstoreconstidx1,
+	[2]Op{OpAMD64MOVLstoreconst, OpAMD64LEAQ4}: OpAMD64MOVLstoreconstidx4,
+	[2]Op{OpAMD64MOVQstoreconst, OpAMD64LEAQ1}: OpAMD64MOVQstoreconstidx1,
+	[2]Op{OpAMD64MOVQstoreconst, OpAMD64LEAQ8}: OpAMD64MOVQstoreconstidx8,
+
+	// TODO: 386
+}