main.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  // The gen command generates Go code (in the parent directory) for all
     6  // the architecture-specific opcodes, blocks, and rewrites.
     7  package main
     8  
     9  import (
    10  	"bytes"
    11  	"flag"
    12  	"fmt"
    13  	"go/format"
    14  	"log"
    15  	"math/bits"
    16  	"os"
    17  	"path"
    18  	"regexp"
    19  	"runtime"
    20  	"runtime/pprof"
    21  	"runtime/trace"
    22  	"slices"
    23  	"sort"
    24  	"strings"
    25  	"sync"
    26  )
    27  
    28  // TODO: capitalize these types, so that we can more easily tell variable names
    29  // apart from type names, and avoid awkward func parameters like "arch arch".
    30  
    31  type arch struct {
    32  	name               string
    33  	pkg                string // obj package to import for this arch.
    34  	genfile            string // source file containing opcode code generation.
    35  	genSIMDfile        string // source file containing opcode code generation for SIMD.
    36  	ops                []opData
    37  	blocks             []blockData
    38  	regnames           []string
    39  	ParamIntRegNames   string
    40  	ParamFloatRegNames string
    41  	gpregmask          regMask
    42  	fpregmask          regMask
    43  	fp32regmask        regMask
    44  	fp64regmask        regMask
    45  	specialregmask     regMask
    46  	framepointerreg    int8
    47  	linkreg            int8
    48  	generic            bool
    49  	imports            []string
    50  }
    51  
    52  type opData struct {
    53  	name              string
    54  	reg               regInfo
    55  	asm               string
    56  	typ               string // default result type
    57  	aux               string
    58  	rematerializeable bool
    59  	argLength         int32  // number of arguments, if -1, then this operation has a variable number of arguments
    60  	commutative       bool   // this operation is commutative on its first 2 arguments (e.g. addition)
    61  	resultInArg0      bool   // (first, if a tuple) output of v and v.Args[0] must be allocated to the same register
    62  	resultNotInArgs   bool   // outputs must not be allocated to the same registers as inputs
    63  	clobberFlags      bool   // this op clobbers flags register
    64  	needIntTemp       bool   // need a temporary free integer register
    65  	call              bool   // is a function call
    66  	tailCall          bool   // is a tail call
    67  	nilCheck          bool   // this op is a nil check on arg0
    68  	faultOnNilArg0    bool   // this op will fault if arg0 is nil (and aux encodes a small offset)
    69  	faultOnNilArg1    bool   // this op will fault if arg1 is nil (and aux encodes a small offset)
    70  	hasSideEffects    bool   // for "reasons", not to be eliminated.  E.g., atomic store, #19182.
    71  	zeroWidth         bool   // op never translates into any machine code. example: copy, which may sometimes translate to machine code, is not zero-width.
    72  	unsafePoint       bool   // this op is an unsafe point, i.e. not safe for async preemption
    73  	fixedReg          bool   // this op will be assigned a fixed register
    74  	symEffect         string // effect this op has on symbol in aux
    75  	scale             uint8  // amd64/386 indexed load scale
    76  }
    77  
    78  type blockData struct {
    79  	name     string // the suffix for this block ("EQ", "LT", etc.)
    80  	controls int    // the number of control values this type of block requires
    81  	aux      string // the type of the Aux/AuxInt value, if any
    82  }
    83  
    84  type regInfo struct {
    85  	// inputs[i] encodes the set of registers allowed for the i'th input.
    86  	// Inputs that don't use registers (flags, memory, etc.) should be 0.
    87  	inputs []regMask
    88  	// clobbers encodes the set of registers that are overwritten by
    89  	// the instruction (other than the output registers).
    90  	clobbers regMask
    91  	// Instruction clobbers the register containing input 0.
    92  	clobbersArg0 bool
    93  	// Instruction clobbers the register containing input 1.
    94  	clobbersArg1 bool
    95  	// outputs[i] encodes the set of registers allowed for the i'th output.
    96  	outputs []regMask
    97  }
    98  
    99  type regMask uint64
   100  
   101  func (a arch) regMaskComment(r regMask) string {
   102  	var buf strings.Builder
   103  	for i := uint64(0); r != 0; i++ {
   104  		if r&1 != 0 {
   105  			if buf.Len() == 0 {
   106  				buf.WriteString(" //")
   107  			}
   108  			buf.WriteString(" ")
   109  			buf.WriteString(a.regnames[i])
   110  		}
   111  		r >>= 1
   112  	}
   113  	return buf.String()
   114  }
   115  
   116  var archs []arch
   117  
   118  var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to `file`")
   119  var memprofile = flag.String("memprofile", "", "write memory profile to `file`")
   120  var tracefile = flag.String("trace", "", "write trace to `file`")
   121  var outDir = flag.String("outdir", "..", "directory in which to write generated files")
   122  
   123  func main() {
   124  	flag.Parse()
   125  	if *cpuprofile != "" {
   126  		f, err := os.Create(*cpuprofile)
   127  		if err != nil {
   128  			log.Fatal("could not create CPU profile: ", err)
   129  		}
   130  		defer f.Close()
   131  		if err := pprof.StartCPUProfile(f); err != nil {
   132  			log.Fatal("could not start CPU profile: ", err)
   133  		}
   134  		defer pprof.StopCPUProfile()
   135  	}
   136  	if *tracefile != "" {
   137  		f, err := os.Create(*tracefile)
   138  		if err != nil {
   139  			log.Fatalf("failed to create trace output file: %v", err)
   140  		}
   141  		defer func() {
   142  			if err := f.Close(); err != nil {
   143  				log.Fatalf("failed to close trace file: %v", err)
   144  			}
   145  		}()
   146  
   147  		if err := trace.Start(f); err != nil {
   148  			log.Fatalf("failed to start trace: %v", err)
   149  		}
   150  		defer trace.Stop()
   151  	}
   152  
   153  	if *outDir != ".." {
   154  		err := os.MkdirAll(*outDir, 0755)
   155  		if err != nil {
   156  			log.Fatalf("failed to create output directory: %v", err)
   157  		}
   158  	}
   159  
   160  	slices.SortFunc(archs, func(a, b arch) int {
   161  		return strings.Compare(a.name, b.name)
   162  	})
   163  
   164  	// The generate tasks are run concurrently, since they are CPU-intensive
   165  	// that can easily make use of many cores on a machine.
   166  	//
   167  	// Note that there is no limit on the concurrency at the moment. On a
   168  	// four-core laptop at the time of writing, peak RSS usually reaches
   169  	// ~200MiB, which seems doable by practically any machine nowadays. If
   170  	// that stops being the case, we can cap this func to a fixed number of
   171  	// architectures being generated at once.
   172  
   173  	tasks := []func(){
   174  		genOp,
   175  		genAllocators,
   176  	}
   177  	for _, a := range archs {
   178  		a := a // the funcs are ran concurrently at a later time
   179  		tasks = append(tasks, func() {
   180  			genRules(a)
   181  			genSplitLoadRules(a)
   182  			genLateLowerRules(a)
   183  		})
   184  	}
   185  	var wg sync.WaitGroup
   186  	for _, task := range tasks {
   187  		task := task
   188  		wg.Add(1)
   189  		go func() {
   190  			task()
   191  			wg.Done()
   192  		}()
   193  	}
   194  	wg.Wait()
   195  
   196  	if *memprofile != "" {
   197  		f, err := os.Create(*memprofile)
   198  		if err != nil {
   199  			log.Fatal("could not create memory profile: ", err)
   200  		}
   201  		defer f.Close()
   202  		runtime.GC() // get up-to-date statistics
   203  		if err := pprof.WriteHeapProfile(f); err != nil {
   204  			log.Fatal("could not write memory profile: ", err)
   205  		}
   206  	}
   207  }
   208  
   209  func outFile(file string) string {
   210  	return *outDir + "/" + file
   211  }
   212  
   213  func genOp() {
   214  	w := new(bytes.Buffer)
   215  	fmt.Fprintf(w, "// Code generated from _gen/*Ops.go using 'go generate'; DO NOT EDIT.\n")
   216  	fmt.Fprintln(w)
   217  	fmt.Fprintln(w, "package ssa")
   218  
   219  	fmt.Fprintln(w, "import (")
   220  	fmt.Fprintln(w, "\"cmd/internal/obj\"")
   221  	for _, a := range archs {
   222  		if a.pkg != "" {
   223  			fmt.Fprintf(w, "%q\n", a.pkg)
   224  		}
   225  	}
   226  	fmt.Fprintln(w, ")")
   227  
   228  	// generate Block* declarations
   229  	fmt.Fprintln(w, "const (")
   230  	fmt.Fprintln(w, "BlockInvalid BlockKind = iota")
   231  	for _, a := range archs {
   232  		fmt.Fprintln(w)
   233  		for _, d := range a.blocks {
   234  			fmt.Fprintf(w, "Block%s%s\n", a.Name(), d.name)
   235  		}
   236  	}
   237  	fmt.Fprintln(w, ")")
   238  
   239  	// generate block kind string method
   240  	fmt.Fprintln(w, "var blockString = [...]string{")
   241  	fmt.Fprintln(w, "BlockInvalid:\"BlockInvalid\",")
   242  	for _, a := range archs {
   243  		fmt.Fprintln(w)
   244  		for _, b := range a.blocks {
   245  			fmt.Fprintf(w, "Block%s%s:\"%s\",\n", a.Name(), b.name, b.name)
   246  		}
   247  	}
   248  	fmt.Fprintln(w, "}")
   249  	fmt.Fprintln(w, "func (k BlockKind) String() string {return blockString[k]}")
   250  
   251  	// generate block kind auxint method
   252  	fmt.Fprintln(w, "func (k BlockKind) AuxIntType() string {")
   253  	fmt.Fprintln(w, "switch k {")
   254  	for _, a := range archs {
   255  		for _, b := range a.blocks {
   256  			if b.auxIntType() == "invalid" {
   257  				continue
   258  			}
   259  			fmt.Fprintf(w, "case Block%s%s: return \"%s\"\n", a.Name(), b.name, b.auxIntType())
   260  		}
   261  	}
   262  	fmt.Fprintln(w, "}")
   263  	fmt.Fprintln(w, "return \"\"")
   264  	fmt.Fprintln(w, "}")
   265  
   266  	// generate Op* declarations
   267  	fmt.Fprintln(w, "const (")
   268  	fmt.Fprintln(w, "OpInvalid Op = iota") // make sure OpInvalid is 0.
   269  	for _, a := range archs {
   270  		fmt.Fprintln(w)
   271  		for _, v := range a.ops {
   272  			if v.name == "Invalid" {
   273  				continue
   274  			}
   275  			fmt.Fprintf(w, "Op%s%s\n", a.Name(), v.name)
   276  		}
   277  	}
   278  	fmt.Fprintln(w, ")")
   279  
   280  	// generate OpInfo table
   281  	fmt.Fprintln(w, "var opcodeTable = [...]opInfo{")
   282  	fmt.Fprintln(w, " { name: \"OpInvalid\" },")
   283  	for _, a := range archs {
   284  		fmt.Fprintln(w)
   285  
   286  		pkg := path.Base(a.pkg)
   287  		for _, v := range a.ops {
   288  			if v.name == "Invalid" {
   289  				continue
   290  			}
   291  			fmt.Fprintln(w, "{")
   292  			fmt.Fprintf(w, "name:\"%s\",\n", v.name)
   293  
   294  			// flags
   295  			if v.aux != "" {
   296  				fmt.Fprintf(w, "auxType: aux%s,\n", v.aux)
   297  			}
   298  			fmt.Fprintf(w, "argLen: %d,\n", v.argLength)
   299  
   300  			if v.rematerializeable {
   301  				if v.reg.clobbers != 0 || v.reg.clobbersArg0 || v.reg.clobbersArg1 {
   302  					log.Fatalf("%s is rematerializeable and clobbers registers", v.name)
   303  				}
   304  				if v.clobberFlags {
   305  					log.Fatalf("%s is rematerializeable and clobbers flags", v.name)
   306  				}
   307  				fmt.Fprintln(w, "rematerializeable: true,")
   308  			}
   309  			if v.commutative {
   310  				fmt.Fprintln(w, "commutative: true,")
   311  			}
   312  			if v.resultInArg0 {
   313  				fmt.Fprintln(w, "resultInArg0: true,")
   314  				// OpConvert's register mask is selected dynamically,
   315  				// so don't try to check it in the static table.
   316  				if v.name != "Convert" && v.reg.inputs[0] != v.reg.outputs[0] {
   317  					log.Fatalf("%s: input[0] and output[0] must use the same registers for %s", a.name, v.name)
   318  				}
   319  				if v.name != "Convert" && v.commutative && v.reg.inputs[1] != v.reg.outputs[0] {
   320  					log.Fatalf("%s: input[1] and output[0] must use the same registers for %s", a.name, v.name)
   321  				}
   322  			}
   323  			if v.resultNotInArgs {
   324  				fmt.Fprintln(w, "resultNotInArgs: true,")
   325  			}
   326  			if v.clobberFlags {
   327  				fmt.Fprintln(w, "clobberFlags: true,")
   328  			}
   329  			if v.needIntTemp {
   330  				fmt.Fprintln(w, "needIntTemp: true,")
   331  			}
   332  			if v.call {
   333  				fmt.Fprintln(w, "call: true,")
   334  			}
   335  			if v.tailCall {
   336  				fmt.Fprintln(w, "tailCall: true,")
   337  			}
   338  			if v.nilCheck {
   339  				fmt.Fprintln(w, "nilCheck: true,")
   340  			}
   341  			if v.faultOnNilArg0 {
   342  				fmt.Fprintln(w, "faultOnNilArg0: true,")
   343  				if v.aux != "Sym" && v.aux != "SymOff" && v.aux != "SymValAndOff" && v.aux != "Int64" && v.aux != "Int32" && v.aux != "" {
   344  					log.Fatalf("faultOnNilArg0 with aux %s not allowed", v.aux)
   345  				}
   346  			}
   347  			if v.faultOnNilArg1 {
   348  				fmt.Fprintln(w, "faultOnNilArg1: true,")
   349  				if v.aux != "Sym" && v.aux != "SymOff" && v.aux != "SymValAndOff" && v.aux != "Int64" && v.aux != "Int32" && v.aux != "" {
   350  					log.Fatalf("faultOnNilArg1 with aux %s not allowed", v.aux)
   351  				}
   352  			}
   353  			if v.hasSideEffects {
   354  				fmt.Fprintln(w, "hasSideEffects: true,")
   355  			}
   356  			if v.zeroWidth {
   357  				fmt.Fprintln(w, "zeroWidth: true,")
   358  			}
   359  			if v.fixedReg {
   360  				fmt.Fprintln(w, "fixedReg: true,")
   361  			}
   362  			if v.unsafePoint {
   363  				fmt.Fprintln(w, "unsafePoint: true,")
   364  			}
   365  			needEffect := strings.HasPrefix(v.aux, "Sym")
   366  			if v.symEffect != "" {
   367  				if !needEffect {
   368  					log.Fatalf("symEffect with aux %s not allowed", v.aux)
   369  				}
   370  				fmt.Fprintf(w, "symEffect: Sym%s,\n", strings.ReplaceAll(v.symEffect, ",", "|Sym"))
   371  			} else if needEffect {
   372  				log.Fatalf("symEffect needed for aux %s", v.aux)
   373  			}
   374  			if a.name == "generic" {
   375  				fmt.Fprintln(w, "generic:true,")
   376  				fmt.Fprintln(w, "},") // close op
   377  				// generic ops have no reg info or asm
   378  				continue
   379  			}
   380  			if v.asm != "" {
   381  				fmt.Fprintf(w, "asm: %s.A%s,\n", pkg, v.asm)
   382  			}
   383  			if v.scale != 0 {
   384  				fmt.Fprintf(w, "scale: %d,\n", v.scale)
   385  			}
   386  			fmt.Fprintln(w, "reg:regInfo{")
   387  
   388  			// Compute input allocation order. We allocate from the
   389  			// most to the least constrained input. This order guarantees
   390  			// that we will always be able to find a register.
   391  			var s []intPair
   392  			for i, r := range v.reg.inputs {
   393  				if r != 0 {
   394  					s = append(s, intPair{countRegs(r), i})
   395  				}
   396  			}
   397  			if len(s) > 0 {
   398  				sort.Sort(byKey(s))
   399  				fmt.Fprintln(w, "inputs: []inputInfo{")
   400  				for _, p := range s {
   401  					r := v.reg.inputs[p.val]
   402  					fmt.Fprintf(w, "{%d,%d},%s\n", p.val, r, a.regMaskComment(r))
   403  				}
   404  				fmt.Fprintln(w, "},")
   405  			}
   406  
   407  			if v.reg.clobbers > 0 {
   408  				fmt.Fprintf(w, "clobbers: %d,%s\n", v.reg.clobbers, a.regMaskComment(v.reg.clobbers))
   409  			}
   410  			if v.reg.clobbersArg0 {
   411  				fmt.Fprintf(w, "clobbersArg0: true,\n")
   412  			}
   413  			if v.reg.clobbersArg1 {
   414  				fmt.Fprintf(w, "clobbersArg1: true,\n")
   415  			}
   416  
   417  			// reg outputs
   418  			s = s[:0]
   419  			for i, r := range v.reg.outputs {
   420  				s = append(s, intPair{countRegs(r), i})
   421  			}
   422  			if len(s) > 0 {
   423  				sort.Sort(byKey(s))
   424  				fmt.Fprintln(w, "outputs: []outputInfo{")
   425  				for _, p := range s {
   426  					r := v.reg.outputs[p.val]
   427  					fmt.Fprintf(w, "{%d,%d},%s\n", p.val, r, a.regMaskComment(r))
   428  				}
   429  				fmt.Fprintln(w, "},")
   430  			}
   431  			fmt.Fprintln(w, "},") // close reg info
   432  			fmt.Fprintln(w, "},") // close op
   433  		}
   434  	}
   435  	fmt.Fprintln(w, "}")
   436  
   437  	fmt.Fprintln(w, "func (o Op) Asm() obj.As {return opcodeTable[o].asm}")
   438  	fmt.Fprintln(w, "func (o Op) Scale() int16 {return int16(opcodeTable[o].scale)}")
   439  
   440  	// generate op string method
   441  	fmt.Fprintln(w, "func (o Op) String() string {return opcodeTable[o].name }")
   442  
   443  	fmt.Fprintln(w, "func (o Op) SymEffect() SymEffect { return opcodeTable[o].symEffect }")
   444  	fmt.Fprintln(w, "func (o Op) IsCall() bool { return opcodeTable[o].call }")
   445  	fmt.Fprintln(w, "func (o Op) IsTailCall() bool { return opcodeTable[o].tailCall }")
   446  	fmt.Fprintln(w, "func (o Op) HasSideEffects() bool { return opcodeTable[o].hasSideEffects }")
   447  	fmt.Fprintln(w, "func (o Op) UnsafePoint() bool { return opcodeTable[o].unsafePoint }")
   448  	fmt.Fprintln(w, "func (o Op) ResultInArg0() bool { return opcodeTable[o].resultInArg0 }")
   449  
   450  	// generate registers
   451  	for _, a := range archs {
   452  		if a.generic {
   453  			continue
   454  		}
   455  		fmt.Fprintf(w, "var registers%s = [...]Register {\n", a.name)
   456  		num := map[string]int8{}
   457  		for i, r := range a.regnames {
   458  			num[r] = int8(i)
   459  			pkg := a.pkg[len("cmd/internal/obj/"):]
   460  			var objname string // name in cmd/internal/obj/$ARCH
   461  			switch r {
   462  			case "SB":
   463  				// SB isn't a real register.  cmd/internal/obj expects 0 in this case.
   464  				objname = "0"
   465  			case "SP":
   466  				objname = pkg + ".REGSP"
   467  			case "g":
   468  				objname = pkg + ".REGG"
   469  			case "ZERO":
   470  				objname = pkg + ".REGZERO"
   471  			default:
   472  				objname = pkg + ".REG_" + r
   473  			}
   474  			fmt.Fprintf(w, "  {%d, %s, \"%s\"},\n", i, objname, r)
   475  		}
   476  		parameterRegisterList := func(paramNamesString string) []int8 {
   477  			paramNamesString = strings.TrimSpace(paramNamesString)
   478  			if paramNamesString == "" {
   479  				return nil
   480  			}
   481  			paramNames := strings.Split(paramNamesString, " ")
   482  			var paramRegs []int8
   483  			for _, regName := range paramNames {
   484  				if regName == "" {
   485  					// forgive extra spaces
   486  					continue
   487  				}
   488  				if regNum, ok := num[regName]; ok {
   489  					paramRegs = append(paramRegs, regNum)
   490  					delete(num, regName)
   491  				} else {
   492  					log.Fatalf("parameter register %s for architecture %s not a register name (or repeated in parameter list)", regName, a.name)
   493  				}
   494  			}
   495  			return paramRegs
   496  		}
   497  
   498  		paramIntRegs := parameterRegisterList(a.ParamIntRegNames)
   499  		paramFloatRegs := parameterRegisterList(a.ParamFloatRegNames)
   500  
   501  		fmt.Fprintln(w, "}")
   502  		fmt.Fprintf(w, "var paramIntReg%s = %#v\n", a.name, paramIntRegs)
   503  		fmt.Fprintf(w, "var paramFloatReg%s = %#v\n", a.name, paramFloatRegs)
   504  		fmt.Fprintf(w, "var gpRegMask%s = regMask(%d)\n", a.name, a.gpregmask)
   505  		fmt.Fprintf(w, "var fpRegMask%s = regMask(%d)\n", a.name, a.fpregmask)
   506  		if a.fp32regmask != 0 {
   507  			fmt.Fprintf(w, "var fp32RegMask%s = regMask(%d)\n", a.name, a.fp32regmask)
   508  		}
   509  		if a.fp64regmask != 0 {
   510  			fmt.Fprintf(w, "var fp64RegMask%s = regMask(%d)\n", a.name, a.fp64regmask)
   511  		}
   512  		fmt.Fprintf(w, "var specialRegMask%s = regMask(%d)\n", a.name, a.specialregmask)
   513  		fmt.Fprintf(w, "var framepointerReg%s = int8(%d)\n", a.name, a.framepointerreg)
   514  		fmt.Fprintf(w, "var linkReg%s = int8(%d)\n", a.name, a.linkreg)
   515  	}
   516  
   517  	// gofmt result
   518  	b := w.Bytes()
   519  	var err error
   520  	b, err = format.Source(b)
   521  	if err != nil {
   522  		fmt.Printf("%s\n", w.Bytes())
   523  		panic(err)
   524  	}
   525  
   526  	if err := os.WriteFile(outFile("opGen.go"), b, 0666); err != nil {
   527  		log.Fatalf("can't write output: %v\n", err)
   528  	}
   529  
   530  	// Check that the arch genfile handles all the arch-specific opcodes.
   531  	// This is very much a hack, but it is better than nothing.
   532  	//
   533  	// Do a single regexp pass to record all ops being handled in a map, and
   534  	// then compare that with the ops list. This is much faster than one
   535  	// regexp pass per opcode.
   536  	for _, a := range archs {
   537  		if a.genfile == "" {
   538  			continue
   539  		}
   540  
   541  		pattern := fmt.Sprintf(`\Wssa\.Op%s([a-zA-Z0-9_]+)\W`, a.name)
   542  		rxOp, err := regexp.Compile(pattern)
   543  		if err != nil {
   544  			log.Fatalf("bad opcode regexp %s: %v", pattern, err)
   545  		}
   546  
   547  		src, err := os.ReadFile(a.genfile)
   548  		if err != nil {
   549  			log.Fatalf("can't read %s: %v", a.genfile, err)
   550  		}
   551  		// Append the file of simd operations, too
   552  		if a.genSIMDfile != "" {
   553  			simdSrc, err := os.ReadFile(a.genSIMDfile)
   554  			if err != nil {
   555  				log.Fatalf("can't read %s: %v", a.genSIMDfile, err)
   556  			}
   557  			src = append(src, simdSrc...)
   558  		}
   559  
   560  		seen := make(map[string]bool, len(a.ops))
   561  		for _, m := range rxOp.FindAllSubmatch(src, -1) {
   562  			seen[string(m[1])] = true
   563  		}
   564  		for _, op := range a.ops {
   565  			if !seen[op.name] {
   566  				log.Fatalf("Op%s%s has no code generation in %s", a.name, op.name, a.genfile)
   567  			}
   568  		}
   569  	}
   570  }
   571  
   572  // Name returns the name of the architecture for use in Op* and Block* enumerations.
   573  func (a arch) Name() string {
   574  	s := a.name
   575  	if s == "generic" {
   576  		s = ""
   577  	}
   578  	return s
   579  }
   580  
   581  // countRegs returns the number of set bits in the register mask.
   582  func countRegs(r regMask) int {
   583  	return bits.OnesCount64(uint64(r))
   584  }
   585  
   586  // for sorting a pair of integers by key
   587  type intPair struct {
   588  	key, val int
   589  }
   590  type byKey []intPair
   591  
   592  func (a byKey) Len() int           { return len(a) }
   593  func (a byKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
   594  func (a byKey) Less(i, j int) bool { return a[i].key < a[j].key }
   595
View as plain text