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  	ops                []opData
    36  	blocks             []blockData
    37  	regnames           []string
    38  	ParamIntRegNames   string
    39  	ParamFloatRegNames string
    40  	gpregmask          regMask
    41  	fpregmask          regMask
    42  	fp32regmask        regMask
    43  	fp64regmask        regMask
    44  	specialregmask     regMask
    45  	framepointerreg    int8
    46  	linkreg            int8
    47  	generic            bool
    48  	imports            []string
    49  }
    50  
    51  type opData struct {
    52  	name              string
    53  	reg               regInfo
    54  	asm               string
    55  	typ               string // default result type
    56  	aux               string
    57  	rematerializeable bool
    58  	argLength         int32  // number of arguments, if -1, then this operation has a variable number of arguments
    59  	commutative       bool   // this operation is commutative on its first 2 arguments (e.g. addition)
    60  	resultInArg0      bool   // (first, if a tuple) output of v and v.Args[0] must be allocated to the same register
    61  	resultNotInArgs   bool   // outputs must not be allocated to the same registers as inputs
    62  	clobberFlags      bool   // this op clobbers flags register
    63  	needIntTemp       bool   // need a temporary free integer register
    64  	call              bool   // is a function call
    65  	tailCall          bool   // is a tail call
    66  	nilCheck          bool   // this op is a nil check on arg0
    67  	faultOnNilArg0    bool   // this op will fault if arg0 is nil (and aux encodes a small offset)
    68  	faultOnNilArg1    bool   // this op will fault if arg1 is nil (and aux encodes a small offset)
    69  	hasSideEffects    bool   // for "reasons", not to be eliminated.  E.g., atomic store, #19182.
    70  	zeroWidth         bool   // op never translates into any machine code. example: copy, which may sometimes translate to machine code, is not zero-width.
    71  	unsafePoint       bool   // this op is an unsafe point, i.e. not safe for async preemption
    72  	fixedReg          bool   // this op will be assigned a fixed register
    73  	symEffect         string // effect this op has on symbol in aux
    74  	scale             uint8  // amd64/386 indexed load scale
    75  }
    76  
    77  type blockData struct {
    78  	name     string // the suffix for this block ("EQ", "LT", etc.)
    79  	controls int    // the number of control values this type of block requires
    80  	aux      string // the type of the Aux/AuxInt value, if any
    81  }
    82  
    83  type regInfo struct {
    84  	// inputs[i] encodes the set of registers allowed for the i'th input.
    85  	// Inputs that don't use registers (flags, memory, etc.) should be 0.
    86  	inputs []regMask
    87  	// clobbers encodes the set of registers that are overwritten by
    88  	// the instruction (other than the output registers).
    89  	clobbers regMask
    90  	// Instruction clobbers the register containing input 0.
    91  	clobbersArg0 bool
    92  	// Instruction clobbers the register containing input 1.
    93  	clobbersArg1 bool
    94  	// outputs[i] encodes the set of registers allowed for the i'th output.
    95  	outputs []regMask
    96  }
    97  
    98  type regMask uint64
    99  
   100  func (a arch) regMaskComment(r regMask) string {
   101  	var buf strings.Builder
   102  	for i := uint64(0); r != 0; i++ {
   103  		if r&1 != 0 {
   104  			if buf.Len() == 0 {
   105  				buf.WriteString(" //")
   106  			}
   107  			buf.WriteString(" ")
   108  			buf.WriteString(a.regnames[i])
   109  		}
   110  		r >>= 1
   111  	}
   112  	return buf.String()
   113  }
   114  
   115  var archs []arch
   116  
   117  var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to `file`")
   118  var memprofile = flag.String("memprofile", "", "write memory profile to `file`")
   119  var tracefile = flag.String("trace", "", "write trace to `file`")
   120  var outDir = flag.String("outdir", "..", "directory in which to write generated files")
   121  
   122  func main() {
   123  	flag.Parse()
   124  	if *cpuprofile != "" {
   125  		f, err := os.Create(*cpuprofile)
   126  		if err != nil {
   127  			log.Fatal("could not create CPU profile: ", err)
   128  		}
   129  		defer f.Close()
   130  		if err := pprof.StartCPUProfile(f); err != nil {
   131  			log.Fatal("could not start CPU profile: ", err)
   132  		}
   133  		defer pprof.StopCPUProfile()
   134  	}
   135  	if *tracefile != "" {
   136  		f, err := os.Create(*tracefile)
   137  		if err != nil {
   138  			log.Fatalf("failed to create trace output file: %v", err)
   139  		}
   140  		defer func() {
   141  			if err := f.Close(); err != nil {
   142  				log.Fatalf("failed to close trace file: %v", err)
   143  			}
   144  		}()
   145  
   146  		if err := trace.Start(f); err != nil {
   147  			log.Fatalf("failed to start trace: %v", err)
   148  		}
   149  		defer trace.Stop()
   150  	}
   151  
   152  	if *outDir != ".." {
   153  		err := os.MkdirAll(*outDir, 0755)
   154  		if err != nil {
   155  			log.Fatalf("failed to create output directory: %v", err)
   156  		}
   157  	}
   158  
   159  	slices.SortFunc(archs, func(a, b arch) int {
   160  		return strings.Compare(a.name, b.name)
   161  	})
   162  
   163  	// The generate tasks are run concurrently, since they are CPU-intensive
   164  	// that can easily make use of many cores on a machine.
   165  	//
   166  	// Note that there is no limit on the concurrency at the moment. On a
   167  	// four-core laptop at the time of writing, peak RSS usually reaches
   168  	// ~200MiB, which seems doable by practically any machine nowadays. If
   169  	// that stops being the case, we can cap this func to a fixed number of
   170  	// architectures being generated at once.
   171  
   172  	tasks := []func(){
   173  		genOp,
   174  		genAllocators,
   175  	}
   176  	for _, a := range archs {
   177  		a := a // the funcs are ran concurrently at a later time
   178  		tasks = append(tasks, func() {
   179  			genRules(a)
   180  			genSplitLoadRules(a)
   181  			genLateLowerRules(a)
   182  		})
   183  	}
   184  	var wg sync.WaitGroup
   185  	for _, task := range tasks {
   186  		task := task
   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  		seen := make(map[string]bool, len(a.ops))
   551  		for _, m := range rxOp.FindAllSubmatch(src, -1) {
   552  			seen[string(m[1])] = true
   553  		}
   554  		for _, op := range a.ops {
   555  			if !seen[op.name] {
   556  				log.Fatalf("Op%s%s has no code generation in %s", a.name, op.name, a.genfile)
   557  			}
   558  		}
   559  	}
   560  }
   561  
   562  // Name returns the name of the architecture for use in Op* and Block* enumerations.
   563  func (a arch) Name() string {
   564  	s := a.name
   565  	if s == "generic" {
   566  		s = ""
   567  	}
   568  	return s
   569  }
   570  
   571  // countRegs returns the number of set bits in the register mask.
   572  func countRegs(r regMask) int {
   573  	return bits.OnesCount64(uint64(r))
   574  }
   575  
   576  // for sorting a pair of integers by key
   577  type intPair struct {
   578  	key, val int
   579  }
   580  type byKey []intPair
   581  
   582  func (a byKey) Len() int           { return len(a) }
   583  func (a byKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
   584  func (a byKey) Less(i, j int) bool { return a[i].key < a[j].key }
   585
View as plain text