diff options
Diffstat (limited to 'src/cmd/compile/internal/test/testdata/flowgraph_generator1.go')
| -rw-r--r-- | src/cmd/compile/internal/test/testdata/flowgraph_generator1.go | 315 |
1 files changed, 315 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/test/testdata/flowgraph_generator1.go b/src/cmd/compile/internal/test/testdata/flowgraph_generator1.go new file mode 100644 index 0000000000..ad22601f43 --- /dev/null +++ b/src/cmd/compile/internal/test/testdata/flowgraph_generator1.go @@ -0,0 +1,315 @@ +// Copyright 2016 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. + +package main + +import ( + "fmt" + "strings" +) + +// make fake flow graph. + +// The blocks of the flow graph are designated with letters A +// through Z, always including A (start block) and Z (exit +// block) The specification of a flow graph is a comma- +// separated list of block successor words, for blocks ordered +// A, B, C etc, where each block except Z has one or two +// successors, and any block except A can be a target. Within +// the generated code, each block with two successors includes +// a conditional testing x & 1 != 0 (x is the input parameter +// to the generated function) and also unconditionally shifts x +// right by one, so that different inputs generate different +// execution paths, including loops. Every block inverts a +// global binary to ensure it is not empty. For a flow graph +// with J words (J+1 blocks), a J-1 bit serial number specifies +// which blocks (not including A and Z) include an increment of +// the return variable y by increasing powers of 10, and a +// different version of the test function is created for each +// of the 2-to-the-(J-1) serial numbers. + +// For each generated function a compact summary is also +// created so that the generated function can be simulated +// with a simple interpreter to sanity check the behavior of +// the compiled code. + +// For example: + +// func BC_CD_BE_BZ_CZ101(x int64) int64 { +// y := int64(0) +// var b int64 +// _ = b +// b = x & 1 +// x = x >> 1 +// if b != 0 { +// goto C +// } +// goto B +// B: +// glob_ = !glob_ +// y += 1 +// b = x & 1 +// x = x >> 1 +// if b != 0 { +// goto D +// } +// goto C +// C: +// glob_ = !glob_ +// // no y increment +// b = x & 1 +// x = x >> 1 +// if b != 0 { +// goto E +// } +// goto B +// D: +// glob_ = !glob_ +// y += 10 +// b = x & 1 +// x = x >> 1 +// if b != 0 { +// goto Z +// } +// goto B +// E: +// glob_ = !glob_ +// // no y increment +// b = x & 1 +// x = x >> 1 +// if b != 0 { +// goto Z +// } +// goto C +// Z: +// return y +// } + +// {f:BC_CD_BE_BZ_CZ101, +// maxin:32, blocks:[]blo{ +// blo{inc:0, cond:true, succs:[2]int64{1, 2}}, +// blo{inc:1, cond:true, succs:[2]int64{2, 3}}, +// blo{inc:0, cond:true, succs:[2]int64{1, 4}}, +// blo{inc:10, cond:true, succs:[2]int64{1, 25}}, +// blo{inc:0, cond:true, succs:[2]int64{2, 25}},}}, + +var labels string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + +func blocks(spec string) (blocks []string, fnameBase string) { + spec = strings.ToUpper(spec) + blocks = strings.Split(spec, ",") + fnameBase = strings.Replace(spec, ",", "_", -1) + return +} + +func makeFunctionFromFlowGraph(blocks []blo, fname string) string { + s := "" + + for j := range blocks { + // begin block + if j == 0 { + // block A, implicit label + s += ` +func ` + fname + `(x int64) int64 { + y := int64(0) + var b int64 + _ = b` + } else { + // block B,C, etc, explicit label w/ conditional increment + l := labels[j : j+1] + yeq := ` + // no y increment` + if blocks[j].inc != 0 { + yeq = ` + y += ` + fmt.Sprintf("%d", blocks[j].inc) + } + + s += ` +` + l + `: + glob = !glob` + yeq + } + + // edges to successors + if blocks[j].cond { // conditionally branch to second successor + s += ` + b = x & 1 + x = x >> 1 + if b != 0 {` + ` + goto ` + string(labels[blocks[j].succs[1]]) + ` + }` + + } + // branch to first successor + s += ` + goto ` + string(labels[blocks[j].succs[0]]) + } + + // end block (Z) + s += ` +Z: + return y +} +` + return s +} + +var graphs []string = []string{ + "Z", "BZ,Z", "B,BZ", "BZ,BZ", + "ZB,Z", "B,ZB", "ZB,BZ", "ZB,ZB", + + "BC,C,Z", "BC,BC,Z", "BC,BC,BZ", + "BC,Z,Z", "BC,ZC,Z", "BC,ZC,BZ", + "BZ,C,Z", "BZ,BC,Z", "BZ,CZ,Z", + "BZ,C,BZ", "BZ,BC,BZ", "BZ,CZ,BZ", + "BZ,C,CZ", "BZ,BC,CZ", "BZ,CZ,CZ", + + "BC,CD,BE,BZ,CZ", + "BC,BD,CE,CZ,BZ", + "BC,BD,CE,FZ,GZ,F,G", + "BC,BD,CE,FZ,GZ,G,F", + + "BC,DE,BE,FZ,FZ,Z", + "BC,DE,BE,FZ,ZF,Z", + "BC,DE,BE,ZF,FZ,Z", + "BC,DE,EB,FZ,FZ,Z", + "BC,ED,BE,FZ,FZ,Z", + "CB,DE,BE,FZ,FZ,Z", + + "CB,ED,BE,FZ,FZ,Z", + "BC,ED,EB,FZ,ZF,Z", + "CB,DE,EB,ZF,FZ,Z", + "CB,ED,EB,FZ,FZ,Z", + + "BZ,CD,CD,CE,BZ", + "EC,DF,FG,ZC,GB,BE,FD", + "BH,CF,DG,HE,BF,CG,DH,BZ", +} + +// blo describes a block in the generated/interpreted code +type blo struct { + inc int64 // increment amount + cond bool // block ends in conditional + succs [2]int64 +} + +// strings2blocks converts a slice of strings specifying +// successors into a slice of blo encoding the blocks in a +// common form easy to execute or interpret. +func strings2blocks(blocks []string, fname string, i int) (bs []blo, cond uint) { + bs = make([]blo, len(blocks)) + edge := int64(1) + cond = 0 + k := uint(0) + for j, s := range blocks { + if j == 0 { + } else { + if (i>>k)&1 != 0 { + bs[j].inc = edge + edge *= 10 + } + k++ + } + if len(s) > 1 { + bs[j].succs[1] = int64(blocks[j][1] - 'A') + bs[j].cond = true + cond++ + } + bs[j].succs[0] = int64(blocks[j][0] - 'A') + } + return bs, cond +} + +// fmtBlocks writes out the blocks for consumption in the generated test +func fmtBlocks(bs []blo) string { + s := "[]blo{" + for _, b := range bs { + s += fmt.Sprintf("blo{inc:%d, cond:%v, succs:[2]int64{%d, %d}},", b.inc, b.cond, b.succs[0], b.succs[1]) + } + s += "}" + return s +} + +func main() { + fmt.Printf(`// This is a machine-generated test file from flowgraph_generator1.go. +package main +import "fmt" +var glob bool +`) + s := "var funs []fun = []fun{" + for _, g := range graphs { + split, fnameBase := blocks(g) + nconfigs := 1 << uint(len(split)-1) + + for i := 0; i < nconfigs; i++ { + fname := fnameBase + fmt.Sprintf("%b", i) + bs, k := strings2blocks(split, fname, i) + fmt.Printf("%s", makeFunctionFromFlowGraph(bs, fname)) + s += ` + {f:` + fname + `, maxin:` + fmt.Sprintf("%d", 1<<k) + `, blocks:` + fmtBlocks(bs) + `},` + } + + } + s += `} +` + // write types for name+array tables. + fmt.Printf("%s", + ` +type blo struct { + inc int64 + cond bool + succs [2]int64 +} +type fun struct { + f func(int64) int64 + maxin int64 + blocks []blo +} +`) + // write table of function names and blo arrays. + fmt.Printf("%s", s) + + // write interpreter and main/test + fmt.Printf("%s", ` +func interpret(blocks []blo, x int64) (int64, bool) { + y := int64(0) + last := int64(25) // 'Z'-'A' + j := int64(0) + for i := 0; i < 4*len(blocks); i++ { + b := blocks[j] + y += b.inc + next := b.succs[0] + if b.cond { + c := x&1 != 0 + x = x>>1 + if c { + next = b.succs[1] + } + } + if next == last { + return y, true + } + j = next + } + return -1, false +} + +func main() { + sum := int64(0) + for i, f := range funs { + for x := int64(0); x < 16*f.maxin; x++ { + y, ok := interpret(f.blocks, x) + if ok { + yy := f.f(x) + if y != yy { + fmt.Printf("y(%d) != yy(%d), x=%b, i=%d, blocks=%v\n", y, yy, x, i, f.blocks) + return + } + sum += y + } + } + } +// fmt.Printf("Sum of all returns over all terminating inputs is %d\n", sum) +} +`) +} |