| // Copyright 2015 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // +build gen |
| |
| // This program generates Go code that applies rewrite rules to a Value. |
| // The generated code implements a function of type func (v *Value) bool |
| // which returns true iff if did something. |
| // Ideas stolen from Swift: http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-2000-2.html |
| |
| package main |
| |
| import ( |
| "bufio" |
| "bytes" |
| "flag" |
| "fmt" |
| "go/format" |
| "io" |
| "io/ioutil" |
| "log" |
| "os" |
| "regexp" |
| "sort" |
| "strings" |
| ) |
| |
| // rule syntax: |
| // sexpr [&& extra conditions] -> [@block] sexpr |
| // |
| // sexpr are s-expressions (lisp-like parenthesized groupings) |
| // sexpr ::= (opcode sexpr*) |
| // | variable |
| // | <type> |
| // | [auxint] |
| // | {aux} |
| // |
| // aux ::= variable | {code} |
| // type ::= variable | {code} |
| // variable ::= some token |
| // opcode ::= one of the opcodes from ../op.go (without the Op prefix) |
| |
| // extra conditions is just a chunk of Go that evaluates to a boolean. It may use |
| // variables declared in the matching sexpr. The variable "v" is predefined to be |
| // the value matched by the entire rule. |
| |
| // If multiple rules match, the first one in file order is selected. |
| |
| var ( |
| genLog = flag.Bool("log", false, "generate code that logs; for debugging only") |
| ) |
| |
| type Rule struct { |
| rule string |
| loc string // file name & line number |
| } |
| |
| func (r Rule) String() string { |
| return fmt.Sprintf("rule %q at %s", r.rule, r.loc) |
| } |
| |
| // parse returns the matching part of the rule, additional conditions, and the result. |
| func (r Rule) parse() (match, cond, result string) { |
| s := strings.Split(r.rule, "->") |
| if len(s) != 2 { |
| log.Fatalf("no arrow in %s", r) |
| } |
| match = strings.TrimSpace(s[0]) |
| result = strings.TrimSpace(s[1]) |
| cond = "" |
| if i := strings.Index(match, "&&"); i >= 0 { |
| cond = strings.TrimSpace(match[i+2:]) |
| match = strings.TrimSpace(match[:i]) |
| } |
| return match, cond, result |
| } |
| |
| func genRules(arch arch) { |
| // Open input file. |
| text, err := os.Open(arch.name + ".rules") |
| if err != nil { |
| log.Fatalf("can't read rule file: %v", err) |
| } |
| |
| // oprules contains a list of rules for each block and opcode |
| blockrules := map[string][]Rule{} |
| oprules := map[string][]Rule{} |
| |
| // read rule file |
| scanner := bufio.NewScanner(text) |
| rule := "" |
| var lineno int |
| var ruleLineno int // line number of "->" |
| for scanner.Scan() { |
| lineno++ |
| line := scanner.Text() |
| if i := strings.Index(line, "//"); i >= 0 { |
| // Remove comments. Note that this isn't string safe, so |
| // it will truncate lines with // inside strings. Oh well. |
| line = line[:i] |
| } |
| rule += " " + line |
| rule = strings.TrimSpace(rule) |
| if rule == "" { |
| continue |
| } |
| if !strings.Contains(rule, "->") { |
| continue |
| } |
| if ruleLineno == 0 { |
| ruleLineno = lineno |
| } |
| if strings.HasSuffix(rule, "->") { |
| continue |
| } |
| if unbalanced(rule) { |
| continue |
| } |
| |
| loc := fmt.Sprintf("%s.rules:%d", arch.name, ruleLineno) |
| r := Rule{rule: rule, loc: loc} |
| if rawop := strings.Split(rule, " ")[0][1:]; isBlock(rawop, arch) { |
| blockrules[rawop] = append(blockrules[rawop], r) |
| } else { |
| // Do fancier value op matching. |
| match, _, _ := r.parse() |
| op, oparch, _, _, _, _ := parseValue(match, arch, loc) |
| opname := fmt.Sprintf("Op%s%s", oparch, op.name) |
| oprules[opname] = append(oprules[opname], r) |
| } |
| rule = "" |
| ruleLineno = 0 |
| } |
| if err := scanner.Err(); err != nil { |
| log.Fatalf("scanner failed: %v\n", err) |
| } |
| if unbalanced(rule) { |
| log.Fatalf("%s.rules:%d: unbalanced rule: %v\n", arch.name, lineno, rule) |
| } |
| |
| // Order all the ops. |
| var ops []string |
| for op := range oprules { |
| ops = append(ops, op) |
| } |
| sort.Strings(ops) |
| |
| // Start output buffer, write header. |
| w := new(bytes.Buffer) |
| fmt.Fprintf(w, "// autogenerated from gen/%s.rules: do not edit!\n", arch.name) |
| fmt.Fprintln(w, "// generated with: cd gen; go run *.go") |
| fmt.Fprintln(w) |
| fmt.Fprintln(w, "package ssa") |
| fmt.Fprintln(w, "import \"math\"") |
| fmt.Fprintln(w, "var _ = math.MinInt8 // in case not otherwise used") |
| |
| // Main rewrite routine is a switch on v.Op. |
| fmt.Fprintf(w, "func rewriteValue%s(v *Value, config *Config) bool {\n", arch.name) |
| fmt.Fprintf(w, "switch v.Op {\n") |
| for _, op := range ops { |
| fmt.Fprintf(w, "case %s:\n", op) |
| fmt.Fprintf(w, "return rewriteValue%s_%s(v, config)\n", arch.name, op) |
| } |
| fmt.Fprintf(w, "}\n") |
| fmt.Fprintf(w, "return false\n") |
| fmt.Fprintf(w, "}\n") |
| |
| // Generate a routine per op. Note that we don't make one giant routine |
| // because it is too big for some compilers. |
| for _, op := range ops { |
| fmt.Fprintf(w, "func rewriteValue%s_%s(v *Value, config *Config) bool {\n", arch.name, op) |
| fmt.Fprintln(w, "b := v.Block") |
| fmt.Fprintln(w, "_ = b") |
| var canFail bool |
| for i, rule := range oprules[op] { |
| match, cond, result := rule.parse() |
| fmt.Fprintf(w, "// match: %s\n", match) |
| fmt.Fprintf(w, "// cond: %s\n", cond) |
| fmt.Fprintf(w, "// result: %s\n", result) |
| |
| canFail = false |
| fmt.Fprintf(w, "for {\n") |
| if genMatch(w, arch, match, rule.loc) { |
| canFail = true |
| } |
| |
| if cond != "" { |
| fmt.Fprintf(w, "if !(%s) {\nbreak\n}\n", cond) |
| canFail = true |
| } |
| if !canFail && i != len(oprules[op])-1 { |
| log.Fatalf("unconditional rule %s is followed by other rules", match) |
| } |
| |
| genResult(w, arch, result, rule.loc) |
| if *genLog { |
| fmt.Fprintf(w, "logRule(\"%s\")\n", rule.loc) |
| } |
| fmt.Fprintf(w, "return true\n") |
| |
| fmt.Fprintf(w, "}\n") |
| } |
| if canFail { |
| fmt.Fprintf(w, "return false\n") |
| } |
| fmt.Fprintf(w, "}\n") |
| } |
| |
| // Generate block rewrite function. There are only a few block types |
| // so we can make this one function with a switch. |
| fmt.Fprintf(w, "func rewriteBlock%s(b *Block, config *Config) bool {\n", arch.name) |
| fmt.Fprintf(w, "switch b.Kind {\n") |
| ops = nil |
| for op := range blockrules { |
| ops = append(ops, op) |
| } |
| sort.Strings(ops) |
| for _, op := range ops { |
| fmt.Fprintf(w, "case %s:\n", blockName(op, arch)) |
| for _, rule := range blockrules[op] { |
| match, cond, result := rule.parse() |
| fmt.Fprintf(w, "// match: %s\n", match) |
| fmt.Fprintf(w, "// cond: %s\n", cond) |
| fmt.Fprintf(w, "// result: %s\n", result) |
| |
| fmt.Fprintf(w, "for {\n") |
| |
| s := split(match[1 : len(match)-1]) // remove parens, then split |
| |
| // check match of control value |
| if s[1] != "nil" { |
| fmt.Fprintf(w, "v := b.Control\n") |
| if strings.Contains(s[1], "(") { |
| genMatch0(w, arch, s[1], "v", map[string]struct{}{}, false, rule.loc) |
| } else { |
| fmt.Fprintf(w, "_ = v\n") // in case we don't use v |
| fmt.Fprintf(w, "%s := b.Control\n", s[1]) |
| } |
| } |
| |
| // assign successor names |
| succs := s[2:] |
| for i, a := range succs { |
| if a != "_" { |
| fmt.Fprintf(w, "%s := b.Succs[%d]\n", a, i) |
| } |
| } |
| |
| if cond != "" { |
| fmt.Fprintf(w, "if !(%s) {\nbreak\n}\n", cond) |
| } |
| |
| // Rule matches. Generate result. |
| t := split(result[1 : len(result)-1]) // remove parens, then split |
| newsuccs := t[2:] |
| |
| // Check if newsuccs is the same set as succs. |
| m := map[string]bool{} |
| for _, succ := range succs { |
| if m[succ] { |
| log.Fatalf("can't have a repeat successor name %s in %s", succ, rule) |
| } |
| m[succ] = true |
| } |
| for _, succ := range newsuccs { |
| if !m[succ] { |
| log.Fatalf("unknown successor %s in %s", succ, rule) |
| } |
| delete(m, succ) |
| } |
| if len(m) != 0 { |
| log.Fatalf("unmatched successors %v in %s", m, rule) |
| } |
| |
| fmt.Fprintf(w, "b.Kind = %s\n", blockName(t[0], arch)) |
| if t[1] == "nil" { |
| fmt.Fprintf(w, "b.SetControl(nil)\n") |
| } else { |
| fmt.Fprintf(w, "b.SetControl(%s)\n", genResult0(w, arch, t[1], new(int), false, false, rule.loc)) |
| } |
| |
| succChanged := false |
| for i := 0; i < len(succs); i++ { |
| if succs[i] != newsuccs[i] { |
| succChanged = true |
| } |
| } |
| if succChanged { |
| if len(succs) != 2 { |
| log.Fatalf("changed successors, len!=2 in %s", rule) |
| } |
| if succs[0] != newsuccs[1] || succs[1] != newsuccs[0] { |
| log.Fatalf("can only handle swapped successors in %s", rule) |
| } |
| fmt.Fprintln(w, "b.swapSuccessors()") |
| } |
| for i := 0; i < len(succs); i++ { |
| fmt.Fprintf(w, "_ = %s\n", newsuccs[i]) |
| } |
| |
| if *genLog { |
| fmt.Fprintf(w, "logRule(\"%s\")\n", rule.loc) |
| } |
| fmt.Fprintf(w, "return true\n") |
| |
| fmt.Fprintf(w, "}\n") |
| } |
| } |
| fmt.Fprintf(w, "}\n") |
| fmt.Fprintf(w, "return false\n") |
| fmt.Fprintf(w, "}\n") |
| |
| // gofmt result |
| b := w.Bytes() |
| src, err := format.Source(b) |
| if err != nil { |
| fmt.Printf("%s\n", b) |
| panic(err) |
| } |
| |
| // Write to file |
| err = ioutil.WriteFile("../rewrite"+arch.name+".go", src, 0666) |
| if err != nil { |
| log.Fatalf("can't write output: %v\n", err) |
| } |
| } |
| |
| // genMatch returns true if the match can fail. |
| func genMatch(w io.Writer, arch arch, match string, loc string) bool { |
| return genMatch0(w, arch, match, "v", map[string]struct{}{}, true, loc) |
| } |
| |
| func genMatch0(w io.Writer, arch arch, match, v string, m map[string]struct{}, top bool, loc string) bool { |
| if match[0] != '(' || match[len(match)-1] != ')' { |
| panic("non-compound expr in genMatch0: " + match) |
| } |
| canFail := false |
| |
| op, oparch, typ, auxint, aux, args := parseValue(match, arch, loc) |
| |
| // check op |
| if !top { |
| fmt.Fprintf(w, "if %s.Op != Op%s%s {\nbreak\n}\n", v, oparch, op.name) |
| canFail = true |
| } |
| |
| if typ != "" { |
| if !isVariable(typ) { |
| // code. We must match the results of this code. |
| fmt.Fprintf(w, "if %s.Type != %s {\nbreak\n}\n", v, typ) |
| canFail = true |
| } else { |
| // variable |
| if _, ok := m[typ]; ok { |
| // must match previous variable |
| fmt.Fprintf(w, "if %s.Type != %s {\nbreak\n}\n", v, typ) |
| canFail = true |
| } else { |
| m[typ] = struct{}{} |
| fmt.Fprintf(w, "%s := %s.Type\n", typ, v) |
| } |
| } |
| } |
| |
| if auxint != "" { |
| if !isVariable(auxint) { |
| // code |
| fmt.Fprintf(w, "if %s.AuxInt != %s {\nbreak\n}\n", v, auxint) |
| canFail = true |
| } else { |
| // variable |
| if _, ok := m[auxint]; ok { |
| fmt.Fprintf(w, "if %s.AuxInt != %s {\nbreak\n}\n", v, auxint) |
| canFail = true |
| } else { |
| m[auxint] = struct{}{} |
| fmt.Fprintf(w, "%s := %s.AuxInt\n", auxint, v) |
| } |
| } |
| } |
| |
| if aux != "" { |
| |
| if !isVariable(aux) { |
| // code |
| fmt.Fprintf(w, "if %s.Aux != %s {\nbreak\n}\n", v, aux) |
| canFail = true |
| } else { |
| // variable |
| if _, ok := m[aux]; ok { |
| fmt.Fprintf(w, "if %s.Aux != %s {\nbreak\n}\n", v, aux) |
| canFail = true |
| } else { |
| m[aux] = struct{}{} |
| fmt.Fprintf(w, "%s := %s.Aux\n", aux, v) |
| } |
| } |
| } |
| |
| for i, arg := range args { |
| if arg == "_" { |
| continue |
| } |
| if !strings.Contains(arg, "(") { |
| // leaf variable |
| if _, ok := m[arg]; ok { |
| // variable already has a definition. Check whether |
| // the old definition and the new definition match. |
| // For example, (add x x). Equality is just pointer equality |
| // on Values (so cse is important to do before lowering). |
| fmt.Fprintf(w, "if %s != %s.Args[%d] {\nbreak\n}\n", arg, v, i) |
| canFail = true |
| } else { |
| // remember that this variable references the given value |
| m[arg] = struct{}{} |
| fmt.Fprintf(w, "%s := %s.Args[%d]\n", arg, v, i) |
| } |
| continue |
| } |
| // compound sexpr |
| var argname string |
| colon := strings.Index(arg, ":") |
| openparen := strings.Index(arg, "(") |
| if colon >= 0 && openparen >= 0 && colon < openparen { |
| // rule-specified name |
| argname = arg[:colon] |
| arg = arg[colon+1:] |
| } else { |
| // autogenerated name |
| argname = fmt.Sprintf("%s_%d", v, i) |
| } |
| fmt.Fprintf(w, "%s := %s.Args[%d]\n", argname, v, i) |
| if genMatch0(w, arch, arg, argname, m, false, loc) { |
| canFail = true |
| } |
| } |
| |
| if op.argLength == -1 { |
| fmt.Fprintf(w, "if len(%s.Args) != %d {\nbreak\n}\n", v, len(args)) |
| canFail = true |
| } |
| return canFail |
| } |
| |
| func genResult(w io.Writer, arch arch, result string, loc string) { |
| move := false |
| if result[0] == '@' { |
| // parse @block directive |
| s := strings.SplitN(result[1:], " ", 2) |
| fmt.Fprintf(w, "b = %s\n", s[0]) |
| result = s[1] |
| move = true |
| } |
| genResult0(w, arch, result, new(int), true, move, loc) |
| } |
| func genResult0(w io.Writer, arch arch, result string, alloc *int, top, move bool, loc string) string { |
| // TODO: when generating a constant result, use f.constVal to avoid |
| // introducing copies just to clean them up again. |
| if result[0] != '(' { |
| // variable |
| if top { |
| // It in not safe in general to move a variable between blocks |
| // (and particularly not a phi node). |
| // Introduce a copy. |
| fmt.Fprintf(w, "v.reset(OpCopy)\n") |
| fmt.Fprintf(w, "v.Type = %s.Type\n", result) |
| fmt.Fprintf(w, "v.AddArg(%s)\n", result) |
| } |
| return result |
| } |
| |
| op, oparch, typ, auxint, aux, args := parseValue(result, arch, loc) |
| |
| // Find the type of the variable. |
| typeOverride := typ != "" |
| if typ == "" && op.typ != "" { |
| typ = typeName(op.typ) |
| } |
| |
| var v string |
| if top && !move { |
| v = "v" |
| fmt.Fprintf(w, "v.reset(Op%s%s)\n", oparch, op.name) |
| if typeOverride { |
| fmt.Fprintf(w, "v.Type = %s\n", typ) |
| } |
| } else { |
| if typ == "" { |
| log.Fatalf("sub-expression %s (op=Op%s%s) must have a type", result, oparch, op.name) |
| } |
| v = fmt.Sprintf("v%d", *alloc) |
| *alloc++ |
| fmt.Fprintf(w, "%s := b.NewValue0(v.Line, Op%s%s, %s)\n", v, oparch, op.name, typ) |
| if move && top { |
| // Rewrite original into a copy |
| fmt.Fprintf(w, "v.reset(OpCopy)\n") |
| fmt.Fprintf(w, "v.AddArg(%s)\n", v) |
| } |
| } |
| |
| if auxint != "" { |
| fmt.Fprintf(w, "%s.AuxInt = %s\n", v, auxint) |
| } |
| if aux != "" { |
| fmt.Fprintf(w, "%s.Aux = %s\n", v, aux) |
| } |
| for _, arg := range args { |
| x := genResult0(w, arch, arg, alloc, false, move, loc) |
| fmt.Fprintf(w, "%s.AddArg(%s)\n", v, x) |
| } |
| |
| return v |
| } |
| |
| func split(s string) []string { |
| var r []string |
| |
| outer: |
| for s != "" { |
| d := 0 // depth of ({[< |
| var open, close byte // opening and closing markers ({[< or )}]> |
| nonsp := false // found a non-space char so far |
| for i := 0; i < len(s); i++ { |
| switch { |
| case d == 0 && s[i] == '(': |
| open, close = '(', ')' |
| d++ |
| case d == 0 && s[i] == '<': |
| open, close = '<', '>' |
| d++ |
| case d == 0 && s[i] == '[': |
| open, close = '[', ']' |
| d++ |
| case d == 0 && s[i] == '{': |
| open, close = '{', '}' |
| d++ |
| case d == 0 && (s[i] == ' ' || s[i] == '\t'): |
| if nonsp { |
| r = append(r, strings.TrimSpace(s[:i])) |
| s = s[i:] |
| continue outer |
| } |
| case d > 0 && s[i] == open: |
| d++ |
| case d > 0 && s[i] == close: |
| d-- |
| default: |
| nonsp = true |
| } |
| } |
| if d != 0 { |
| panic("imbalanced expression: " + s) |
| } |
| if nonsp { |
| r = append(r, strings.TrimSpace(s)) |
| } |
| break |
| } |
| return r |
| } |
| |
| // isBlock returns true if this op is a block opcode. |
| func isBlock(name string, arch arch) bool { |
| for _, b := range genericBlocks { |
| if b.name == name { |
| return true |
| } |
| } |
| for _, b := range arch.blocks { |
| if b.name == name { |
| return true |
| } |
| } |
| return false |
| } |
| |
| // parseValue parses a parenthesized value from a rule. |
| // The value can be from the match or the result side. |
| // It returns the op and unparsed strings for typ, auxint, and aux restrictions and for all args. |
| // oparch is the architecture that op is located in, or "" for generic. |
| func parseValue(val string, arch arch, loc string) (op opData, oparch string, typ string, auxint string, aux string, args []string) { |
| val = val[1 : len(val)-1] // remove () |
| |
| // Split val up into regions. |
| // Split by spaces/tabs, except those contained in (), {}, [], or <>. |
| s := split(val) |
| |
| // Extract restrictions and args. |
| for _, a := range s[1:] { |
| switch a[0] { |
| case '<': |
| typ = a[1 : len(a)-1] // remove <> |
| case '[': |
| auxint = a[1 : len(a)-1] // remove [] |
| case '{': |
| aux = a[1 : len(a)-1] // remove {} |
| default: |
| args = append(args, a) |
| } |
| } |
| |
| // Resolve the op. |
| |
| // match reports whether x is a good op to select. |
| // If strict is true, rule generation might succeed. |
| // If strict is false, rule generation has failed, |
| // but we're trying to generate a useful error. |
| // Doing strict=true then strict=false allows |
| // precise op matching while retaining good error messages. |
| match := func(x opData, strict bool, archname string) bool { |
| if x.name != s[0] { |
| return false |
| } |
| if x.argLength != -1 && int(x.argLength) != len(args) { |
| if strict { |
| return false |
| } else { |
| log.Printf("%s: op %s (%s) should have %d args, has %d", loc, s[0], archname, x.argLength, len(args)) |
| } |
| } |
| return true |
| } |
| |
| for _, x := range genericOps { |
| if match(x, true, "generic") { |
| op = x |
| break |
| } |
| } |
| if arch.name != "generic" { |
| for _, x := range arch.ops { |
| if match(x, true, arch.name) { |
| if op.name != "" { |
| log.Fatalf("%s: matches for op %s found in both generic and %s", loc, op.name, arch.name) |
| } |
| op = x |
| oparch = arch.name |
| break |
| } |
| } |
| } |
| |
| if op.name == "" { |
| // Failed to find the op. |
| // Run through everything again with strict=false |
| // to generate useful diagnosic messages before failing. |
| for _, x := range genericOps { |
| match(x, false, "generic") |
| } |
| for _, x := range arch.ops { |
| match(x, false, arch.name) |
| } |
| log.Fatalf("%s: unknown op %s", loc, s) |
| } |
| |
| // Sanity check aux, auxint. |
| if auxint != "" { |
| switch op.aux { |
| case "Bool", "Int8", "Int16", "Int32", "Int64", "Int128", "Float32", "Float64", "SymOff", "SymValAndOff", "SymInt32", "SizeAndAlign": |
| default: |
| log.Fatalf("%s: op %s %s can't have auxint", loc, op.name, op.aux) |
| } |
| } |
| if aux != "" { |
| switch op.aux { |
| case "String", "Sym", "SymOff", "SymValAndOff", "SymInt32": |
| default: |
| log.Fatalf("%s: op %s %s can't have aux", loc, op.name, op.aux) |
| } |
| } |
| |
| return |
| } |
| |
| func blockName(name string, arch arch) string { |
| for _, b := range genericBlocks { |
| if b.name == name { |
| return "Block" + name |
| } |
| } |
| return "Block" + arch.name + name |
| } |
| |
| // typeName returns the string to use to generate a type. |
| func typeName(typ string) string { |
| if typ[0] == '(' { |
| ts := strings.Split(typ[1:len(typ)-1], ",") |
| if len(ts) != 2 { |
| panic("Tuple expect 2 arguments") |
| } |
| return "MakeTuple(" + typeName(ts[0]) + ", " + typeName(ts[1]) + ")" |
| } |
| switch typ { |
| case "Flags", "Mem", "Void", "Int128": |
| return "Type" + typ |
| default: |
| return "config.fe.Type" + typ + "()" |
| } |
| } |
| |
| // unbalanced returns true if there aren't the same number of ( and ) in the string. |
| func unbalanced(s string) bool { |
| var left, right int |
| for _, c := range s { |
| if c == '(' { |
| left++ |
| } |
| if c == ')' { |
| right++ |
| } |
| } |
| return left != right |
| } |
| |
| // isVariable reports whether s is a single Go alphanumeric identifier. |
| func isVariable(s string) bool { |
| b, err := regexp.MatchString("^[A-Za-z_][A-Za-z_0-9]*$", s) |
| if err != nil { |
| panic("bad variable regexp") |
| } |
| return b |
| } |
