src/cmd/compile/internal/ssa/gen/rulegen.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 //go:build gen
   6 // +build gen
   7
   8 // This program generates Go code that applies rewrite rules to a Value.
   9 // The generated code implements a function of type func (v *Value) bool
  10 // which reports whether if did something.
  11 // Ideas stolen from Swift: http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-2000-2.html
  12
  13 package main
  14
  15 import (
  16         "bufio"
  17         "bytes"
  18         "flag"
  19         "fmt"
  20         "go/ast"
  21         "go/format"
  22         "go/parser"
  23         "go/printer"
  24         "go/token"
  25         "io"
  26         "io/ioutil"
  27         "log"
  28         "os"
  29         "path"
  30         "regexp"
  31         "sort"
  32         "strconv"
  33         "strings"
  34
  35         "golang.org/x/tools/go/ast/astutil"
  36 )
  37
  38 // rule syntax:
  39 //  sexpr [&& extra conditions] => [@block] sexpr
  40 //
  41 // sexpr are s-expressions (lisp-like parenthesized groupings)
  42 // sexpr ::= [variable:](opcode sexpr*)
  43 //         | variable
  44 //         | <type>
  45 //         | [auxint]
  46 //         | {aux}
  47 //
  48 // aux      ::= variable | {code}
  49 // type     ::= variable | {code}
  50 // variable ::= some token
  51 // opcode   ::= one of the opcodes from the *Ops.go files
  52
  53 // special rules: trailing ellipsis "..." (in the outermost sexpr?) must match on both sides of a rule.
  54 //                trailing three underscore "___" in the outermost match sexpr indicate the presence of
  55 //                   extra ignored args that need not appear in the replacement
  56
  57 // extra conditions is just a chunk of Go that evaluates to a boolean. It may use
  58 // variables declared in the matching tsexpr. The variable "v" is predefined to be
  59 // the value matched by the entire rule.
  60
  61 // If multiple rules match, the first one in file order is selected.
  62
  63 var (
  64         genLog  = flag.Bool("log", false, "generate code that logs; for debugging only")
  65         addLine = flag.Bool("line", false, "add line number comment to generated rules; for debugging only")
  66 )
  67
  68 type Rule struct {
  69         Rule string
  70         Loc  string // file name & line number
  71 }
  72
  73 func (r Rule) String() string {
  74         return fmt.Sprintf("rule %q at %s", r.Rule, r.Loc)
  75 }
  76
  77 func normalizeSpaces(s string) string {
  78         return strings.Join(strings.Fields(strings.TrimSpace(s)), " ")
  79 }
  80
  81 // parse returns the matching part of the rule, additional conditions, and the result.
  82 func (r Rule) parse() (match, cond, result string) {
  83         s := strings.Split(r.Rule, "=>")
  84         match = normalizeSpaces(s[0])
  85         result = normalizeSpaces(s[1])
  86         cond = ""
  87         if i := strings.Index(match, "&&"); i >= 0 {
  88                 cond = normalizeSpaces(match[i+2:])
  89                 match = normalizeSpaces(match[:i])
  90         }
  91         return match, cond, result
  92 }
  93
  94 func genRules(arch arch)          { genRulesSuffix(arch, "") }
  95 func genSplitLoadRules(arch arch) { genRulesSuffix(arch, "splitload") }
  96
  97 func genRulesSuffix(arch arch, suff string) {
  98         // Open input file.
  99         text, err := os.Open(arch.name + suff + ".rules")
 100         if err != nil {
 101                 if suff == "" {
 102                         // All architectures must have a plain rules file.
 103                         log.Fatalf("can't read rule file: %v", err)
 104                 }
 105                 // Some architectures have bonus rules files that others don't share. That's fine.
 106                 return
 107         }
 108
 109         // oprules contains a list of rules for each block and opcode
 110         blockrules := map[string][]Rule{}
 111         oprules := map[string][]Rule{}
 112
 113         // read rule file
 114         scanner := bufio.NewScanner(text)
 115         rule := ""
 116         var lineno int
 117         var ruleLineno int // line number of "=>"
 118         for scanner.Scan() {
 119                 lineno++
 120                 line := scanner.Text()
 121                 if i := strings.Index(line, "//"); i >= 0 {
 122                         // Remove comments. Note that this isn't string safe, so
 123                         // it will truncate lines with // inside strings. Oh well.
 124                         line = line[:i]
 125                 }
 126                 rule += " " + line
 127                 rule = strings.TrimSpace(rule)
 128                 if rule == "" {
 129                         continue
 130                 }
 131                 if !strings.Contains(rule, "=>") {
 132                         continue
 133                 }
 134                 if ruleLineno == 0 {
 135                         ruleLineno = lineno
 136                 }
 137                 if strings.HasSuffix(rule, "=>") {
 138                         continue // continue on the next line
 139                 }
 140                 if n := balance(rule); n > 0 {
 141                         continue // open parentheses remain, continue on the next line
 142                 } else if n < 0 {
 143                         break // continuing the line can't help, and it will only make errors worse
 144                 }
 145
 146                 loc := fmt.Sprintf("%s%s.rules:%d", arch.name, suff, ruleLineno)
 147                 for _, rule2 := range expandOr(rule) {
 148                         r := Rule{Rule: rule2, Loc: loc}
 149                         if rawop := strings.Split(rule2, " ")[0][1:]; isBlock(rawop, arch) {
 150                                 blockrules[rawop] = append(blockrules[rawop], r)
 151                                 continue
 152                         }
 153                         // Do fancier value op matching.
 154                         match, _, _ := r.parse()
 155                         op, oparch, _, _, _, _ := parseValue(match, arch, loc)
 156                         opname := fmt.Sprintf("Op%s%s", oparch, op.name)
 157                         oprules[opname] = append(oprules[opname], r)
 158                 }
 159                 rule = ""
 160                 ruleLineno = 0
 161         }
 162         if err := scanner.Err(); err != nil {
 163                 log.Fatalf("scanner failed: %v\n", err)
 164         }
 165         if balance(rule) != 0 {
 166                 log.Fatalf("%s.rules:%d: unbalanced rule: %v\n", arch.name, lineno, rule)
 167         }
 168
 169         // Order all the ops.
 170         var ops []string
 171         for op := range oprules {
 172                 ops = append(ops, op)
 173         }
 174         sort.Strings(ops)
 175
 176         genFile := &File{Arch: arch, Suffix: suff}
 177         // Main rewrite routine is a switch on v.Op.
 178         fn := &Func{Kind: "Value", ArgLen: -1}
 179
 180         sw := &Switch{Expr: exprf("v.Op")}
 181         for _, op := range ops {
 182                 eop, ok := parseEllipsisRules(oprules[op], arch)
 183                 if ok {
 184                         if strings.Contains(oprules[op][0].Rule, "=>") && opByName(arch, op).aux != opByName(arch, eop).aux {
 185                                 panic(fmt.Sprintf("can't use ... for ops that have different aux types: %s and %s", op, eop))
 186                         }
 187                         swc := &Case{Expr: exprf("%s", op)}
 188                         swc.add(stmtf("v.Op = %s", eop))
 189                         swc.add(stmtf("return true"))
 190                         sw.add(swc)
 191                         continue
 192                 }
 193
 194                 swc := &Case{Expr: exprf("%s", op)}
 195                 swc.add(stmtf("return rewriteValue%s%s_%s(v)", arch.name, suff, op))
 196                 sw.add(swc)
 197         }
 198         if len(sw.List) > 0 { // skip if empty
 199                 fn.add(sw)
 200         }
 201         fn.add(stmtf("return false"))
 202         genFile.add(fn)
 203
 204         // Generate a routine per op. Note that we don't make one giant routine
 205         // because it is too big for some compilers.
 206         for _, op := range ops {
 207                 rules := oprules[op]
 208                 _, ok := parseEllipsisRules(oprules[op], arch)
 209                 if ok {
 210                         continue
 211                 }
 212
 213                 // rr is kept between iterations, so that each rule can check
 214                 // that the previous rule wasn't unconditional.
 215                 var rr *RuleRewrite
 216                 fn := &Func{
 217                         Kind:   "Value",
 218                         Suffix: fmt.Sprintf("_%s", op),
 219                         ArgLen: opByName(arch, op).argLength,
 220                 }
 221                 fn.add(declReserved("b", "v.Block"))
 222                 fn.add(declReserved("config", "b.Func.Config"))
 223                 fn.add(declReserved("fe", "b.Func.fe"))
 224                 fn.add(declReserved("typ", "&b.Func.Config.Types"))
 225                 for _, rule := range rules {
 226                         if rr != nil && !rr.CanFail {
 227                                 log.Fatalf("unconditional rule %s is followed by other rules", rr.Match)
 228                         }
 229                         rr = &RuleRewrite{Loc: rule.Loc}
 230                         rr.Match, rr.Cond, rr.Result = rule.parse()
 231                         pos, _ := genMatch(rr, arch, rr.Match, fn.ArgLen >= 0)
 232                         if pos == "" {
 233                                 pos = "v.Pos"
 234                         }
 235                         if rr.Cond != "" {
 236                                 rr.add(breakf("!(%s)", rr.Cond))
 237                         }
 238                         genResult(rr, arch, rr.Result, pos)
 239                         if *genLog {
 240                                 rr.add(stmtf("logRule(%q)", rule.Loc))
 241                         }
 242                         fn.add(rr)
 243                 }
 244                 if rr.CanFail {
 245                         fn.add(stmtf("return false"))
 246                 }
 247                 genFile.add(fn)
 248         }
 249
 250         // Generate block rewrite function. There are only a few block types
 251         // so we can make this one function with a switch.
 252         fn = &Func{Kind: "Block"}
 253         fn.add(declReserved("config", "b.Func.Config"))
 254         fn.add(declReserved("typ", "&b.Func.Config.Types"))
 255
 256         sw = &Switch{Expr: exprf("b.Kind")}
 257         ops = ops[:0]
 258         for op := range blockrules {
 259                 ops = append(ops, op)
 260         }
 261         sort.Strings(ops)
 262         for _, op := range ops {
 263                 name, data := getBlockInfo(op, arch)
 264                 swc := &Case{Expr: exprf("%s", name)}
 265                 for _, rule := range blockrules[op] {
 266                         swc.add(genBlockRewrite(rule, arch, data))
 267                 }
 268                 sw.add(swc)
 269         }
 270         if len(sw.List) > 0 { // skip if empty
 271                 fn.add(sw)
 272         }
 273         fn.add(stmtf("return false"))
 274         genFile.add(fn)
 275
 276         // Remove unused imports and variables.
 277         buf := new(bytes.Buffer)
 278         fprint(buf, genFile)
 279         fset := token.NewFileSet()
 280         file, err := parser.ParseFile(fset, "", buf, parser.ParseComments)
 281         if err != nil {
 282                 filename := fmt.Sprintf("%s_broken.go", arch.name)
 283                 if err := ioutil.WriteFile(filename, buf.Bytes(), 0644); err != nil {
 284                         log.Printf("failed to dump broken code to %s: %v", filename, err)
 285                 } else {
 286                         log.Printf("dumped broken code to %s", filename)
 287                 }
 288                 log.Fatalf("failed to parse generated code for arch %s: %v", arch.name, err)
 289         }
 290         tfile := fset.File(file.Pos())
 291
 292         // First, use unusedInspector to find the unused declarations by their
 293         // start position.
 294         u := unusedInspector{unused: make(map[token.Pos]bool)}
 295         u.node(file)
 296
 297         // Then, delete said nodes via astutil.Apply.
 298         pre := func(c *astutil.Cursor) bool {
 299                 node := c.Node()
 300                 if node == nil {
 301                         return true
 302                 }
 303                 if u.unused[node.Pos()] {
 304                         c.Delete()
 305                         // Unused imports and declarations use exactly
 306                         // one line. Prevent leaving an empty line.
 307                         tfile.MergeLine(tfile.Position(node.Pos()).Line)
 308                         return false
 309                 }
 310                 return true
 311         }
 312         post := func(c *astutil.Cursor) bool {
 313                 switch node := c.Node().(type) {
 314                 case *ast.GenDecl:
 315                         if len(node.Specs) == 0 {
 316                                 // Don't leave a broken or empty GenDecl behind,
 317                                 // such as "import ()".
 318                                 c.Delete()
 319                         }
 320                 }
 321                 return true
 322         }
 323         file = astutil.Apply(file, pre, post).(*ast.File)
 324
 325         // Write the well-formatted source to file
 326         f, err := os.Create("../rewrite" + arch.name + suff + ".go")
 327         if err != nil {
 328                 log.Fatalf("can't write output: %v", err)
 329         }
 330         defer f.Close()
 331         // gofmt result; use a buffered writer, as otherwise go/format spends
 332         // far too much time in syscalls.
 333         bw := bufio.NewWriter(f)
 334         if err := format.Node(bw, fset, file); err != nil {
 335                 log.Fatalf("can't format output: %v", err)
 336         }
 337         if err := bw.Flush(); err != nil {
 338                 log.Fatalf("can't write output: %v", err)
 339         }
 340         if err := f.Close(); err != nil {
 341                 log.Fatalf("can't write output: %v", err)
 342         }
 343 }
 344
 345 // unusedInspector can be used to detect unused variables and imports in an
 346 // ast.Node via its node method. The result is available in the "unused" map.
 347 //
 348 // note that unusedInspector is lazy and best-effort; it only supports the node
 349 // types and patterns used by the rulegen program.
 350 type unusedInspector struct {
 351         // scope is the current scope, which can never be nil when a declaration
 352         // is encountered. That is, the unusedInspector.node entrypoint should
 353         // generally be an entire file or block.
 354         scope *scope
 355
 356         // unused is the resulting set of unused declared names, indexed by the
 357         // starting position of the node that declared the name.
 358         unused map[token.Pos]bool
 359
 360         // defining is the object currently being defined; this is useful so
 361         // that if "foo := bar" is unused and removed, we can then detect if
 362         // "bar" becomes unused as well.
 363         defining *object
 364 }
 365
 366 // scoped opens a new scope when called, and returns a function which closes
 367 // that same scope. When a scope is closed, unused variables are recorded.
 368 func (u *unusedInspector) scoped() func() {
 369         outer := u.scope
 370         u.scope = &scope{outer: outer, objects: map[string]*object{}}
 371         return func() {
 372                 for anyUnused := true; anyUnused; {
 373                         anyUnused = false
 374                         for _, obj := range u.scope.objects {
 375                                 if obj.numUses > 0 {
 376                                         continue
 377                                 }
 378                                 u.unused[obj.pos] = true
 379                                 for _, used := range obj.used {
 380                                         if used.numUses--; used.numUses == 0 {
 381                                                 anyUnused = true
 382                                         }
 383                                 }
 384                                 // We've decremented numUses for each of the
 385                                 // objects in used. Zero this slice too, to keep
 386                                 // everything consistent.
 387                                 obj.used = nil
 388                         }
 389                 }
 390                 u.scope = outer
 391         }
 392 }
 393
 394 func (u *unusedInspector) exprs(list []ast.Expr) {
 395         for _, x := range list {
 396                 u.node(x)
 397         }
 398 }
 399
 400 func (u *unusedInspector) node(node ast.Node) {
 401         switch node := node.(type) {
 402         case *ast.File:
 403                 defer u.scoped()()
 404                 for _, decl := range node.Decls {
 405                         u.node(decl)
 406                 }
 407         case *ast.GenDecl:
 408                 for _, spec := range node.Specs {
 409                         u.node(spec)
 410                 }
 411         case *ast.ImportSpec:
 412                 impPath, _ := strconv.Unquote(node.Path.Value)
 413                 name := path.Base(impPath)
 414                 u.scope.objects[name] = &object{
 415                         name: name,
 416                         pos:  node.Pos(),
 417                 }
 418         case *ast.FuncDecl:
 419                 u.node(node.Type)
 420                 if node.Body != nil {
 421                         u.node(node.Body)
 422                 }
 423         case *ast.FuncType:
 424                 if node.Params != nil {
 425                         u.node(node.Params)
 426                 }
 427                 if node.Results != nil {
 428                         u.node(node.Results)
 429                 }
 430         case *ast.FieldList:
 431                 for _, field := range node.List {
 432                         u.node(field)
 433                 }
 434         case *ast.Field:
 435                 u.node(node.Type)
 436
 437         // statements
 438
 439         case *ast.BlockStmt:
 440                 defer u.scoped()()
 441                 for _, stmt := range node.List {
 442                         u.node(stmt)
 443                 }
 444         case *ast.DeclStmt:
 445                 u.node(node.Decl)
 446         case *ast.IfStmt:
 447                 if node.Init != nil {
 448                         u.node(node.Init)
 449                 }
 450                 u.node(node.Cond)
 451                 u.node(node.Body)
 452                 if node.Else != nil {
 453                         u.node(node.Else)
 454                 }
 455         case *ast.ForStmt:
 456                 if node.Init != nil {
 457                         u.node(node.Init)
 458                 }
 459                 if node.Cond != nil {
 460                         u.node(node.Cond)
 461                 }
 462                 if node.Post != nil {
 463                         u.node(node.Post)
 464                 }
 465                 u.node(node.Body)
 466         case *ast.SwitchStmt:
 467                 if node.Init != nil {
 468                         u.node(node.Init)
 469                 }
 470                 if node.Tag != nil {
 471                         u.node(node.Tag)
 472                 }
 473                 u.node(node.Body)
 474         case *ast.CaseClause:
 475                 u.exprs(node.List)
 476                 defer u.scoped()()
 477                 for _, stmt := range node.Body {
 478                         u.node(stmt)
 479                 }
 480         case *ast.BranchStmt:
 481         case *ast.ExprStmt:
 482                 u.node(node.X)
 483         case *ast.AssignStmt:
 484                 if node.Tok != token.DEFINE {
 485                         u.exprs(node.Rhs)
 486                         u.exprs(node.Lhs)
 487                         break
 488                 }
 489                 lhs := node.Lhs
 490                 if len(lhs) == 2 && lhs[1].(*ast.Ident).Name == "_" {
 491                         lhs = lhs[:1]
 492                 }
 493                 if len(lhs) != 1 {
 494                         panic("no support for := with multiple names")
 495                 }
 496
 497                 name := lhs[0].(*ast.Ident)
 498                 obj := &object{
 499                         name: name.Name,
 500                         pos:  name.NamePos,
 501                 }
 502
 503                 old := u.defining
 504                 u.defining = obj
 505                 u.exprs(node.Rhs)
 506                 u.defining = old
 507
 508                 u.scope.objects[name.Name] = obj
 509         case *ast.ReturnStmt:
 510                 u.exprs(node.Results)
 511         case *ast.IncDecStmt:
 512                 u.node(node.X)
 513
 514         // expressions
 515
 516         case *ast.CallExpr:
 517                 u.node(node.Fun)
 518                 u.exprs(node.Args)
 519         case *ast.SelectorExpr:
 520                 u.node(node.X)
 521         case *ast.UnaryExpr:
 522                 u.node(node.X)
 523         case *ast.BinaryExpr:
 524                 u.node(node.X)
 525                 u.node(node.Y)
 526         case *ast.StarExpr:
 527                 u.node(node.X)
 528         case *ast.ParenExpr:
 529                 u.node(node.X)
 530         case *ast.IndexExpr:
 531                 u.node(node.X)
 532                 u.node(node.Index)
 533         case *ast.TypeAssertExpr:
 534                 u.node(node.X)
 535                 u.node(node.Type)
 536         case *ast.Ident:
 537                 if obj := u.scope.Lookup(node.Name); obj != nil {
 538                         obj.numUses++
 539                         if u.defining != nil {
 540                                 u.defining.used = append(u.defining.used, obj)
 541                         }
 542                 }
 543         case *ast.BasicLit:
 544         case *ast.ValueSpec:
 545                 u.exprs(node.Values)
 546         default:
 547                 panic(fmt.Sprintf("unhandled node: %T", node))
 548         }
 549 }
 550
 551 // scope keeps track of a certain scope and its declared names, as well as the
 552 // outer (parent) scope.
 553 type scope struct {
 554         outer   *scope             // can be nil, if this is the top-level scope
 555         objects map[string]*object // indexed by each declared name
 556 }
 557
 558 func (s *scope) Lookup(name string) *object {
 559         if obj := s.objects[name]; obj != nil {
 560                 return obj
 561         }
 562         if s.outer == nil {
 563                 return nil
 564         }
 565         return s.outer.Lookup(name)
 566 }
 567
 568 // object keeps track of a declared name, such as a variable or import.
 569 type object struct {
 570         name string
 571         pos  token.Pos // start position of the node declaring the object
 572
 573         numUses int       // number of times this object is used
 574         used    []*object // objects that its declaration makes use of
 575 }
 576
 577 func fprint(w io.Writer, n Node) {
 578         switch n := n.(type) {
 579         case *File:
 580                 file := n
 581                 seenRewrite := make(map[[3]string]string)
 582                 fmt.Fprintf(w, "// Code generated from gen/%s%s.rules; DO NOT EDIT.\n", n.Arch.name, n.Suffix)
 583                 fmt.Fprintf(w, "// generated with: cd gen; go run *.go\n")
 584                 fmt.Fprintf(w, "\npackage ssa\n")
 585                 for _, path := range append([]string{
 586                         "fmt",
 587                         "internal/buildcfg",
 588                         "math",
 589                         "cmd/internal/obj",
 590                         "cmd/compile/internal/base",
 591                         "cmd/compile/internal/types",
 592                 }, n.Arch.imports...) {
 593                         fmt.Fprintf(w, "import %q\n", path)
 594                 }
 595                 for _, f := range n.List {
 596                         f := f.(*Func)
 597                         fmt.Fprintf(w, "func rewrite%s%s%s%s(", f.Kind, n.Arch.name, n.Suffix, f.Suffix)
 598                         fmt.Fprintf(w, "%c *%s) bool {\n", strings.ToLower(f.Kind)[0], f.Kind)
 599                         if f.Kind == "Value" && f.ArgLen > 0 {
 600                                 for i := f.ArgLen - 1; i >= 0; i-- {
 601                                         fmt.Fprintf(w, "v_%d := v.Args[%d]\n", i, i)
 602                                 }
 603                         }
 604                         for _, n := range f.List {
 605                                 fprint(w, n)
 606
 607                                 if rr, ok := n.(*RuleRewrite); ok {
 608                                         k := [3]string{
 609                                                 normalizeMatch(rr.Match, file.Arch),
 610                                                 normalizeWhitespace(rr.Cond),
 611                                                 normalizeWhitespace(rr.Result),
 612                                         }
 613                                         if prev, ok := seenRewrite[k]; ok {
 614                                                 log.Fatalf("duplicate rule %s, previously seen at %s\n", rr.Loc, prev)
 615                                         }
 616                                         seenRewrite[k] = rr.Loc
 617                                 }
 618                         }
 619                         fmt.Fprintf(w, "}\n")
 620                 }
 621         case *Switch:
 622                 fmt.Fprintf(w, "switch ")
 623                 fprint(w, n.Expr)
 624                 fmt.Fprintf(w, " {\n")
 625                 for _, n := range n.List {
 626                         fprint(w, n)
 627                 }
 628                 fmt.Fprintf(w, "}\n")
 629         case *Case:
 630                 fmt.Fprintf(w, "case ")
 631                 fprint(w, n.Expr)
 632                 fmt.Fprintf(w, ":\n")
 633                 for _, n := range n.List {
 634                         fprint(w, n)
 635                 }
 636         case *RuleRewrite:
 637                 if *addLine {
 638                         fmt.Fprintf(w, "// %s\n", n.Loc)
 639                 }
 640                 fmt.Fprintf(w, "// match: %s\n", n.Match)
 641                 if n.Cond != "" {
 642                         fmt.Fprintf(w, "// cond: %s\n", n.Cond)
 643                 }
 644                 fmt.Fprintf(w, "// result: %s\n", n.Result)
 645                 fmt.Fprintf(w, "for %s {\n", n.Check)
 646                 nCommutative := 0
 647                 for _, n := range n.List {
 648                         if b, ok := n.(*CondBreak); ok {
 649                                 b.InsideCommuteLoop = nCommutative > 0
 650                         }
 651                         fprint(w, n)
 652                         if loop, ok := n.(StartCommuteLoop); ok {
 653                                 if nCommutative != loop.Depth {
 654                                         panic("mismatch commute loop depth")
 655                                 }
 656                                 nCommutative++
 657                         }
 658                 }
 659                 fmt.Fprintf(w, "return true\n")
 660                 for i := 0; i < nCommutative; i++ {
 661                         fmt.Fprintln(w, "}")
 662                 }
 663                 if n.CommuteDepth > 0 && n.CanFail {
 664                         fmt.Fprint(w, "break\n")
 665                 }
 666                 fmt.Fprintf(w, "}\n")
 667         case *Declare:
 668                 fmt.Fprintf(w, "%s := ", n.Name)
 669                 fprint(w, n.Value)
 670                 fmt.Fprintln(w)
 671         case *CondBreak:
 672                 fmt.Fprintf(w, "if ")
 673                 fprint(w, n.Cond)
 674                 fmt.Fprintf(w, " {\n")
 675                 if n.InsideCommuteLoop {
 676                         fmt.Fprintf(w, "continue")
 677                 } else {
 678                         fmt.Fprintf(w, "break")
 679                 }
 680                 fmt.Fprintf(w, "\n}\n")
 681         case ast.Node:
 682                 printConfig.Fprint(w, emptyFset, n)
 683                 if _, ok := n.(ast.Stmt); ok {
 684                         fmt.Fprintln(w)
 685                 }
 686         case StartCommuteLoop:
 687                 fmt.Fprintf(w, "for _i%[1]d := 0; _i%[1]d <= 1; _i%[1]d, %[2]s_0, %[2]s_1 = _i%[1]d + 1, %[2]s_1, %[2]s_0 {\n", n.Depth, n.V)
 688         default:
 689                 log.Fatalf("cannot print %T", n)
 690         }
 691 }
 692
 693 var printConfig = printer.Config{
 694         Mode: printer.RawFormat, // we use go/format later, so skip work here
 695 }
 696
 697 var emptyFset = token.NewFileSet()
 698
 699 // Node can be a Statement or an ast.Expr.
 700 type Node interface{}
 701
 702 // Statement can be one of our high-level statement struct types, or an
 703 // ast.Stmt under some limited circumstances.
 704 type Statement interface{}
 705
 706 // BodyBase is shared by all of our statement pseudo-node types which can
 707 // contain other statements.
 708 type BodyBase struct {
 709         List    []Statement
 710         CanFail bool
 711 }
 712
 713 func (w *BodyBase) add(node Statement) {
 714         var last Statement
 715         if len(w.List) > 0 {
 716                 last = w.List[len(w.List)-1]
 717         }
 718         if node, ok := node.(*CondBreak); ok {
 719                 w.CanFail = true
 720                 if last, ok := last.(*CondBreak); ok {
 721                         // Add to the previous "if <cond> { break }" via a
 722                         // logical OR, which will save verbosity.
 723                         last.Cond = &ast.BinaryExpr{
 724                                 Op: token.LOR,
 725                                 X:  last.Cond,
 726                                 Y:  node.Cond,
 727                         }
 728                         return
 729                 }
 730         }
 731
 732         w.List = append(w.List, node)
 733 }
 734
 735 // predeclared contains globally known tokens that should not be redefined.
 736 var predeclared = map[string]bool{
 737         "nil":   true,
 738         "false": true,
 739         "true":  true,
 740 }
 741
 742 // declared reports if the body contains a Declare with the given name.
 743 func (w *BodyBase) declared(name string) bool {
 744         if predeclared[name] {
 745                 // Treat predeclared names as having already been declared.
 746                 // This lets us use nil to match an aux field or
 747                 // true and false to match an auxint field.
 748                 return true
 749         }
 750         for _, s := range w.List {
 751                 if decl, ok := s.(*Declare); ok && decl.Name == name {
 752                         return true
 753                 }
 754         }
 755         return false
 756 }
 757
 758 // These types define some high-level statement struct types, which can be used
 759 // as a Statement. This allows us to keep some node structs simpler, and have
 760 // higher-level nodes such as an entire rule rewrite.
 761 //
 762 // Note that ast.Expr is always used as-is; we don't declare our own expression
 763 // nodes.
 764 type (
 765         File struct {
 766                 BodyBase // []*Func
 767                 Arch     arch
 768                 Suffix   string
 769         }
 770         Func struct {
 771                 BodyBase
 772                 Kind   string // "Value" or "Block"
 773                 Suffix string
 774                 ArgLen int32 // if kind == "Value", number of args for this op
 775         }
 776         Switch struct {
 777                 BodyBase // []*Case
 778                 Expr     ast.Expr
 779         }
 780         Case struct {
 781                 BodyBase
 782                 Expr ast.Expr
 783         }
 784         RuleRewrite struct {
 785                 BodyBase
 786                 Match, Cond, Result string // top comments
 787                 Check               string // top-level boolean expression
 788
 789                 Alloc        int    // for unique var names
 790                 Loc          string // file name & line number of the original rule
 791                 CommuteDepth int    // used to track depth of commute loops
 792         }
 793         Declare struct {
 794                 Name  string
 795                 Value ast.Expr
 796         }
 797         CondBreak struct {
 798                 Cond              ast.Expr
 799                 InsideCommuteLoop bool
 800         }
 801         StartCommuteLoop struct {
 802                 Depth int
 803                 V     string
 804         }
 805 )
 806
 807 // exprf parses a Go expression generated from fmt.Sprintf, panicking if an
 808 // error occurs.
 809 func exprf(format string, a ...interface{}) ast.Expr {
 810         src := fmt.Sprintf(format, a...)
 811         expr, err := parser.ParseExpr(src)
 812         if err != nil {
 813                 log.Fatalf("expr parse error on %q: %v", src, err)
 814         }
 815         return expr
 816 }
 817
 818 // stmtf parses a Go statement generated from fmt.Sprintf. This function is only
 819 // meant for simple statements that don't have a custom Statement node declared
 820 // in this package, such as ast.ReturnStmt or ast.ExprStmt.
 821 func stmtf(format string, a ...interface{}) Statement {
 822         src := fmt.Sprintf(format, a...)
 823         fsrc := "package p\nfunc _() {\n" + src + "\n}\n"
 824         file, err := parser.ParseFile(token.NewFileSet(), "", fsrc, 0)
 825         if err != nil {
 826                 log.Fatalf("stmt parse error on %q: %v", src, err)
 827         }
 828         return file.Decls[0].(*ast.FuncDecl).Body.List[0]
 829 }
 830
 831 var reservedNames = map[string]bool{
 832         "v":      true, // Values[i], etc
 833         "b":      true, // v.Block
 834         "config": true, // b.Func.Config
 835         "fe":     true, // b.Func.fe
 836         "typ":    true, // &b.Func.Config.Types
 837 }
 838
 839 // declf constructs a simple "name := value" declaration,
 840 // using exprf for its value.
 841 //
 842 // name must not be one of reservedNames.
 843 // This helps prevent unintended shadowing and name clashes.
 844 // To declare a reserved name, use declReserved.
 845 func declf(loc, name, format string, a ...interface{}) *Declare {
 846         if reservedNames[name] {
 847                 log.Fatalf("rule %s uses the reserved name %s", loc, name)
 848         }
 849         return &Declare{name, exprf(format, a...)}
 850 }
 851
 852 // declReserved is like declf, but the name must be one of reservedNames.
 853 // Calls to declReserved should generally be static and top-level.
 854 func declReserved(name, value string) *Declare {
 855         if !reservedNames[name] {
 856                 panic(fmt.Sprintf("declReserved call does not use a reserved name: %q", name))
 857         }
 858         return &Declare{name, exprf(value)}
 859 }
 860
 861 // breakf constructs a simple "if cond { break }" statement, using exprf for its
 862 // condition.
 863 func breakf(format string, a ...interface{}) *CondBreak {
 864         return &CondBreak{Cond: exprf(format, a...)}
 865 }
 866
 867 func genBlockRewrite(rule Rule, arch arch, data blockData) *RuleRewrite {
 868         rr := &RuleRewrite{Loc: rule.Loc}
 869         rr.Match, rr.Cond, rr.Result = rule.parse()
 870         _, _, auxint, aux, s := extract(rr.Match) // remove parens, then split
 871
 872         // check match of control values
 873         if len(s) < data.controls {
 874                 log.Fatalf("incorrect number of arguments in %s, got %v wanted at least %v", rule, len(s), data.controls)
 875         }
 876         controls := s[:data.controls]
 877         pos := make([]string, data.controls)
 878         for i, arg := range controls {
 879                 cname := fmt.Sprintf("b.Controls[%v]", i)
 880                 if strings.Contains(arg, "(") {
 881                         vname, expr := splitNameExpr(arg)
 882                         if vname == "" {
 883                                 vname = fmt.Sprintf("v_%v", i)
 884                         }
 885                         rr.add(declf(rr.Loc, vname, cname))
 886                         p, op := genMatch0(rr, arch, expr, vname, nil, false) // TODO: pass non-nil cnt?
 887                         if op != "" {
 888                                 check := fmt.Sprintf("%s.Op == %s", cname, op)
 889                                 if rr.Check == "" {
 890                                         rr.Check = check
 891                                 } else {
 892                                         rr.Check += " && " + check
 893                                 }
 894                         }
 895                         if p == "" {
 896                                 p = vname + ".Pos"
 897                         }
 898                         pos[i] = p
 899                 } else {
 900                         rr.add(declf(rr.Loc, arg, cname))
 901                         pos[i] = arg + ".Pos"
 902                 }
 903         }
 904         for _, e := range []struct {
 905                 name, field, dclType string
 906         }{
 907                 {auxint, "AuxInt", data.auxIntType()},
 908                 {aux, "Aux", data.auxType()},
 909         } {
 910                 if e.name == "" {
 911                         continue
 912                 }
 913
 914                 if e.dclType == "" {
 915                         log.Fatalf("op %s has no declared type for %s", data.name, e.field)
 916                 }
 917                 if !token.IsIdentifier(e.name) || rr.declared(e.name) {
 918                         rr.add(breakf("%sTo%s(b.%s) != %s", unTitle(e.field), title(e.dclType), e.field, e.name))
 919                 } else {
 920                         rr.add(declf(rr.Loc, e.name, "%sTo%s(b.%s)", unTitle(e.field), title(e.dclType), e.field))
 921                 }
 922         }
 923         if rr.Cond != "" {
 924                 rr.add(breakf("!(%s)", rr.Cond))
 925         }
 926
 927         // Rule matches. Generate result.
 928         outop, _, auxint, aux, t := extract(rr.Result) // remove parens, then split
 929         blockName, outdata := getBlockInfo(outop, arch)
 930         if len(t) < outdata.controls {
 931                 log.Fatalf("incorrect number of output arguments in %s, got %v wanted at least %v", rule, len(s), outdata.controls)
 932         }
 933
 934         // Check if newsuccs is the same set as succs.
 935         succs := s[data.controls:]
 936         newsuccs := t[outdata.controls:]
 937         m := map[string]bool{}
 938         for _, succ := range succs {
 939                 if m[succ] {
 940                         log.Fatalf("can't have a repeat successor name %s in %s", succ, rule)
 941                 }
 942                 m[succ] = true
 943         }
 944         for _, succ := range newsuccs {
 945                 if !m[succ] {
 946                         log.Fatalf("unknown successor %s in %s", succ, rule)
 947                 }
 948                 delete(m, succ)
 949         }
 950         if len(m) != 0 {
 951                 log.Fatalf("unmatched successors %v in %s", m, rule)
 952         }
 953
 954         var genControls [2]string
 955         for i, control := range t[:outdata.controls] {
 956                 // Select a source position for any new control values.
 957                 // TODO: does it always make sense to use the source position
 958                 // of the original control values or should we be using the
 959                 // block's source position in some cases?
 960                 newpos := "b.Pos" // default to block's source position
 961                 if i < len(pos) && pos[i] != "" {
 962                         // Use the previous control value's source position.
 963                         newpos = pos[i]
 964                 }
 965
 966                 // Generate a new control value (or copy an existing value).
 967                 genControls[i] = genResult0(rr, arch, control, false, false, newpos, nil)
 968         }
 969         switch outdata.controls {
 970         case 0:
 971                 rr.add(stmtf("b.Reset(%s)", blockName))
 972         case 1:
 973                 rr.add(stmtf("b.resetWithControl(%s, %s)", blockName, genControls[0]))
 974         case 2:
 975                 rr.add(stmtf("b.resetWithControl2(%s, %s, %s)", blockName, genControls[0], genControls[1]))
 976         default:
 977                 log.Fatalf("too many controls: %d", outdata.controls)
 978         }
 979
 980         if auxint != "" {
 981                 // Make sure auxint value has the right type.
 982                 rr.add(stmtf("b.AuxInt = %sToAuxInt(%s)", unTitle(outdata.auxIntType()), auxint))
 983         }
 984         if aux != "" {
 985                 // Make sure aux value has the right type.
 986                 rr.add(stmtf("b.Aux = %sToAux(%s)", unTitle(outdata.auxType()), aux))
 987         }
 988
 989         succChanged := false
 990         for i := 0; i < len(succs); i++ {
 991                 if succs[i] != newsuccs[i] {
 992                         succChanged = true
 993                 }
 994         }
 995         if succChanged {
 996                 if len(succs) != 2 {
 997                         log.Fatalf("changed successors, len!=2 in %s", rule)
 998                 }
 999                 if succs[0] != newsuccs[1] || succs[1] != newsuccs[0] {
1000                         log.Fatalf("can only handle swapped successors in %s", rule)
1001                 }
1002                 rr.add(stmtf("b.swapSuccessors()"))
1003         }
1004
1005         if *genLog {
1006                 rr.add(stmtf("logRule(%q)", rule.Loc))
1007         }
1008         return rr
1009 }
1010
1011 // genMatch returns the variable whose source position should be used for the
1012 // result (or "" if no opinion), and a boolean that reports whether the match can fail.
1013 func genMatch(rr *RuleRewrite, arch arch, match string, pregenTop bool) (pos, checkOp string) {
1014         cnt := varCount(rr)
1015         return genMatch0(rr, arch, match, "v", cnt, pregenTop)
1016 }
1017
1018 func genMatch0(rr *RuleRewrite, arch arch, match, v string, cnt map[string]int, pregenTop bool) (pos, checkOp string) {
1019         if match[0] != '(' || match[len(match)-1] != ')' {
1020                 log.Fatalf("%s: non-compound expr in genMatch0: %q", rr.Loc, match)
1021         }
1022         op, oparch, typ, auxint, aux, args := parseValue(match, arch, rr.Loc)
1023
1024         checkOp = fmt.Sprintf("Op%s%s", oparch, op.name)
1025
1026         if op.faultOnNilArg0 || op.faultOnNilArg1 {
1027                 // Prefer the position of an instruction which could fault.
1028                 pos = v + ".Pos"
1029         }
1030
1031         // If the last argument is ___, it means "don't care about trailing arguments, really"
1032         // The likely/intended use is for rewrites that are too tricky to express in the existing pattern language
1033         // Do a length check early because long patterns fed short (ultimately not-matching) inputs will
1034         // do an indexing error in pattern-matching.
1035         if op.argLength == -1 {
1036                 l := len(args)
1037                 if l == 0 || args[l-1] != "___" {
1038                         rr.add(breakf("len(%s.Args) != %d", v, l))
1039                 } else if l > 1 && args[l-1] == "___" {
1040                         rr.add(breakf("len(%s.Args) < %d", v, l-1))
1041                 }
1042         }
1043
1044         for _, e := range []struct {
1045                 name, field, dclType string
1046         }{
1047                 {typ, "Type", "*types.Type"},
1048                 {auxint, "AuxInt", op.auxIntType()},
1049                 {aux, "Aux", op.auxType()},
1050         } {
1051                 if e.name == "" {
1052                         continue
1053                 }
1054
1055                 if e.dclType == "" {
1056                         log.Fatalf("op %s has no declared type for %s", op.name, e.field)
1057                 }
1058                 if !token.IsIdentifier(e.name) || rr.declared(e.name) {
1059                         switch e.field {
1060                         case "Aux":
1061                                 rr.add(breakf("auxTo%s(%s.%s) != %s", title(e.dclType), v, e.field, e.name))
1062                         case "AuxInt":
1063                                 rr.add(breakf("auxIntTo%s(%s.%s) != %s", title(e.dclType), v, e.field, e.name))
1064                         case "Type":
1065                                 rr.add(breakf("%s.%s != %s", v, e.field, e.name))
1066                         }
1067                 } else {
1068                         switch e.field {
1069                         case "Aux":
1070                                 rr.add(declf(rr.Loc, e.name, "auxTo%s(%s.%s)", title(e.dclType), v, e.field))
1071                         case "AuxInt":
1072                                 rr.add(declf(rr.Loc, e.name, "auxIntTo%s(%s.%s)", title(e.dclType), v, e.field))
1073                         case "Type":
1074                                 rr.add(declf(rr.Loc, e.name, "%s.%s", v, e.field))
1075                         }
1076                 }
1077         }
1078
1079         commutative := op.commutative
1080         if commutative {
1081                 if args[0] == args[1] {
1082                         // When we have (Add x x), for any x,
1083                         // even if there are other uses of x besides these two,
1084                         // and even if x is not a variable,
1085                         // we can skip the commutative match.
1086                         commutative = false
1087                 }
1088                 if cnt[args[0]] == 1 && cnt[args[1]] == 1 {
1089                         // When we have (Add x y) with no other uses
1090                         // of x and y in the matching rule and condition,
1091                         // then we can skip the commutative match (Add y x).
1092                         commutative = false
1093                 }
1094         }
1095
1096         if !pregenTop {
1097                 // Access last argument first to minimize bounds checks.
1098                 for n := len(args) - 1; n > 0; n-- {
1099                         a := args[n]
1100                         if a == "_" {
1101                                 continue
1102                         }
1103                         if !rr.declared(a) && token.IsIdentifier(a) && !(commutative && len(args) == 2) {
1104                                 rr.add(declf(rr.Loc, a, "%s.Args[%d]", v, n))
1105                                 // delete the last argument so it is not reprocessed
1106                                 args = args[:n]
1107                         } else {
1108                                 rr.add(stmtf("_ = %s.Args[%d]", v, n))
1109                         }
1110                         break
1111                 }
1112         }
1113         if commutative && !pregenTop {
1114                 for i := 0; i <= 1; i++ {
1115                         vname := fmt.Sprintf("%s_%d", v, i)
1116                         rr.add(declf(rr.Loc, vname, "%s.Args[%d]", v, i))
1117                 }
1118         }
1119         if commutative {
1120                 rr.add(StartCommuteLoop{rr.CommuteDepth, v})
1121                 rr.CommuteDepth++
1122         }
1123         for i, arg := range args {
1124                 if arg == "_" {
1125                         continue
1126                 }
1127                 var rhs string
1128                 if (commutative && i < 2) || pregenTop {
1129                         rhs = fmt.Sprintf("%s_%d", v, i)
1130                 } else {
1131                         rhs = fmt.Sprintf("%s.Args[%d]", v, i)
1132                 }
1133                 if !strings.Contains(arg, "(") {
1134                         // leaf variable
1135                         if rr.declared(arg) {
1136                                 // variable already has a definition. Check whether
1137                                 // the old definition and the new definition match.
1138                                 // For example, (add x x).  Equality is just pointer equality
1139                                 // on Values (so cse is important to do before lowering).
1140                                 rr.add(breakf("%s != %s", arg, rhs))
1141                         } else {
1142                                 if arg != rhs {
1143                                         rr.add(declf(rr.Loc, arg, "%s", rhs))
1144                                 }
1145                         }
1146                         continue
1147                 }
1148                 // compound sexpr
1149                 argname, expr := splitNameExpr(arg)
1150                 if argname == "" {
1151                         argname = fmt.Sprintf("%s_%d", v, i)
1152                 }
1153                 if argname == "b" {
1154                         log.Fatalf("don't name args 'b', it is ambiguous with blocks")
1155                 }
1156
1157                 if argname != rhs {
1158                         rr.add(declf(rr.Loc, argname, "%s", rhs))
1159                 }
1160                 bexpr := exprf("%s.Op != addLater", argname)
1161                 rr.add(&CondBreak{Cond: bexpr})
1162                 argPos, argCheckOp := genMatch0(rr, arch, expr, argname, cnt, false)
1163                 bexpr.(*ast.BinaryExpr).Y.(*ast.Ident).Name = argCheckOp
1164
1165                 if argPos != "" {
1166                         // Keep the argument in preference to the parent, as the
1167                         // argument is normally earlier in program flow.
1168                         // Keep the argument in preference to an earlier argument,
1169                         // as that prefers the memory argument which is also earlier
1170                         // in the program flow.
1171                         pos = argPos
1172                 }
1173         }
1174
1175         return pos, checkOp
1176 }
1177
1178 func genResult(rr *RuleRewrite, arch arch, result, pos string) {
1179         move := result[0] == '@'
1180         if move {
1181                 // parse @block directive
1182                 s := strings.SplitN(result[1:], " ", 2)
1183                 rr.add(stmtf("b = %s", s[0]))
1184                 result = s[1]
1185         }
1186         cse := make(map[string]string)
1187         genResult0(rr, arch, result, true, move, pos, cse)
1188 }
1189
1190 func genResult0(rr *RuleRewrite, arch arch, result string, top, move bool, pos string, cse map[string]string) string {
1191         resname, expr := splitNameExpr(result)
1192         result = expr
1193         // TODO: when generating a constant result, use f.constVal to avoid
1194         // introducing copies just to clean them up again.
1195         if result[0] != '(' {
1196                 // variable
1197                 if top {
1198                         // It in not safe in general to move a variable between blocks
1199                         // (and particularly not a phi node).
1200                         // Introduce a copy.
1201                         rr.add(stmtf("v.copyOf(%s)", result))
1202                 }
1203                 return result
1204         }
1205
1206         w := normalizeWhitespace(result)
1207         if prev := cse[w]; prev != "" {
1208                 return prev
1209         }
1210
1211         op, oparch, typ, auxint, aux, args := parseValue(result, arch, rr.Loc)
1212
1213         // Find the type of the variable.
1214         typeOverride := typ != ""
1215         if typ == "" && op.typ != "" {
1216                 typ = typeName(op.typ)
1217         }
1218
1219         v := "v"
1220         if top && !move {
1221                 rr.add(stmtf("v.reset(Op%s%s)", oparch, op.name))
1222                 if typeOverride {
1223                         rr.add(stmtf("v.Type = %s", typ))
1224                 }
1225         } else {
1226                 if typ == "" {
1227                         log.Fatalf("sub-expression %s (op=Op%s%s) at %s must have a type", result, oparch, op.name, rr.Loc)
1228                 }
1229                 if resname == "" {
1230                         v = fmt.Sprintf("v%d", rr.Alloc)
1231                 } else {
1232                         v = resname
1233                 }
1234                 rr.Alloc++
1235                 rr.add(declf(rr.Loc, v, "b.NewValue0(%s, Op%s%s, %s)", pos, oparch, op.name, typ))
1236                 if move && top {
1237                         // Rewrite original into a copy
1238                         rr.add(stmtf("v.copyOf(%s)", v))
1239                 }
1240         }
1241
1242         if auxint != "" {
1243                 // Make sure auxint value has the right type.
1244                 rr.add(stmtf("%s.AuxInt = %sToAuxInt(%s)", v, unTitle(op.auxIntType()), auxint))
1245         }
1246         if aux != "" {
1247                 // Make sure aux value has the right type.
1248                 rr.add(stmtf("%s.Aux = %sToAux(%s)", v, unTitle(op.auxType()), aux))
1249         }
1250         all := new(strings.Builder)
1251         for i, arg := range args {
1252                 x := genResult0(rr, arch, arg, false, move, pos, cse)
1253                 if i > 0 {
1254                         all.WriteString(", ")
1255                 }
1256                 all.WriteString(x)
1257         }
1258         switch len(args) {
1259         case 0:
1260         case 1:
1261                 rr.add(stmtf("%s.AddArg(%s)", v, all.String()))
1262         default:
1263                 rr.add(stmtf("%s.AddArg%d(%s)", v, len(args), all.String()))
1264         }
1265
1266         if cse != nil {
1267                 cse[w] = v
1268         }
1269         return v
1270 }
1271
1272 func split(s string) []string {
1273         var r []string
1274
1275 outer:
1276         for s != "" {
1277                 d := 0               // depth of ({[<
1278                 var open, close byte // opening and closing markers ({[< or )}]>
1279                 nonsp := false       // found a non-space char so far
1280                 for i := 0; i < len(s); i++ {
1281                         switch {
1282                         case d == 0 && s[i] == '(':
1283                                 open, close = '(', ')'
1284                                 d++
1285                         case d == 0 && s[i] == '<':
1286                                 open, close = '<', '>'
1287                                 d++
1288                         case d == 0 && s[i] == '[':
1289                                 open, close = '[', ']'
1290                                 d++
1291                         case d == 0 && s[i] == '{':
1292                                 open, close = '{', '}'
1293                                 d++
1294                         case d == 0 && (s[i] == ' ' || s[i] == '\t'):
1295                                 if nonsp {
1296                                         r = append(r, strings.TrimSpace(s[:i]))
1297                                         s = s[i:]
1298                                         continue outer
1299                                 }
1300                         case d > 0 && s[i] == open:
1301                                 d++
1302                         case d > 0 && s[i] == close:
1303                                 d--
1304                         default:
1305                                 nonsp = true
1306                         }
1307                 }
1308                 if d != 0 {
1309                         log.Fatalf("imbalanced expression: %q", s)
1310                 }
1311                 if nonsp {
1312                         r = append(r, strings.TrimSpace(s))
1313                 }
1314                 break
1315         }
1316         return r
1317 }
1318
1319 // isBlock reports whether this op is a block opcode.
1320 func isBlock(name string, arch arch) bool {
1321         for _, b := range genericBlocks {
1322                 if b.name == name {
1323                         return true
1324                 }
1325         }
1326         for _, b := range arch.blocks {
1327                 if b.name == name {
1328                         return true
1329                 }
1330         }
1331         return false
1332 }
1333
1334 func extract(val string) (op, typ, auxint, aux string, args []string) {
1335         val = val[1 : len(val)-1] // remove ()
1336
1337         // Split val up into regions.
1338         // Split by spaces/tabs, except those contained in (), {}, [], or <>.
1339         s := split(val)
1340
1341         // Extract restrictions and args.
1342         op = s[0]
1343         for _, a := range s[1:] {
1344                 switch a[0] {
1345                 case '<':
1346                         typ = a[1 : len(a)-1] // remove <>
1347                 case '[':
1348                         auxint = a[1 : len(a)-1] // remove []
1349                 case '{':
1350                         aux = a[1 : len(a)-1] // remove {}
1351                 default:
1352                         args = append(args, a)
1353                 }
1354         }
1355         return
1356 }
1357
1358 // parseValue parses a parenthesized value from a rule.
1359 // The value can be from the match or the result side.
1360 // It returns the op and unparsed strings for typ, auxint, and aux restrictions and for all args.
1361 // oparch is the architecture that op is located in, or "" for generic.
1362 func parseValue(val string, arch arch, loc string) (op opData, oparch, typ, auxint, aux string, args []string) {
1363         // Resolve the op.
1364         var s string
1365         s, typ, auxint, aux, args = extract(val)
1366
1367         // match reports whether x is a good op to select.
1368         // If strict is true, rule generation might succeed.
1369         // If strict is false, rule generation has failed,
1370         // but we're trying to generate a useful error.
1371         // Doing strict=true then strict=false allows
1372         // precise op matching while retaining good error messages.
1373         match := func(x opData, strict bool, archname string) bool {
1374                 if x.name != s {
1375                         return false
1376                 }
1377                 if x.argLength != -1 && int(x.argLength) != len(args) && (len(args) != 1 || args[0] != "...") {
1378                         if strict {
1379                                 return false
1380                         }
1381                         log.Printf("%s: op %s (%s) should have %d args, has %d", loc, s, archname, x.argLength, len(args))
1382                 }
1383                 return true
1384         }
1385
1386         for _, x := range genericOps {
1387                 if match(x, true, "generic") {
1388                         op = x
1389                         break
1390                 }
1391         }
1392         for _, x := range arch.ops {
1393                 if arch.name != "generic" && match(x, true, arch.name) {
1394                         if op.name != "" {
1395                                 log.Fatalf("%s: matches for op %s found in both generic and %s", loc, op.name, arch.name)
1396                         }
1397                         op = x
1398                         oparch = arch.name
1399                         break
1400                 }
1401         }
1402
1403         if op.name == "" {
1404                 // Failed to find the op.
1405                 // Run through everything again with strict=false
1406                 // to generate useful diagnosic messages before failing.
1407                 for _, x := range genericOps {
1408                         match(x, false, "generic")
1409                 }
1410                 for _, x := range arch.ops {
1411                         match(x, false, arch.name)
1412                 }
1413                 log.Fatalf("%s: unknown op %s", loc, s)
1414         }
1415
1416         // Sanity check aux, auxint.
1417         if auxint != "" && !opHasAuxInt(op) {
1418                 log.Fatalf("%s: op %s %s can't have auxint", loc, op.name, op.aux)
1419         }
1420         if aux != "" && !opHasAux(op) {
1421                 log.Fatalf("%s: op %s %s can't have aux", loc, op.name, op.aux)
1422         }
1423         return
1424 }
1425
1426 func opHasAuxInt(op opData) bool {
1427         switch op.aux {
1428         case "Bool", "Int8", "Int16", "Int32", "Int64", "Int128", "UInt8", "Float32", "Float64",
1429                 "SymOff", "CallOff", "SymValAndOff", "TypSize", "ARM64BitField", "FlagConstant", "CCop":
1430                 return true
1431         }
1432         return false
1433 }
1434
1435 func opHasAux(op opData) bool {
1436         switch op.aux {
1437         case "String", "Sym", "SymOff", "Call", "CallOff", "SymValAndOff", "Typ", "TypSize",
1438                 "S390XCCMask", "S390XRotateParams":
1439                 return true
1440         }
1441         return false
1442 }
1443
1444 // splitNameExpr splits s-expr arg, possibly prefixed by "name:",
1445 // into name and the unprefixed expression.
1446 // For example, "x:(Foo)" yields "x", "(Foo)",
1447 // and "(Foo)" yields "", "(Foo)".
1448 func splitNameExpr(arg string) (name, expr string) {
1449         colon := strings.Index(arg, ":")
1450         if colon < 0 {
1451                 return "", arg
1452         }
1453         openparen := strings.Index(arg, "(")
1454         if openparen < 0 {
1455                 log.Fatalf("splitNameExpr(%q): colon but no open parens", arg)
1456         }
1457         if colon > openparen {
1458                 // colon is inside the parens, such as in "(Foo x:(Bar))".
1459                 return "", arg
1460         }
1461         return arg[:colon], arg[colon+1:]
1462 }
1463
1464 func getBlockInfo(op string, arch arch) (name string, data blockData) {
1465         for _, b := range genericBlocks {
1466                 if b.name == op {
1467                         return "Block" + op, b
1468                 }
1469         }
1470         for _, b := range arch.blocks {
1471                 if b.name == op {
1472                         return "Block" + arch.name + op, b
1473                 }
1474         }
1475         log.Fatalf("could not find block data for %s", op)
1476         panic("unreachable")
1477 }
1478
1479 // typeName returns the string to use to generate a type.
1480 func typeName(typ string) string {
1481         if typ[0] == '(' {
1482                 ts := strings.Split(typ[1:len(typ)-1], ",")
1483                 if len(ts) != 2 {
1484                         log.Fatalf("Tuple expect 2 arguments")
1485                 }
1486                 return "types.NewTuple(" + typeName(ts[0]) + ", " + typeName(ts[1]) + ")"
1487         }
1488         switch typ {
1489         case "Flags", "Mem", "Void", "Int128":
1490                 return "types.Type" + typ
1491         default:
1492                 return "typ." + typ
1493         }
1494 }
1495
1496 // balance returns the number of unclosed '(' characters in s.
1497 // If a ')' appears without a corresponding '(', balance returns -1.
1498 func balance(s string) int {
1499         balance := 0
1500         for _, c := range s {
1501                 switch c {
1502                 case '(':
1503                         balance++
1504                 case ')':
1505                         balance--
1506                         if balance < 0 {
1507                                 // don't allow ")(" to return 0
1508                                 return -1
1509                         }
1510                 }
1511         }
1512         return balance
1513 }
1514
1515 // findAllOpcode is a function to find the opcode portion of s-expressions.
1516 var findAllOpcode = regexp.MustCompile(`[(](\w+[|])+\w+[)]`).FindAllStringIndex
1517
1518 // excludeFromExpansion reports whether the substring s[idx[0]:idx[1]] in a rule
1519 // should be disregarded as a candidate for | expansion.
1520 // It uses simple syntactic checks to see whether the substring
1521 // is inside an AuxInt expression or inside the && conditions.
1522 func excludeFromExpansion(s string, idx []int) bool {
1523         left := s[:idx[0]]
1524         if strings.LastIndexByte(left, '[') > strings.LastIndexByte(left, ']') {
1525                 // Inside an AuxInt expression.
1526                 return true
1527         }
1528         right := s[idx[1]:]
1529         if strings.Contains(left, "&&") && strings.Contains(right, "=>") {
1530                 // Inside && conditions.
1531                 return true
1532         }
1533         return false
1534 }
1535
1536 // expandOr converts a rule into multiple rules by expanding | ops.
1537 func expandOr(r string) []string {
1538         // Find every occurrence of |-separated things.
1539         // They look like MOV(B|W|L|Q|SS|SD)load or MOV(Q|L)loadidx(1|8).
1540         // Generate rules selecting one case from each |-form.
1541
1542         // Count width of |-forms.  They must match.
1543         n := 1
1544         for _, idx := range findAllOpcode(r, -1) {
1545                 if excludeFromExpansion(r, idx) {
1546                         continue
1547                 }
1548                 s := r[idx[0]:idx[1]]
1549                 c := strings.Count(s, "|") + 1
1550                 if c == 1 {
1551                         continue
1552                 }
1553                 if n > 1 && n != c {
1554                         log.Fatalf("'|' count doesn't match in %s: both %d and %d\n", r, n, c)
1555                 }
1556                 n = c
1557         }
1558         if n == 1 {
1559                 // No |-form in this rule.
1560                 return []string{r}
1561         }
1562         // Build each new rule.
1563         res := make([]string, n)
1564         for i := 0; i < n; i++ {
1565                 buf := new(strings.Builder)
1566                 x := 0
1567                 for _, idx := range findAllOpcode(r, -1) {
1568                         if excludeFromExpansion(r, idx) {
1569                                 continue
1570                         }
1571                         buf.WriteString(r[x:idx[0]])              // write bytes we've skipped over so far
1572                         s := r[idx[0]+1 : idx[1]-1]               // remove leading "(" and trailing ")"
1573                         buf.WriteString(strings.Split(s, "|")[i]) // write the op component for this rule
1574                         x = idx[1]                                // note that we've written more bytes
1575                 }
1576                 buf.WriteString(r[x:])
1577                 res[i] = buf.String()
1578         }
1579         return res
1580 }
1581
1582 // varCount returns a map which counts the number of occurrences of
1583 // Value variables in the s-expression rr.Match and the Go expression rr.Cond.
1584 func varCount(rr *RuleRewrite) map[string]int {
1585         cnt := map[string]int{}
1586         varCount1(rr.Loc, rr.Match, cnt)
1587         if rr.Cond != "" {
1588                 expr, err := parser.ParseExpr(rr.Cond)
1589                 if err != nil {
1590                         log.Fatalf("%s: failed to parse cond %q: %v", rr.Loc, rr.Cond, err)
1591                 }
1592                 ast.Inspect(expr, func(n ast.Node) bool {
1593                         if id, ok := n.(*ast.Ident); ok {
1594                                 cnt[id.Name]++
1595                         }
1596                         return true
1597                 })
1598         }
1599         return cnt
1600 }
1601
1602 func varCount1(loc, m string, cnt map[string]int) {
1603         if m[0] == '<' || m[0] == '[' || m[0] == '{' {
1604                 return
1605         }
1606         if token.IsIdentifier(m) {
1607                 cnt[m]++
1608                 return
1609         }
1610         // Split up input.
1611         name, expr := splitNameExpr(m)
1612         if name != "" {
1613                 cnt[name]++
1614         }
1615         if expr[0] != '(' || expr[len(expr)-1] != ')' {
1616                 log.Fatalf("%s: non-compound expr in varCount1: %q", loc, expr)
1617         }
1618         s := split(expr[1 : len(expr)-1])
1619         for _, arg := range s[1:] {
1620                 varCount1(loc, arg, cnt)
1621         }
1622 }
1623
1624 // normalizeWhitespace replaces 2+ whitespace sequences with a single space.
1625 func normalizeWhitespace(x string) string {
1626         x = strings.Join(strings.Fields(x), " ")
1627         x = strings.Replace(x, "( ", "(", -1)
1628         x = strings.Replace(x, " )", ")", -1)
1629         x = strings.Replace(x, "[ ", "[", -1)
1630         x = strings.Replace(x, " ]", "]", -1)
1631         x = strings.Replace(x, ")=>", ") =>", -1)
1632         return x
1633 }
1634
1635 // opIsCommutative reports whether op s is commutative.
1636 func opIsCommutative(op string, arch arch) bool {
1637         for _, x := range genericOps {
1638                 if op == x.name {
1639                         if x.commutative {
1640                                 return true
1641                         }
1642                         break
1643                 }
1644         }
1645         if arch.name != "generic" {
1646                 for _, x := range arch.ops {
1647                         if op == x.name {
1648                                 if x.commutative {
1649                                         return true
1650                                 }
1651                                 break
1652                         }
1653                 }
1654         }
1655         return false
1656 }
1657
1658 func normalizeMatch(m string, arch arch) string {
1659         if token.IsIdentifier(m) {
1660                 return m
1661         }
1662         op, typ, auxint, aux, args := extract(m)
1663         if opIsCommutative(op, arch) {
1664                 if args[1] < args[0] {
1665                         args[0], args[1] = args[1], args[0]
1666                 }
1667         }
1668         s := new(strings.Builder)
1669         fmt.Fprintf(s, "%s <%s> [%s] {%s}", op, typ, auxint, aux)
1670         for _, arg := range args {
1671                 prefix, expr := splitNameExpr(arg)
1672                 fmt.Fprint(s, " ", prefix, normalizeMatch(expr, arch))
1673         }
1674         return s.String()
1675 }
1676
1677 func parseEllipsisRules(rules []Rule, arch arch) (newop string, ok bool) {
1678         if len(rules) != 1 {
1679                 for _, r := range rules {
1680                         if strings.Contains(r.Rule, "...") {
1681                                 log.Fatalf("%s: found ellipsis in rule, but there are other rules with the same op", r.Loc)
1682                         }
1683                 }
1684                 return "", false
1685         }
1686         rule := rules[0]
1687         match, cond, result := rule.parse()
1688         if cond != "" || !isEllipsisValue(match) || !isEllipsisValue(result) {
1689                 if strings.Contains(rule.Rule, "...") {
1690                         log.Fatalf("%s: found ellipsis in non-ellipsis rule", rule.Loc)
1691                 }
1692                 checkEllipsisRuleCandidate(rule, arch)
1693                 return "", false
1694         }
1695         op, oparch, _, _, _, _ := parseValue(result, arch, rule.Loc)
1696         return fmt.Sprintf("Op%s%s", oparch, op.name), true
1697 }
1698
1699 // isEllipsisValue reports whether s is of the form (OpX ...).
1700 func isEllipsisValue(s string) bool {
1701         if len(s) < 2 || s[0] != '(' || s[len(s)-1] != ')' {
1702                 return false
1703         }
1704         c := split(s[1 : len(s)-1])
1705         if len(c) != 2 || c[1] != "..." {
1706                 return false
1707         }
1708         return true
1709 }
1710
1711 func checkEllipsisRuleCandidate(rule Rule, arch arch) {
1712         match, cond, result := rule.parse()
1713         if cond != "" {
1714                 return
1715         }
1716         op, _, _, auxint, aux, args := parseValue(match, arch, rule.Loc)
1717         var auxint2, aux2 string
1718         var args2 []string
1719         var usingCopy string
1720         var eop opData
1721         if result[0] != '(' {
1722                 // Check for (Foo x) => x, which can be converted to (Foo ...) => (Copy ...).
1723                 args2 = []string{result}
1724                 usingCopy = " using Copy"
1725         } else {
1726                 eop, _, _, auxint2, aux2, args2 = parseValue(result, arch, rule.Loc)
1727         }
1728         // Check that all restrictions in match are reproduced exactly in result.
1729         if aux != aux2 || auxint != auxint2 || len(args) != len(args2) {
1730                 return
1731         }
1732         if strings.Contains(rule.Rule, "=>") && op.aux != eop.aux {
1733                 return
1734         }
1735         for i := range args {
1736                 if args[i] != args2[i] {
1737                         return
1738                 }
1739         }
1740         switch {
1741         case opHasAux(op) && aux == "" && aux2 == "":
1742                 fmt.Printf("%s: rule silently zeros aux, either copy aux or explicitly zero\n", rule.Loc)
1743         case opHasAuxInt(op) && auxint == "" && auxint2 == "":
1744                 fmt.Printf("%s: rule silently zeros auxint, either copy auxint or explicitly zero\n", rule.Loc)
1745         default:
1746                 fmt.Printf("%s: possible ellipsis rule candidate%s: %q\n", rule.Loc, usingCopy, rule.Rule)
1747         }
1748 }
1749
1750 func opByName(arch arch, name string) opData {
1751         name = name[2:]
1752         for _, x := range genericOps {
1753                 if name == x.name {
1754                         return x
1755                 }
1756         }
1757         if arch.name != "generic" {
1758                 name = name[len(arch.name):]
1759                 for _, x := range arch.ops {
1760                         if name == x.name {
1761                                 return x
1762                         }
1763                 }
1764         }
1765         log.Fatalf("failed to find op named %s in arch %s", name, arch.name)
1766         panic("unreachable")
1767 }
1768
1769 // auxType returns the Go type that this operation should store in its aux field.
1770 func (op opData) auxType() string {
1771         switch op.aux {
1772         case "String":
1773                 return "string"
1774         case "Sym":
1775                 // Note: a Sym can be an *obj.LSym, a *gc.Node, or nil.
1776                 return "Sym"
1777         case "SymOff":
1778                 return "Sym"
1779         case "Call":
1780                 return "Call"
1781         case "CallOff":
1782                 return "Call"
1783         case "SymValAndOff":
1784                 return "Sym"
1785         case "Typ":
1786                 return "*types.Type"
1787         case "TypSize":
1788                 return "*types.Type"
1789         case "S390XCCMask":
1790                 return "s390x.CCMask"
1791         case "S390XRotateParams":
1792                 return "s390x.RotateParams"
1793         default:
1794                 return "invalid"
1795         }
1796 }
1797
1798 // auxIntType returns the Go type that this operation should store in its auxInt field.
1799 func (op opData) auxIntType() string {
1800         switch op.aux {
1801         case "Bool":
1802                 return "bool"
1803         case "Int8":
1804                 return "int8"
1805         case "Int16":
1806                 return "int16"
1807         case "Int32":
1808                 return "int32"
1809         case "Int64":
1810                 return "int64"
1811         case "Int128":
1812                 return "int128"
1813         case "UInt8":
1814                 return "uint8"
1815         case "Float32":
1816                 return "float32"
1817         case "Float64":
1818                 return "float64"
1819         case "CallOff":
1820                 return "int32"
1821         case "SymOff":
1822                 return "int32"
1823         case "SymValAndOff":
1824                 return "ValAndOff"
1825         case "TypSize":
1826                 return "int64"
1827         case "CCop":
1828                 return "Op"
1829         case "FlagConstant":
1830                 return "flagConstant"
1831         case "ARM64BitField":
1832                 return "arm64BitField"
1833         default:
1834                 return "invalid"
1835         }
1836 }
1837
1838 // auxType returns the Go type that this block should store in its aux field.
1839 func (b blockData) auxType() string {
1840         switch b.aux {
1841         case "S390XCCMask", "S390XCCMaskInt8", "S390XCCMaskUint8":
1842                 return "s390x.CCMask"
1843         case "S390XRotateParams":
1844                 return "s390x.RotateParams"
1845         default:
1846                 return "invalid"
1847         }
1848 }
1849
1850 // auxIntType returns the Go type that this block should store in its auxInt field.
1851 func (b blockData) auxIntType() string {
1852         switch b.aux {
1853         case "S390XCCMaskInt8":
1854                 return "int8"
1855         case "S390XCCMaskUint8":
1856                 return "uint8"
1857         case "Int64":
1858                 return "int64"
1859         default:
1860                 return "invalid"
1861         }
1862 }
1863
1864 func title(s string) string {
1865         if i := strings.Index(s, "."); i >= 0 {
1866                 switch strings.ToLower(s[:i]) {
1867                 case "s390x": // keep arch prefix for clarity
1868                         s = s[:i] + s[i+1:]
1869                 default:
1870                         s = s[i+1:]
1871                 }
1872         }
1873         return strings.Title(s)
1874 }
1875
1876 func unTitle(s string) string {
1877         if i := strings.Index(s, "."); i >= 0 {
1878                 switch strings.ToLower(s[:i]) {
1879                 case "s390x": // keep arch prefix for clarity
1880                         s = s[:i] + s[i+1:]
1881                 default:
1882                         s = s[i+1:]
1883                 }
1884         }
1885         return strings.ToLower(s[:1]) + s[1:]
1886 }