config.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  import (
     8  	"cmd/compile/internal/abi"
     9  	"cmd/compile/internal/base"
    10  	"cmd/compile/internal/ir"
    11  	"cmd/compile/internal/ssa/ssabase"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/compile/internal/types"
    14  	"cmd/internal/obj"
    15  	"cmd/internal/src"
    16  )
    17  
    18  type (
    19  	BlockRewriter func(*Block) bool
    20  	ValueRewriter func(*Value) bool
    21  )
    22  
    23  // A Config holds readonly compilation information.
    24  // It is created once, early during compilation,
    25  // and shared across all compilations.
    26  type Config struct {
    27  	Arch           string // "amd64", etc.
    28  	PtrSize        int64  // 4 or 8; copy of cmd/internal/sys.Arch.PtrSize
    29  	RegSize        int64  // 4 or 8; copy of cmd/internal/sys.Arch.RegSize
    30  	Types          Types
    31  	LowerBlock     BlockRewriter      // block lowering function, first round
    32  	LowerValue     ValueRewriter      // value lowering function, first round
    33  	LateLowerBlock BlockRewriter      // block lowering function that needs to be run after the first round; only used on some architectures
    34  	LateLowerValue ValueRewriter      // value lowering function that needs to be run after the first round; only used on some architectures
    35  	SplitLoad      ValueRewriter      // function for splitting merged load ops; only used on some architectures
    36  	Registers      []ssabase.Register // machine registers
    37  	GpRegMask      ssaop.RegMask      // general purpose integer register mask
    38  	FpRegMask      ssaop.RegMask      // floating point register mask
    39  	Fp32RegMask    ssaop.RegMask      // floating point register mask
    40  	Fp64RegMask    ssaop.RegMask      // floating point register mask
    41  	SimdRegMask    ssaop.RegMask      // simd register mask; may be same as fpRegMask
    42  	SimdMaskReg    ssaop.RegMask      // simd mask (predicate) register mask; empty if the arch has none
    43  	// SpecialRegMask is the set of registers that are allocatable only where
    44  	// an operation's register mask names them explicitly. The register allocator
    45  	// must not place a value in one of these merely because of its type.
    46  	SpecialRegMask ssaop.RegMask
    47  	IntParamRegs   []int8         // register numbers of integer param (in/out) registers
    48  	FloatParamRegs []int8         // register numbers of floating param (in/out) registers
    49  	ABI1           *abi.ABIConfig // "ABIInternal" under development // TODO change comment when this becomes current
    50  	ABI0           *abi.ABIConfig
    51  	FPReg          int8      // register number of frame pointer, -1 if not used
    52  	LinkReg        int8      // register number of link register if it is a general purpose register, -1 if not used
    53  	HasGReg        bool      // has hardware g register
    54  	Ctxt           *obj.Link // Generic arch information
    55  	Optimize       bool      // Do optimization
    56  	SoftFloat      bool      //
    57  	Race           bool      // race detector enabled
    58  	BigEndian      bool      //
    59  	UnalignedOK    bool      // Unaligned loads/stores are ok
    60  	HaveBswap64    bool      // architecture implements Bswap64
    61  	HaveBswap32    bool      // architecture implements Bswap32
    62  	HaveBswap16    bool      // architecture implements Bswap16
    63  	HaveCondSelect bool      // architecture implements CondSelect
    64  
    65  	// MulRecipes[x] = function to build v * x from v.
    66  	MulRecipes map[int64]mulRecipe
    67  }
    68  
    69  type Frontend interface {
    70  	Logger
    71  
    72  	// StringData returns a symbol pointing to the given string's contents.
    73  	StringData(string) *obj.LSym
    74  
    75  	// Given the name for a compound type, returns the name we should use
    76  	// for the parts of that compound type.
    77  	SplitSlot(parent *LocalSlot, suffix string, offset int64, t *types.Type) LocalSlot
    78  
    79  	// Syslook returns a symbol of the runtime function/variable with the
    80  	// given name.
    81  	Syslook(string) *obj.LSym
    82  
    83  	// UseWriteBarrier reports whether write barrier is enabled
    84  	UseWriteBarrier() bool
    85  
    86  	// Func returns the ir.Func of the function being compiled.
    87  	Func() *ir.Func
    88  }
    89  
    90  type Logger interface {
    91  	// Logf logs a message from the compiler.
    92  	Logf(string, ...any)
    93  
    94  	// Log reports whether logging is not a no-op
    95  	// some logging calls account for more than a few heap allocations.
    96  	Log() bool
    97  
    98  	// Fatalf reports a compiler error and exits.
    99  	Fatalf(pos src.XPos, msg string, args ...any)
   100  
   101  	// Warnl writes compiler messages in the form expected by "errorcheck" tests
   102  	Warnl(pos src.XPos, fmt_ string, args ...any)
   103  
   104  	// Forwards the Debug flags from gc
   105  	Debug_checknil() bool
   106  }
   107  
   108  type Types struct {
   109  	Bool       *types.Type
   110  	Int8       *types.Type
   111  	Int16      *types.Type
   112  	Int32      *types.Type
   113  	Int64      *types.Type
   114  	UInt8      *types.Type
   115  	UInt16     *types.Type
   116  	UInt32     *types.Type
   117  	UInt64     *types.Type
   118  	Int        *types.Type
   119  	Float32    *types.Type
   120  	Float64    *types.Type
   121  	UInt       *types.Type
   122  	Uintptr    *types.Type
   123  	String     *types.Type
   124  	BytePtr    *types.Type // TODO: use unsafe.Pointer instead?
   125  	Int32Ptr   *types.Type
   126  	UInt32Ptr  *types.Type
   127  	IntPtr     *types.Type
   128  	UintptrPtr *types.Type
   129  	Float32Ptr *types.Type
   130  	Float64Ptr *types.Type
   131  	BytePtrPtr *types.Type
   132  	Vec128     *types.Type
   133  	Vec256     *types.Type
   134  	Vec512     *types.Type
   135  	Mask       *types.Type
   136  }
   137  
   138  type mulRecipe struct {
   139  	cost  int
   140  	Build func(*Value, *Value) *Value // build(m, v) returns v * x built at m.
   141  }
   142  
   143  // NewTypes creates and populates a Types.
   144  func NewTypes() *Types {
   145  	t := new(Types)
   146  	t.SetTypPtrs()
   147  	return t
   148  }
   149  
   150  // SetTypPtrs populates t.
   151  func (t *Types) SetTypPtrs() {
   152  	t.Bool = types.Types[types.TBOOL]
   153  	t.Int8 = types.Types[types.TINT8]
   154  	t.Int16 = types.Types[types.TINT16]
   155  	t.Int32 = types.Types[types.TINT32]
   156  	t.Int64 = types.Types[types.TINT64]
   157  	t.UInt8 = types.Types[types.TUINT8]
   158  	t.UInt16 = types.Types[types.TUINT16]
   159  	t.UInt32 = types.Types[types.TUINT32]
   160  	t.UInt64 = types.Types[types.TUINT64]
   161  	t.Int = types.Types[types.TINT]
   162  	t.Float32 = types.Types[types.TFLOAT32]
   163  	t.Float64 = types.Types[types.TFLOAT64]
   164  	t.UInt = types.Types[types.TUINT]
   165  	t.Uintptr = types.Types[types.TUINTPTR]
   166  	t.String = types.Types[types.TSTRING]
   167  	t.BytePtr = types.NewPtr(types.Types[types.TUINT8])
   168  	t.Int32Ptr = types.NewPtr(types.Types[types.TINT32])
   169  	t.UInt32Ptr = types.NewPtr(types.Types[types.TUINT32])
   170  	t.IntPtr = types.NewPtr(types.Types[types.TINT])
   171  	t.UintptrPtr = types.NewPtr(types.Types[types.TUINTPTR])
   172  	t.Float32Ptr = types.NewPtr(types.Types[types.TFLOAT32])
   173  	t.Float64Ptr = types.NewPtr(types.Types[types.TFLOAT64])
   174  	t.BytePtrPtr = types.NewPtr(types.NewPtr(types.Types[types.TUINT8]))
   175  	t.Vec128 = types.TypeVec128
   176  	t.Vec256 = types.TypeVec256
   177  	t.Vec512 = types.TypeVec512
   178  	t.Mask = types.TypeMask
   179  }
   180  
   181  func (c *Config) HaveByteSwap(size int64) bool {
   182  	switch size {
   183  	case 8:
   184  		return c.HaveBswap64
   185  	case 4:
   186  		return c.HaveBswap32
   187  	case 2:
   188  		return c.HaveBswap16
   189  	default:
   190  		base.Fatalf("bad size %d\n", size)
   191  		return false
   192  	}
   193  }
   194  
   195  func (c *Config) BuildRecipes(arch string) {
   196  	// Information for strength-reducing multiplies.
   197  	type linearCombo struct {
   198  		// we can compute a*x+b*y in one instruction
   199  		a, b int64
   200  		// cost, in arbitrary units (tenths of cycles, usually)
   201  		cost int
   202  		// builds SSA value for a*x+b*y. Use the position
   203  		// information from m.
   204  		build func(m, x, y *Value) *Value
   205  	}
   206  
   207  	// List all the linear combination instructions we have.
   208  	var linearCombos []linearCombo
   209  	r := func(a, b int64, cost int, build func(m, x, y *Value) *Value) {
   210  		linearCombos = append(linearCombos, linearCombo{a: a, b: b, cost: cost, build: build})
   211  	}
   212  	var mulCost int
   213  	switch arch {
   214  	case "amd64":
   215  		// Assumes that the following costs from https://gmplib.org/~tege/x86-timing.pdf:
   216  		//    1 - addq, shlq, leaq, negq, subq
   217  		//    3 - imulq
   218  		// These costs limit the rewrites to two instructions.
   219  		// Operations which have to happen in place (and thus
   220  		// may require a reg-reg move) score slightly higher.
   221  		mulCost = 30
   222  		// add
   223  		r(1, 1, 10,
   224  			func(m, x, y *Value) *Value {
   225  				v := m.Block.NewValue2(m.Pos, ssaop.OpAMD64ADDQ, m.Type, x, y)
   226  				if m.Type.Size() == 4 {
   227  					v.Op = ssaop.OpAMD64ADDL
   228  				}
   229  				return v
   230  			})
   231  		// neg
   232  		r(-1, 0, 11,
   233  			func(m, x, y *Value) *Value {
   234  				v := m.Block.NewValue1(m.Pos, ssaop.OpAMD64NEGQ, m.Type, x)
   235  				if m.Type.Size() == 4 {
   236  					v.Op = ssaop.OpAMD64NEGL
   237  				}
   238  				return v
   239  			})
   240  		// sub
   241  		r(1, -1, 11,
   242  			func(m, x, y *Value) *Value {
   243  				v := m.Block.NewValue2(m.Pos, ssaop.OpAMD64SUBQ, m.Type, x, y)
   244  				if m.Type.Size() == 4 {
   245  					v.Op = ssaop.OpAMD64SUBL
   246  				}
   247  				return v
   248  			})
   249  		// lea
   250  		r(1, 2, 10,
   251  			func(m, x, y *Value) *Value {
   252  				v := m.Block.NewValue2(m.Pos, ssaop.OpAMD64LEAQ2, m.Type, x, y)
   253  				if m.Type.Size() == 4 {
   254  					v.Op = ssaop.OpAMD64LEAL2
   255  				}
   256  				return v
   257  			})
   258  		r(1, 4, 10,
   259  			func(m, x, y *Value) *Value {
   260  				v := m.Block.NewValue2(m.Pos, ssaop.OpAMD64LEAQ4, m.Type, x, y)
   261  				if m.Type.Size() == 4 {
   262  					v.Op = ssaop.OpAMD64LEAL4
   263  				}
   264  				return v
   265  			})
   266  		r(1, 8, 10,
   267  			func(m, x, y *Value) *Value {
   268  				v := m.Block.NewValue2(m.Pos, ssaop.OpAMD64LEAQ8, m.Type, x, y)
   269  				if m.Type.Size() == 4 {
   270  					v.Op = ssaop.OpAMD64LEAL8
   271  				}
   272  				return v
   273  			})
   274  		// regular shifts
   275  		for i := 2; i < 64; i++ {
   276  			r(1<<i, 0, 11,
   277  				func(m, x, y *Value) *Value {
   278  					v := m.Block.NewValue1I(m.Pos, ssaop.OpAMD64SHLQconst, m.Type, int64(i), x)
   279  					if m.Type.Size() == 4 {
   280  						v.Op = ssaop.OpAMD64SHLLconst
   281  					}
   282  					return v
   283  				})
   284  		}
   285  
   286  	case "arm64":
   287  		// Rationale (for M2 ultra):
   288  		// - multiply is 3 cycles.
   289  		// - add/neg/sub/shift are 1 cycle.
   290  		// - add/neg/sub+shiftLL are 2 cycles.
   291  		// We break ties against the multiply because using a
   292  		// multiply also needs to load the constant into a register.
   293  		// (It's 3 cycles and 2 instructions either way, but the
   294  		// linear combo one might use 1 less register.)
   295  		// The multiply constant might get lifted out of a loop though. Hmm....
   296  		// Other arm64 chips have different tradeoffs.
   297  		// Some chip's add+shift instructions are 1 cycle for shifts up to 4
   298  		// and 2 cycles for shifts bigger than 4. So weight the larger shifts
   299  		// a bit more.
   300  		// TODO: figure out a happy medium.
   301  		mulCost = 35
   302  		// add
   303  		r(1, 1, 10,
   304  			func(m, x, y *Value) *Value {
   305  				return m.Block.NewValue2(m.Pos, ssaop.OpARM64ADD, m.Type, x, y)
   306  			})
   307  		// neg
   308  		r(-1, 0, 10,
   309  			func(m, x, y *Value) *Value {
   310  				return m.Block.NewValue1(m.Pos, ssaop.OpARM64NEG, m.Type, x)
   311  			})
   312  		// sub
   313  		r(1, -1, 10,
   314  			func(m, x, y *Value) *Value {
   315  				return m.Block.NewValue2(m.Pos, ssaop.OpARM64SUB, m.Type, x, y)
   316  			})
   317  		// ADDshiftLL
   318  		for i := 1; i < 64; i++ {
   319  			c := 20
   320  			if i > 4 {
   321  				c++
   322  			}
   323  			r(1, 1<<i, c,
   324  				func(m, x, y *Value) *Value {
   325  					return m.Block.NewValue2I(m.Pos, ssaop.OpARM64ADDshiftLL, m.Type, int64(i), x, y)
   326  				})
   327  		}
   328  		// NEGshiftLL
   329  		for i := 1; i < 64; i++ {
   330  			c := 20
   331  			if i > 4 {
   332  				c++
   333  			}
   334  			r(-1<<i, 0, c,
   335  				func(m, x, y *Value) *Value {
   336  					return m.Block.NewValue1I(m.Pos, ssaop.OpARM64NEGshiftLL, m.Type, int64(i), x)
   337  				})
   338  		}
   339  		// SUBshiftLL
   340  		for i := 1; i < 64; i++ {
   341  			c := 20
   342  			if i > 4 {
   343  				c++
   344  			}
   345  			r(1, -1<<i, c,
   346  				func(m, x, y *Value) *Value {
   347  					return m.Block.NewValue2I(m.Pos, ssaop.OpARM64SUBshiftLL, m.Type, int64(i), x, y)
   348  				})
   349  		}
   350  		// regular shifts
   351  		for i := 1; i < 64; i++ {
   352  			c := 10
   353  			if i == 1 {
   354  				// Prefer x<<1 over x+x.
   355  				// Note that we eventually reverse this decision in ARM64latelower.rules,
   356  				// but this makes shift combining rules in ARM64.rules simpler.
   357  				c--
   358  			}
   359  			r(1<<i, 0, c,
   360  				func(m, x, y *Value) *Value {
   361  					return m.Block.NewValue1I(m.Pos, ssaop.OpARM64SLLconst, m.Type, int64(i), x)
   362  				})
   363  		}
   364  	case "loong64":
   365  		// - multiply is 4 cycles.
   366  		// - add/sub/shift/alsl are 1 cycle.
   367  		// On loong64, using a multiply also needs to load the constant into a register.
   368  		// TODO: figure out a happy medium.
   369  		mulCost = 45
   370  
   371  		// add
   372  		r(1, 1, 10,
   373  			func(m, x, y *Value) *Value {
   374  				return m.Block.NewValue2(m.Pos, ssaop.OpLOONG64ADDV, m.Type, x, y)
   375  			})
   376  		// neg
   377  		r(-1, 0, 10,
   378  			func(m, x, y *Value) *Value {
   379  				return m.Block.NewValue1(m.Pos, ssaop.OpLOONG64NEGV, m.Type, x)
   380  			})
   381  		// sub
   382  		r(1, -1, 10,
   383  			func(m, x, y *Value) *Value {
   384  				return m.Block.NewValue2(m.Pos, ssaop.OpLOONG64SUBV, m.Type, x, y)
   385  			})
   386  
   387  		// ADDshiftLLV
   388  		for i := 1; i < 5; i++ {
   389  			c := 10
   390  			r(1, 1<<i, c,
   391  				func(m, x, y *Value) *Value {
   392  					return m.Block.NewValue2I(m.Pos, ssaop.OpLOONG64ADDshiftLLV, m.Type, int64(i), x, y)
   393  				})
   394  		}
   395  
   396  		// regular shifts
   397  		for i := 1; i < 64; i++ {
   398  			c := 10
   399  			if i == 1 {
   400  				// Prefer x<<1 over x+x.
   401  				// Note that we eventually reverse this decision in LOONG64latelower.rules,
   402  				// but this makes shift combining rules in LOONG64.rules simpler.
   403  				c--
   404  			}
   405  			r(1<<i, 0, c,
   406  				func(m, x, y *Value) *Value {
   407  					return m.Block.NewValue1I(m.Pos, ssaop.OpLOONG64SLLVconst, m.Type, int64(i), x)
   408  				})
   409  		}
   410  	}
   411  
   412  	c.MulRecipes = map[int64]mulRecipe{}
   413  
   414  	// Single-instruction recipes.
   415  	// The only option for the input value(s) is v.
   416  	for _, combo := range linearCombos {
   417  		x := combo.a + combo.b
   418  		cost := combo.cost
   419  		old := c.MulRecipes[x]
   420  		if (old.Build == nil || cost < old.cost) && cost < mulCost {
   421  			c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   422  				return combo.build(m, v, v)
   423  			}}
   424  		}
   425  	}
   426  	// Two-instruction recipes.
   427  	// A: Both of the outer's inputs are from the same single-instruction recipe.
   428  	// B: First input is v and the second is from a single-instruction recipe.
   429  	// C: Second input is v and the first is from a single-instruction recipe.
   430  	// A is slightly preferred because it often needs 1 less register, so it
   431  	// goes first.
   432  
   433  	// A
   434  	for _, inner := range linearCombos {
   435  		for _, outer := range linearCombos {
   436  			x := (inner.a + inner.b) * (outer.a + outer.b)
   437  			cost := inner.cost + outer.cost
   438  			old := c.MulRecipes[x]
   439  			if (old.Build == nil || cost < old.cost) && cost < mulCost {
   440  				c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   441  					v = inner.build(m, v, v)
   442  					return outer.build(m, v, v)
   443  				}}
   444  			}
   445  		}
   446  	}
   447  
   448  	// B
   449  	for _, inner := range linearCombos {
   450  		for _, outer := range linearCombos {
   451  			x := outer.a + outer.b*(inner.a+inner.b)
   452  			cost := inner.cost + outer.cost
   453  			old := c.MulRecipes[x]
   454  			if (old.Build == nil || cost < old.cost) && cost < mulCost {
   455  				c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   456  					return outer.build(m, v, inner.build(m, v, v))
   457  				}}
   458  			}
   459  		}
   460  	}
   461  
   462  	// C
   463  	for _, inner := range linearCombos {
   464  		for _, outer := range linearCombos {
   465  			x := outer.a*(inner.a+inner.b) + outer.b
   466  			cost := inner.cost + outer.cost
   467  			old := c.MulRecipes[x]
   468  			if (old.Build == nil || cost < old.cost) && cost < mulCost {
   469  				c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   470  					return outer.build(m, inner.build(m, v, v), v)
   471  				}}
   472  			}
   473  		}
   474  	}
   475  
   476  	// Currently we only process 3 linear combination instructions for loong64.
   477  	if arch == "loong64" {
   478  		// Three-instruction recipes.
   479  		// D: The first and the second are all single-instruction recipes, and they are also the third's inputs.
   480  		// E: The first single-instruction is the second's input, and the second is the third's input.
   481  
   482  		// D
   483  		for _, first := range linearCombos {
   484  			for _, second := range linearCombos {
   485  				for _, third := range linearCombos {
   486  					x := third.a*(first.a+first.b) + third.b*(second.a+second.b)
   487  					cost := first.cost + second.cost + third.cost
   488  					old := c.MulRecipes[x]
   489  					if (old.Build == nil || cost < old.cost) && cost < mulCost {
   490  						c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   491  							v1 := first.build(m, v, v)
   492  							v2 := second.build(m, v, v)
   493  							return third.build(m, v1, v2)
   494  						}}
   495  					}
   496  				}
   497  			}
   498  		}
   499  
   500  		// E
   501  		for _, first := range linearCombos {
   502  			for _, second := range linearCombos {
   503  				for _, third := range linearCombos {
   504  					x := third.a*(second.a*(first.a+first.b)+second.b) + third.b
   505  					cost := first.cost + second.cost + third.cost
   506  					old := c.MulRecipes[x]
   507  					if (old.Build == nil || cost < old.cost) && cost < mulCost {
   508  						c.MulRecipes[x] = mulRecipe{cost: cost, Build: func(m, v *Value) *Value {
   509  							v1 := first.build(m, v, v)
   510  							v2 := second.build(m, v1, v)
   511  							return third.build(m, v2, v)
   512  						}}
   513  					}
   514  				}
   515  			}
   516  		}
   517  	}
   518  
   519  	// These cases should be handled specially by rewrite rules.
   520  	// (Otherwise v * 1 == (neg (neg v)))
   521  	delete(c.MulRecipes, 0)
   522  	delete(c.MulRecipes, 1)
   523  
   524  	// Currently:
   525  	// len(c.mulRecipes) == 5984 on arm64
   526  	//                       680 on amd64
   527  	//                      9738 on loong64
   528  	// This function takes ~2.5ms on arm64.
   529  	//println(len(c.mulRecipes))
   530  }
   531
View as plain text