// 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 reports whether 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 ::= [variable:](opcode sexpr*)
// | variable
// | <type>
// | [auxint]
// | {aux}
//
// aux ::= variable | {code}
// type ::= variable | {code}
// variable ::= some token
// opcode ::= one of the opcodes from the *Ops.go files
// 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)
}
func normalizeSpaces(s string) string {
return strings.Join(strings.Fields(strings.TrimSpace(s)), " ")
}
// 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 = normalizeSpaces(s[0])
result = normalizeSpaces(s[1])
cond = ""
if i := strings.Index(match, "&&"); i >= 0 {
cond = normalizeSpaces(match[i+2:])
match = normalizeSpaces(match[:i])
}
return match, cond, result
}
func genRules(arch arch) { genRulesSuffix(arch, "") }
func genSplitLoadRules(arch arch) { genRulesSuffix(arch, "splitload") }
func genRulesSuffix(arch arch, suff string) {
// Open input file.
text, err := os.Open(arch.name + suff + ".rules")
if err != nil {
if suff == "" {
// All architectures must have a plain rules file.
log.Fatalf("can't read rule file: %v", err)
}
// Some architectures have bonus rules files that others don't share. That's fine.
return
}
// 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%s.rules:%d", arch.name, suff, ruleLineno)
for _, rule2 := range expandOr(rule) {
for _, rule3 := range commute(rule2, arch) {
r := Rule{rule: rule3, loc: loc}
if rawop := strings.Split(rule3, " ")[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, "// Code generated from gen/%s%s.rules; DO NOT EDIT.\n", arch.name, suff)
fmt.Fprintln(w, "// generated with: cd gen; go run *.go")
fmt.Fprintln(w)
fmt.Fprintln(w, "package ssa")
fmt.Fprintln(w, "import \"fmt\"")
fmt.Fprintln(w, "import \"math\"")
fmt.Fprintln(w, "import \"cmd/internal/obj\"")
fmt.Fprintln(w, "import \"cmd/internal/objabi\"")
fmt.Fprintln(w, "import \"cmd/compile/internal/types\"")
fmt.Fprintln(w, "var _ = fmt.Println // in case not otherwise used")
fmt.Fprintln(w, "var _ = math.MinInt8 // in case not otherwise used")
fmt.Fprintln(w, "var _ = obj.ANOP // in case not otherwise used")
fmt.Fprintln(w, "var _ = objabi.GOROOT // in case not otherwise used")
fmt.Fprintln(w, "var _ = types.TypeMem // in case not otherwise used")
fmt.Fprintln(w)
const chunkSize = 10
// Main rewrite routine is a switch on v.Op.
fmt.Fprintf(w, "func rewriteValue%s%s(v *Value) bool {\n", arch.name, suff)
fmt.Fprintf(w, "switch v.Op {\n")
for _, op := range ops {
fmt.Fprintf(w, "case %s:\n", op)
fmt.Fprint(w, "return ")
for chunk := 0; chunk < len(oprules[op]); chunk += chunkSize {
if chunk > 0 {
fmt.Fprint(w, " || ")
}
fmt.Fprintf(w, "rewriteValue%s%s_%s_%d(v)", arch.name, suff, op, chunk)
}
fmt.Fprintln(w)
}
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 {
for chunk := 0; chunk < len(oprules[op]); chunk += chunkSize {
buf := new(bytes.Buffer)
var canFail bool
endchunk := chunk + chunkSize
if endchunk > len(oprules[op]) {
endchunk = len(oprules[op])
}
for i, rule := range oprules[op][chunk:endchunk] {
match, cond, result := rule.parse()
fmt.Fprintf(buf, "// match: %s\n", match)
fmt.Fprintf(buf, "// cond: %s\n", cond)
fmt.Fprintf(buf, "// result: %s\n", result)
canFail = false
fmt.Fprintf(buf, "for {\n")
pos, _, matchCanFail := genMatch(buf, arch, match, rule.loc)
if pos == "" {
pos = "v.Pos"
}
if matchCanFail {
canFail = true
}
if cond != "" {
fmt.Fprintf(buf, "if !(%s) {\nbreak\n}\n", cond)
canFail = true
}
if !canFail && i+chunk != len(oprules[op])-1 {
log.Fatalf("unconditional rule %s is followed by other rules", match)
}
genResult(buf, arch, result, rule.loc, pos)
if *genLog {
fmt.Fprintf(buf, "logRule(\"%s\")\n", rule.loc)
}
fmt.Fprintf(buf, "return true\n")
fmt.Fprintf(buf, "}\n")
}
if canFail {
fmt.Fprintf(buf, "return false\n")
}
body := buf.String()
// Figure out whether we need b, config, fe, and/or types; provide them if so.
hasb := strings.Contains(body, " b.")
hasconfig := strings.Contains(body, "config.") || strings.Contains(body, "config)")
hasfe := strings.Contains(body, "fe.")
hastyps := strings.Contains(body, "typ.")
fmt.Fprintf(w, "func rewriteValue%s%s_%s_%d(v *Value) bool {\n", arch.name, suff, op, chunk)
if hasb || hasconfig || hasfe || hastyps {
fmt.Fprintln(w, "b := v.Block")
}
if hasconfig {
fmt.Fprintln(w, "config := b.Func.Config")
}
if hasfe {
fmt.Fprintln(w, "fe := b.Func.fe")
}
if hastyps {
fmt.Fprintln(w, "typ := &b.Func.Config.Types")
}
fmt.Fprint(w, body)
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%s(b *Block) bool {\n", arch.name, suff)
fmt.Fprintln(w, "config := b.Func.Config")
fmt.Fprintln(w, "typ := &config.Types")
fmt.Fprintln(w, "_ = typ")
fmt.Fprintln(w, "v := b.Control")
fmt.Fprintln(w, "_ = v")
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)
_, _, _, aux, s := extract(match) // remove parens, then split
loopw := new(bytes.Buffer)
// check match of control value
pos := ""
checkOp := ""
if s[0] != "nil" {
if strings.Contains(s[0], "(") {
pos, checkOp, _ = genMatch0(loopw, arch, s[0], "v", map[string]struct{}{}, rule.loc)
} else {
fmt.Fprintf(loopw, "%s := b.Control\n", s[0])
}
}
if aux != "" {
fmt.Fprintf(loopw, "%s := b.Aux\n", aux)
}
if cond != "" {
fmt.Fprintf(loopw, "if !(%s) {\nbreak\n}\n", cond)
}
// Rule matches. Generate result.
outop, _, _, aux, t := extract(result) // remove parens, then split
newsuccs := t[1:]
// Check if newsuccs is the same set as succs.
succs := s[1:]
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(loopw, "b.Kind = %s\n", blockName(outop, arch))
if t[0] == "nil" {
fmt.Fprintf(loopw, "b.SetControl(nil)\n")
} else {
if pos == "" {
pos = "v.Pos"
}
fmt.Fprintf(loopw, "b.SetControl(%s)\n", genResult0(loopw, arch, t[0], new(int), false, false, rule.loc, pos))
}
if aux != "" {
fmt.Fprintf(loopw, "b.Aux = %s\n", aux)
} else {
fmt.Fprintln(loopw, "b.Aux = nil")
}
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(loopw, "b.swapSuccessors()")
}
if *genLog {
fmt.Fprintf(loopw, "logRule(\"%s\")\n", rule.loc)
}
fmt.Fprintf(loopw, "return true\n")
if checkOp != "" {
fmt.Fprintf(w, "for v.Op == %s {\n", checkOp)
} else {
fmt.Fprintf(w, "for {\n")
}
io.Copy(w, loopw)
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+suff+".go", src, 0666)
if err != nil {
log.Fatalf("can't write output: %v\n", err)
}
}
// genMatch returns the variable whose source position should be used for the
// result (or "" if no opinion), and a boolean that reports whether the match can fail.
func genMatch(w io.Writer, arch arch, match string, loc string) (pos, checkOp string, canFail bool) {
return genMatch0(w, arch, match, "v", map[string]struct{}{}, loc)
}
func genMatch0(w io.Writer, arch arch, match, v string, m map[string]struct{}, loc string) (pos, checkOp string, canFail bool) {
if match[0] != '(' || match[len(match)-1] != ')' {
panic("non-compound expr in genMatch0: " + match)
}
op, oparch, typ, auxint, aux, args := parseValue(match, arch, loc)
checkOp = fmt.Sprintf("Op%s%s", oparch, op.name)
if op.faultOnNilArg0 || op.faultOnNilArg1 {
// Prefer the position of an instruction which could fault.
pos = v + ".Pos"
}
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)
}
}
}
// Access last argument first to minimize bounds checks.
if n := len(args); n > 1 {
a := args[n-1]
if _, set := m[a]; !set && a != "_" && isVariable(a) {
m[a] = struct{}{}
fmt.Fprintf(w, "%s := %s.Args[%d]\n", a, v, n-1)
// delete the last argument so it is not reprocessed
args = args[:n-1]
} else {
fmt.Fprintf(w, "_ = %s.Args[%d]\n", v, n-1)
}
}
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)
}
if argname == "b" {
log.Fatalf("don't name args 'b', it is ambiguous with blocks")
}
fmt.Fprintf(w, "%s := %s.Args[%d]\n", argname, v, i)
w2 := new(bytes.Buffer)
argPos, argCheckOp, _ := genMatch0(w2, arch, arg, argname, m, loc)
fmt.Fprintf(w, "if %s.Op != %s {\nbreak\n}\n", argname, argCheckOp)
io.Copy(w, w2)
if argPos != "" {
// Keep the argument in preference to the parent, as the
// argument is normally earlier in program flow.
// Keep the argument in preference to an earlier argument,
// as that prefers the memory argument which is also earlier
// in the program flow.
pos = argPos
}
canFail = true
}
if op.argLength == -1 {
fmt.Fprintf(w, "if len(%s.Args) != %d {\nbreak\n}\n", v, len(args))
canFail = true
}
return pos, checkOp, canFail
}
func genResult(w io.Writer, arch arch, result string, loc string, pos 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, pos)
}
func genResult0(w io.Writer, arch arch, result string, alloc *int, top, move bool, loc string, pos 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) at %s must have a type", result, oparch, op.name, loc)
}
v = fmt.Sprintf("v%d", *alloc)
*alloc++
fmt.Fprintf(w, "%s := b.NewValue0(%s, Op%s%s, %s)\n", v, pos, 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, pos)
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 reports whether 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
}
func extract(val string) (op 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.
op = s[0]
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)
}
}
return
}
// 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) {
// Resolve the op.
var s string
s, typ, auxint, aux, args = extract(val)
// 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 {
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, 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", "TypSize":
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", "Typ", "TypSize", "CCop":
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 "types.NewTuple(" + typeName(ts[0]) + ", " + typeName(ts[1]) + ")"
}
switch typ {
case "Flags", "Mem", "Void", "Int128":
return "types.Type" + typ
default:
return "typ." + typ
}
}
// unbalanced reports whether 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
}
// opRegexp is a regular expression to find the opcode portion of s-expressions.
var opRegexp = regexp.MustCompile(`[(](\w+[|])+\w+[)]`)
// excludeFromExpansion reports whether the substring s[idx[0]:idx[1]] in a rule
// should be disregarded as a candidate for | expansion.
// It uses simple syntactic checks to see whether the substring
// is inside an AuxInt expression or inside the && conditions.
func excludeFromExpansion(s string, idx []int) bool {
left := s[:idx[0]]
if strings.LastIndexByte(left, '[') > strings.LastIndexByte(left, ']') {
// Inside an AuxInt expression.
return true
}
right := s[idx[1]:]
if strings.Contains(left, "&&") && strings.Contains(right, "->") {
// Inside && conditions.
return true
}
return false
}
// expandOr converts a rule into multiple rules by expanding | ops.
func expandOr(r string) []string {
// Find every occurrence of |-separated things.
// They look like MOV(B|W|L|Q|SS|SD)load or MOV(Q|L)loadidx(1|8).
// Generate rules selecting one case from each |-form.
// Count width of |-forms. They must match.
n := 1
for _, idx := range opRegexp.FindAllStringIndex(r, -1) {
if excludeFromExpansion(r, idx) {
continue
}
s := r[idx[0]:idx[1]]
c := strings.Count(s, "|") + 1
if c == 1 {
continue
}
if n > 1 && n != c {
log.Fatalf("'|' count doesn't match in %s: both %d and %d\n", r, n, c)
}
n = c
}
if n == 1 {
// No |-form in this rule.
return []string{r}
}
// Build each new rule.
res := make([]string, n)
for i := 0; i < n; i++ {
buf := new(strings.Builder)
x := 0
for _, idx := range opRegexp.FindAllStringIndex(r, -1) {
if excludeFromExpansion(r, idx) {
continue
}
buf.WriteString(r[x:idx[0]]) // write bytes we've skipped over so far
s := r[idx[0]+1 : idx[1]-1] // remove leading "(" and trailing ")"
buf.WriteString(strings.Split(s, "|")[i]) // write the op component for this rule
x = idx[1] // note that we've written more bytes
}
buf.WriteString(r[x:])
res[i] = buf.String()
}
return res
}
// commute returns all equivalent rules to r after applying all possible
// argument swaps to the commutable ops in r.
// Potentially exponential, be careful.
func commute(r string, arch arch) []string {
match, cond, result := Rule{rule: r}.parse()
a := commute1(match, varCount(match), arch)
for i, m := range a {
if cond != "" {
m += " && " + cond
}
m += " -> " + result
a[i] = m
}
if len(a) == 1 && normalizeWhitespace(r) != normalizeWhitespace(a[0]) {
fmt.Println(normalizeWhitespace(r))
fmt.Println(normalizeWhitespace(a[0]))
panic("commute() is not the identity for noncommuting rule")
}
if false && len(a) > 1 {
fmt.Println(r)
for _, x := range a {
fmt.Println(" " + x)
}
}
return a
}
func commute1(m string, cnt map[string]int, arch arch) []string {
if m[0] == '<' || m[0] == '[' || m[0] == '{' || isVariable(m) {
return []string{m}
}
// Split up input.
var prefix string
colon := strings.Index(m, ":")
if colon >= 0 && isVariable(m[:colon]) {
prefix = m[:colon+1]
m = m[colon+1:]
}
if m[0] != '(' || m[len(m)-1] != ')' {
panic("non-compound expr in commute1: " + m)
}
s := split(m[1 : len(m)-1])
op := s[0]
// Figure out if the op is commutative or not.
commutative := false
for _, x := range genericOps {
if op == x.name {
if x.commutative {
commutative = true
}
break
}
}
if arch.name != "generic" {
for _, x := range arch.ops {
if op == x.name {
if x.commutative {
commutative = true
}
break
}
}
}
var idx0, idx1 int
if commutative {
// Find indexes of two args we can swap.
for i, arg := range s {
if i == 0 || arg[0] == '<' || arg[0] == '[' || arg[0] == '{' {
continue
}
if idx0 == 0 {
idx0 = i
continue
}
if idx1 == 0 {
idx1 = i
break
}
}
if idx1 == 0 {
panic("couldn't find first two args of commutative op " + s[0])
}
if cnt[s[idx0]] == 1 && cnt[s[idx1]] == 1 || s[idx0] == s[idx1] && cnt[s[idx0]] == 2 {
// When we have (Add x y) with no other uses of x and y in the matching rule,
// then we can skip the commutative match (Add y x).
commutative = false
}
}
// Recursively commute arguments.
a := make([][]string, len(s))
for i, arg := range s {
a[i] = commute1(arg, cnt, arch)
}
// Choose all possibilities from all args.
r := crossProduct(a)
// If commutative, do that again with its two args reversed.
if commutative {
a[idx0], a[idx1] = a[idx1], a[idx0]
r = append(r, crossProduct(a)...)
}
// Construct result.
for i, x := range r {
r[i] = prefix + "(" + x + ")"
}
return r
}
// varCount returns a map which counts the number of occurrences of
// Value variables in m.
func varCount(m string) map[string]int {
cnt := map[string]int{}
varCount1(m, cnt)
return cnt
}
func varCount1(m string, cnt map[string]int) {
if m[0] == '<' || m[0] == '[' || m[0] == '{' {
return
}
if isVariable(m) {
cnt[m]++
return
}
// Split up input.
colon := strings.Index(m, ":")
if colon >= 0 && isVariable(m[:colon]) {
cnt[m[:colon]]++
m = m[colon+1:]
}
if m[0] != '(' || m[len(m)-1] != ')' {
panic("non-compound expr in commute1: " + m)
}
s := split(m[1 : len(m)-1])
for _, arg := range s[1:] {
varCount1(arg, cnt)
}
}
// crossProduct returns all possible values
// x[0][i] + " " + x[1][j] + " " + ... + " " + x[len(x)-1][k]
// for all valid values of i, j, ..., k.
func crossProduct(x [][]string) []string {
if len(x) == 1 {
return x[0]
}
var r []string
for _, tail := range crossProduct(x[1:]) {
for _, first := range x[0] {
r = append(r, first+" "+tail)
}
}
return r
}
// normalizeWhitespace replaces 2+ whitespace sequences with a single space.
func normalizeWhitespace(x string) string {
x = strings.Join(strings.Fields(x), " ")
x = strings.Replace(x, "( ", "(", -1)
x = strings.Replace(x, " )", ")", -1)
x = strings.Replace(x, ")->", ") ->", -1)
return x
}
|
