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  		wg.Add(1)
   188  		go func() {
   189  			task()
   190  			wg.Done()
   191  		}()
   192  	}
   193  	wg.Wait()
   194  
   195  	if *memprofile != "" {
   196  		f, err := os.Create(*memprofile)
   197  		if err != nil {
   198  			log.Fatal("could not create memory profile: ", err)
   199  		}
   200  		defer f.Close()
   201  		runtime.GC() // get up-to-date statistics
   202  		if err := pprof.WriteHeapProfile(f); err != nil {
   203  			log.Fatal("could not write memory profile: ", err)
   204  		}
   205  	}
   206  }
   207  
   208  func outFile(file string) string {
   209  	return *outDir + "/" + file
   210  }
   211  
   212  func genOp() {
   213  	w := new(bytes.Buffer)
   214  	fmt.Fprintf(w, "// Code generated from _gen/*Ops.go using 'go generate'; DO NOT EDIT.\n")
   215  	fmt.Fprintln(w)
   216  	fmt.Fprintln(w, "package ssa")
   217  
   218  	fmt.Fprintln(w, "import (")
   219  	fmt.Fprintln(w, "\"cmd/internal/obj\"")
   220  	for _, a := range archs {
   221  		if a.pkg != "" {
   222  			fmt.Fprintf(w, "%q\n", a.pkg)
   223  		}
   224  	}
   225  	fmt.Fprintln(w, ")")
   226  
   227  	// generate Block* declarations
   228  	fmt.Fprintln(w, "const (")
   229  	fmt.Fprintln(w, "BlockInvalid BlockKind = iota")
   230  	for _, a := range archs {
   231  		fmt.Fprintln(w)
   232  		for _, d := range a.blocks {
   233  			fmt.Fprintf(w, "Block%s%s\n", a.Name(), d.name)
   234  		}
   235  	}
   236  	fmt.Fprintln(w, ")")
   237  
   238  	// generate block kind string method
   239  	fmt.Fprintln(w, "var blockString = [...]string{")
   240  	fmt.Fprintln(w, "BlockInvalid:\"BlockInvalid\",")
   241  	for _, a := range archs {
   242  		fmt.Fprintln(w)
   243  		for _, b := range a.blocks {
   244  			fmt.Fprintf(w, "Block%s%s:\"%s\",\n", a.Name(), b.name, b.name)
   245  		}
   246  	}
   247  	fmt.Fprintln(w, "}")
   248  	fmt.Fprintln(w, "func (k BlockKind) String() string {return blockString[k]}")
   249  
   250  	// generate block kind auxint method
   251  	fmt.Fprintln(w, "func (k BlockKind) AuxIntType() string {")
   252  	fmt.Fprintln(w, "switch k {")
   253  	for _, a := range archs {
   254  		for _, b := range a.blocks {
   255  			if b.auxIntType() == "invalid" {
   256  				continue
   257  			}
   258  			fmt.Fprintf(w, "case Block%s%s: return \"%s\"\n", a.Name(), b.name, b.auxIntType())
   259  		}
   260  	}
   261  	fmt.Fprintln(w, "}")
   262  	fmt.Fprintln(w, "return \"\"")
   263  	fmt.Fprintln(w, "}")
   264  
   265  	// generate Op* declarations
   266  	fmt.Fprintln(w, "const (")
   267  	fmt.Fprintln(w, "OpInvalid Op = iota") // make sure OpInvalid is 0.
   268  	for _, a := range archs {
   269  		fmt.Fprintln(w)
   270  		for _, v := range a.ops {
   271  			if v.name == "Invalid" {
   272  				continue
   273  			}
   274  			fmt.Fprintf(w, "Op%s%s\n", a.Name(), v.name)
   275  		}
   276  	}
   277  	fmt.Fprintln(w, ")")
   278  
   279  	// generate OpInfo table
   280  	fmt.Fprintln(w, "var opcodeTable = [...]opInfo{")
   281  	fmt.Fprintln(w, " { name: \"OpInvalid\" },")
   282  	for _, a := range archs {
   283  		fmt.Fprintln(w)
   284  
   285  		pkg := path.Base(a.pkg)
   286  		for _, v := range a.ops {
   287  			if v.name == "Invalid" {
   288  				continue
   289  			}
   290  			fmt.Fprintln(w, "{")
   291  			fmt.Fprintf(w, "name:\"%s\",\n", v.name)
   292  
   293  			// flags
   294  			if v.aux != "" {
   295  				fmt.Fprintf(w, "auxType: aux%s,\n", v.aux)
   296  			}
   297  			fmt.Fprintf(w, "argLen: %d,\n", v.argLength)
   298  
   299  			if v.rematerializeable {
   300  				if v.reg.clobbers != 0 || v.reg.clobbersArg0 || v.reg.clobbersArg1 {
   301  					log.Fatalf("%s is rematerializeable and clobbers registers", v.name)
   302  				}
   303  				if v.clobberFlags {
   304  					log.Fatalf("%s is rematerializeable and clobbers flags", v.name)
   305  				}
   306  				fmt.Fprintln(w, "rematerializeable: true,")
   307  			}
   308  			if v.commutative {
   309  				fmt.Fprintln(w, "commutative: true,")
   310  			}
   311  			if v.resultInArg0 {
   312  				fmt.Fprintln(w, "resultInArg0: true,")
   313  				// OpConvert's register mask is selected dynamically,
   314  				// so don't try to check it in the static table.
   315  				if v.name != "Convert" && v.reg.inputs[0] != v.reg.outputs[0] {
   316  					log.Fatalf("%s: input[0] and output[0] must use the same registers for %s", a.name, v.name)
   317  				}
   318  				if v.name != "Convert" && v.commutative && v.reg.inputs[1] != v.reg.outputs[0] {
   319  					log.Fatalf("%s: input[1] and output[0] must use the same registers for %s", a.name, v.name)
   320  				}
   321  			}
   322  			if v.resultNotInArgs {
   323  				fmt.Fprintln(w, "resultNotInArgs: true,")
   324  			}
   325  			if v.clobberFlags {
   326  				fmt.Fprintln(w, "clobberFlags: true,")
   327  			}
   328  			if v.needIntTemp {
   329  				fmt.Fprintln(w, "needIntTemp: true,")
   330  			}
   331  			if v.call {
   332  				fmt.Fprintln(w, "call: true,")
   333  			}
   334  			if v.tailCall {
   335  				fmt.Fprintln(w, "tailCall: true,")
   336  			}
   337  			if v.nilCheck {
   338  				fmt.Fprintln(w, "nilCheck: true,")
   339  			}
   340  			if v.faultOnNilArg0 {
   341  				fmt.Fprintln(w, "faultOnNilArg0: true,")
   342  				if v.aux != "Sym" && v.aux != "SymOff" && v.aux != "SymValAndOff" && v.aux != "Int64" && v.aux != "Int32" && v.aux != "" {
   343  					log.Fatalf("faultOnNilArg0 with aux %s not allowed", v.aux)
   344  				}
   345  			}
   346  			if v.faultOnNilArg1 {
   347  				fmt.Fprintln(w, "faultOnNilArg1: true,")
   348  				if v.aux != "Sym" && v.aux != "SymOff" && v.aux != "SymValAndOff" && v.aux != "Int64" && v.aux != "Int32" && v.aux != "" {
   349  					log.Fatalf("faultOnNilArg1 with aux %s not allowed", v.aux)
   350  				}
   351  			}
   352  			if v.hasSideEffects {
   353  				fmt.Fprintln(w, "hasSideEffects: true,")
   354  			}
   355  			if v.zeroWidth {
   356  				fmt.Fprintln(w, "zeroWidth: true,")
   357  			}
   358  			if v.fixedReg {
   359  				fmt.Fprintln(w, "fixedReg: true,")
   360  			}
   361  			if v.unsafePoint {
   362  				fmt.Fprintln(w, "unsafePoint: true,")
   363  			}
   364  			needEffect := strings.HasPrefix(v.aux, "Sym")
   365  			if v.symEffect != "" {
   366  				if !needEffect {
   367  					log.Fatalf("symEffect with aux %s not allowed", v.aux)
   368  				}
   369  				fmt.Fprintf(w, "symEffect: Sym%s,\n", strings.ReplaceAll(v.symEffect, ",", "|Sym"))
   370  			} else if needEffect {
   371  				log.Fatalf("symEffect needed for aux %s", v.aux)
   372  			}
   373  			if a.name == "generic" {
   374  				fmt.Fprintln(w, "generic:true,")
   375  				fmt.Fprintln(w, "},") // close op
   376  				// generic ops have no reg info or asm
   377  				continue
   378  			}
   379  			if v.asm != "" {
   380  				fmt.Fprintf(w, "asm: %s.A%s,\n", pkg, v.asm)
   381  			}
   382  			if v.scale != 0 {
   383  				fmt.Fprintf(w, "scale: %d,\n", v.scale)
   384  			}
   385  			fmt.Fprintln(w, "reg:regInfo{")
   386  
   387  			// Compute input allocation order. We allocate from the
   388  			// most to the least constrained input. This order guarantees
   389  			// that we will always be able to find a register.
   390  			var s []intPair
   391  			for i, r := range v.reg.inputs {
   392  				if r != 0 {
   393  					s = append(s, intPair{countRegs(r), i})
   394  				}
   395  			}
   396  			if len(s) > 0 {
   397  				sort.Sort(byKey(s))
   398  				fmt.Fprintln(w, "inputs: []inputInfo{")
   399  				for _, p := range s {
   400  					r := v.reg.inputs[p.val]
   401  					fmt.Fprintf(w, "{%d,%d},%s\n", p.val, r, a.regMaskComment(r))
   402  				}
   403  				fmt.Fprintln(w, "},")
   404  			}
   405  
   406  			if v.reg.clobbers > 0 {
   407  				fmt.Fprintf(w, "clobbers: %d,%s\n", v.reg.clobbers, a.regMaskComment(v.reg.clobbers))
   408  			}
   409  			if v.reg.clobbersArg0 {
   410  				fmt.Fprintf(w, "clobbersArg0: true,\n")
   411  			}
   412  			if v.reg.clobbersArg1 {
   413  				fmt.Fprintf(w, "clobbersArg1: true,\n")
   414  			}
   415  
   416  			// reg outputs
   417  			s = s[:0]
   418  			for i, r := range v.reg.outputs {
   419  				s = append(s, intPair{countRegs(r), i})
   420  			}
   421  			if len(s) > 0 {
   422  				sort.Sort(byKey(s))
   423  				fmt.Fprintln(w, "outputs: []outputInfo{")
   424  				for _, p := range s {
   425  					r := v.reg.outputs[p.val]
   426  					fmt.Fprintf(w, "{%d,%d},%s\n", p.val, r, a.regMaskComment(r))
   427  				}
   428  				fmt.Fprintln(w, "},")
   429  			}
   430  			fmt.Fprintln(w, "},") // close reg info
   431  			fmt.Fprintln(w, "},") // close op
   432  		}
   433  	}
   434  	fmt.Fprintln(w, "}")
   435  
   436  	fmt.Fprintln(w, "func (o Op) Asm() obj.As {return opcodeTable[o].asm}")
   437  	fmt.Fprintln(w, "func (o Op) Scale() int16 {return int16(opcodeTable[o].scale)}")
   438  
   439  	// generate op string method
   440  	fmt.Fprintln(w, "func (o Op) String() string {return opcodeTable[o].name }")
   441  
   442  	fmt.Fprintln(w, "func (o Op) SymEffect() SymEffect { return opcodeTable[o].symEffect }")
   443  	fmt.Fprintln(w, "func (o Op) IsCall() bool { return opcodeTable[o].call }")
   444  	fmt.Fprintln(w, "func (o Op) IsTailCall() bool { return opcodeTable[o].tailCall }")
   445  	fmt.Fprintln(w, "func (o Op) HasSideEffects() bool { return opcodeTable[o].hasSideEffects }")
   446  	fmt.Fprintln(w, "func (o Op) UnsafePoint() bool { return opcodeTable[o].unsafePoint }")
   447  	fmt.Fprintln(w, "func (o Op) ResultInArg0() bool { return opcodeTable[o].resultInArg0 }")
   448  
   449  	// generate registers
   450  	for _, a := range archs {
   451  		if a.generic {
   452  			continue
   453  		}
   454  		fmt.Fprintf(w, "var registers%s = [...]Register {\n", a.name)
   455  		num := map[string]int8{}
   456  		for i, r := range a.regnames {
   457  			num[r] = int8(i)
   458  			pkg := a.pkg[len("cmd/internal/obj/"):]
   459  			var objname string // name in cmd/internal/obj/$ARCH
   460  			switch r {
   461  			case "SB":
   462  				// SB isn't a real register.  cmd/internal/obj expects 0 in this case.
   463  				objname = "0"
   464  			case "SP":
   465  				objname = pkg + ".REGSP"
   466  			case "g":
   467  				objname = pkg + ".REGG"
   468  			case "ZERO":
   469  				objname = pkg + ".REGZERO"
   470  			default:
   471  				objname = pkg + ".REG_" + r
   472  			}
   473  			fmt.Fprintf(w, "  {%d, %s, \"%s\"},\n", i, objname, r)
   474  		}
   475  		parameterRegisterList := func(paramNamesString string) []int8 {
   476  			paramNamesString = strings.TrimSpace(paramNamesString)
   477  			if paramNamesString == "" {
   478  				return nil
   479  			}
   480  			paramNames := strings.Split(paramNamesString, " ")
   481  			var paramRegs []int8
   482  			for _, regName := range paramNames {
   483  				if regName == "" {
   484  					// forgive extra spaces
   485  					continue
   486  				}
   487  				if regNum, ok := num[regName]; ok {
   488  					paramRegs = append(paramRegs, regNum)
   489  					delete(num, regName)
   490  				} else {
   491  					log.Fatalf("parameter register %s for architecture %s not a register name (or repeated in parameter list)", regName, a.name)
   492  				}
   493  			}
   494  			return paramRegs
   495  		}
   496  
   497  		paramIntRegs := parameterRegisterList(a.ParamIntRegNames)
   498  		paramFloatRegs := parameterRegisterList(a.ParamFloatRegNames)
   499  
   500  		fmt.Fprintln(w, "}")
   501  		fmt.Fprintf(w, "var paramIntReg%s = %#v\n", a.name, paramIntRegs)
   502  		fmt.Fprintf(w, "var paramFloatReg%s = %#v\n", a.name, paramFloatRegs)
   503  		fmt.Fprintf(w, "var gpRegMask%s = regMask(%d)\n", a.name, a.gpregmask)
   504  		fmt.Fprintf(w, "var fpRegMask%s = regMask(%d)\n", a.name, a.fpregmask)
   505  		if a.fp32regmask != 0 {
   506  			fmt.Fprintf(w, "var fp32RegMask%s = regMask(%d)\n", a.name, a.fp32regmask)
   507  		}
   508  		if a.fp64regmask != 0 {
   509  			fmt.Fprintf(w, "var fp64RegMask%s = regMask(%d)\n", a.name, a.fp64regmask)
   510  		}
   511  		fmt.Fprintf(w, "var specialRegMask%s = regMask(%d)\n", a.name, a.specialregmask)
   512  		fmt.Fprintf(w, "var framepointerReg%s = int8(%d)\n", a.name, a.framepointerreg)
   513  		fmt.Fprintf(w, "var linkReg%s = int8(%d)\n", a.name, a.linkreg)
   514  	}
   515  
   516  	// gofmt result
   517  	b := w.Bytes()
   518  	var err error
   519  	b, err = format.Source(b)
   520  	if err != nil {
   521  		fmt.Printf("%s\n", w.Bytes())
   522  		panic(err)
   523  	}
   524  
   525  	if err := os.WriteFile(outFile("opGen.go"), b, 0666); err != nil {
   526  		log.Fatalf("can't write output: %v\n", err)
   527  	}
   528  
   529  	// Check that the arch genfile handles all the arch-specific opcodes.
   530  	// This is very much a hack, but it is better than nothing.
   531  	//
   532  	// Do a single regexp pass to record all ops being handled in a map, and
   533  	// then compare that with the ops list. This is much faster than one
   534  	// regexp pass per opcode.
   535  	for _, a := range archs {
   536  		if a.genfile == "" {
   537  			continue
   538  		}
   539  
   540  		pattern := fmt.Sprintf(`\Wssa\.Op%s([a-zA-Z0-9_]+)\W`, a.name)
   541  		rxOp, err := regexp.Compile(pattern)
   542  		if err != nil {
   543  			log.Fatalf("bad opcode regexp %s: %v", pattern, err)
   544  		}
   545  
   546  		src, err := os.ReadFile(a.genfile)
   547  		if err != nil {
   548  			log.Fatalf("can't read %s: %v", a.genfile, err)
   549  		}
   550  		// Append the file of simd operations, too
   551  		if a.genSIMDfile != "" {
   552  			simdSrc, err := os.ReadFile(a.genSIMDfile)
   553  			if err != nil {
   554  				log.Fatalf("can't read %s: %v", a.genSIMDfile, err)
   555  			}
   556  			src = append(src, simdSrc...)
   557  		}
   558  
   559  		seen := make(map[string]bool, len(a.ops))
   560  		for _, m := range rxOp.FindAllSubmatch(src, -1) {
   561  			seen[string(m[1])] = true
   562  		}
   563  		for _, op := range a.ops {
   564  			if !seen[op.name] {
   565  				log.Fatalf("Op%s%s has no code generation in %s", a.name, op.name, a.genfile)
   566  			}
   567  		}
   568  	}
   569  }
   570  
   571  // Name returns the name of the architecture for use in Op* and Block* enumerations.
   572  func (a arch) Name() string {
   573  	s := a.name
   574  	if s == "generic" {
   575  		s = ""
   576  	}
   577  	return s
   578  }
   579  
   580  // countRegs returns the number of set bits in the register mask.
   581  func countRegs(r regMask) int {
   582  	return bits.OnesCount64(uint64(r))
   583  }
   584  
   585  // for sorting a pair of integers by key
   586  type intPair struct {
   587  	key, val int
   588  }
   589  type byKey []intPair
   590  
   591  func (a byKey) Len() int           { return len(a) }
   592  func (a byKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
   593  func (a byKey) Less(i, j int) bool { return a[i].key < a[j].key }
   594
View as plain text