flowgraph_generator1.go

     1  // Copyright 2016 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  package main
     6  
     7  import (
     8  	"fmt"
     9  	"strings"
    10  )
    11  
    12  // make fake flow graph.
    13  
    14  // The blocks of the flow graph are designated with letters A
    15  // through Z, always including A (start block) and Z (exit
    16  // block) The specification of a flow graph is a comma-
    17  // separated list of block successor words, for blocks ordered
    18  // A, B, C etc, where each block except Z has one or two
    19  // successors, and any block except A can be a target. Within
    20  // the generated code, each block with two successors includes
    21  // a conditional testing x & 1 != 0 (x is the input parameter
    22  // to the generated function) and also unconditionally shifts x
    23  // right by one, so that different inputs generate different
    24  // execution paths, including loops. Every block inverts a
    25  // global binary to ensure it is not empty. For a flow graph
    26  // with J words (J+1 blocks), a J-1 bit serial number specifies
    27  // which blocks (not including A and Z) include an increment of
    28  // the return variable y by increasing powers of 10, and a
    29  // different version of the test function is created for each
    30  // of the 2-to-the-(J-1) serial numbers.
    31  
    32  // For each generated function a compact summary is also
    33  // created so that the generated function can be simulated
    34  // with a simple interpreter to sanity check the behavior of
    35  // the compiled code.
    36  
    37  // For example:
    38  
    39  // func BC_CD_BE_BZ_CZ101(x int64) int64 {
    40  // 	y := int64(0)
    41  // 	var b int64
    42  // 	_ = b
    43  // 	b = x & 1
    44  // 	x = x >> 1
    45  // 	if b != 0 {
    46  // 		goto C
    47  // 	}
    48  // 	goto B
    49  // B:
    50  // 	glob_ = !glob_
    51  // 	y += 1
    52  // 	b = x & 1
    53  // 	x = x >> 1
    54  // 	if b != 0 {
    55  // 		goto D
    56  // 	}
    57  // 	goto C
    58  // C:
    59  // 	glob_ = !glob_
    60  // 	// no y increment
    61  // 	b = x & 1
    62  // 	x = x >> 1
    63  // 	if b != 0 {
    64  // 		goto E
    65  // 	}
    66  // 	goto B
    67  // D:
    68  // 	glob_ = !glob_
    69  // 	y += 10
    70  // 	b = x & 1
    71  // 	x = x >> 1
    72  // 	if b != 0 {
    73  // 		goto Z
    74  // 	}
    75  // 	goto B
    76  // E:
    77  // 	glob_ = !glob_
    78  // 	// no y increment
    79  // 	b = x & 1
    80  // 	x = x >> 1
    81  // 	if b != 0 {
    82  // 		goto Z
    83  // 	}
    84  // 	goto C
    85  // Z:
    86  // 	return y
    87  // }
    88  
    89  // {f:BC_CD_BE_BZ_CZ101,
    90  //  maxin:32, blocks:[]blo{
    91  //  	blo{inc:0, cond:true, succs:[2]int64{1, 2}},
    92  //  	blo{inc:1, cond:true, succs:[2]int64{2, 3}},
    93  //  	blo{inc:0, cond:true, succs:[2]int64{1, 4}},
    94  //  	blo{inc:10, cond:true, succs:[2]int64{1, 25}},
    95  //  	blo{inc:0, cond:true, succs:[2]int64{2, 25}},}},
    96  
    97  var labels string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    98  
    99  func blocks(spec string) (blocks []string, fnameBase string) {
   100  	spec = strings.ToUpper(spec)
   101  	blocks = strings.Split(spec, ",")
   102  	fnameBase = strings.Replace(spec, ",", "_", -1)
   103  	return
   104  }
   105  
   106  func makeFunctionFromFlowGraph(blocks []blo, fname string) string {
   107  	s := ""
   108  
   109  	for j := range blocks {
   110  		// begin block
   111  		if j == 0 {
   112  			// block A, implicit label
   113  			s += `
   114  func ` + fname + `(x int64) int64 {
   115  	y := int64(0)
   116  	var b int64
   117  	_ = b`
   118  		} else {
   119  			// block B,C, etc, explicit label w/ conditional increment
   120  			l := labels[j : j+1]
   121  			yeq := `
   122  	// no y increment`
   123  			if blocks[j].inc != 0 {
   124  				yeq = `
   125  	y += ` + fmt.Sprintf("%d", blocks[j].inc)
   126  			}
   127  
   128  			s += `
   129  ` + l + `:
   130  	glob = !glob` + yeq
   131  		}
   132  
   133  		// edges to successors
   134  		if blocks[j].cond { // conditionally branch to second successor
   135  			s += `
   136  	b = x & 1
   137  	x = x >> 1
   138  	if b != 0 {` + `
   139  		goto ` + string(labels[blocks[j].succs[1]]) + `
   140  	}`
   141  
   142  		}
   143  		// branch to first successor
   144  		s += `
   145  	goto ` + string(labels[blocks[j].succs[0]])
   146  	}
   147  
   148  	// end block (Z)
   149  	s += `
   150  Z:
   151  	return y
   152  }
   153  `
   154  	return s
   155  }
   156  
   157  var graphs []string = []string{
   158  	"Z", "BZ,Z", "B,BZ", "BZ,BZ",
   159  	"ZB,Z", "B,ZB", "ZB,BZ", "ZB,ZB",
   160  
   161  	"BC,C,Z", "BC,BC,Z", "BC,BC,BZ",
   162  	"BC,Z,Z", "BC,ZC,Z", "BC,ZC,BZ",
   163  	"BZ,C,Z", "BZ,BC,Z", "BZ,CZ,Z",
   164  	"BZ,C,BZ", "BZ,BC,BZ", "BZ,CZ,BZ",
   165  	"BZ,C,CZ", "BZ,BC,CZ", "BZ,CZ,CZ",
   166  
   167  	"BC,CD,BE,BZ,CZ",
   168  	"BC,BD,CE,CZ,BZ",
   169  	"BC,BD,CE,FZ,GZ,F,G",
   170  	"BC,BD,CE,FZ,GZ,G,F",
   171  
   172  	"BC,DE,BE,FZ,FZ,Z",
   173  	"BC,DE,BE,FZ,ZF,Z",
   174  	"BC,DE,BE,ZF,FZ,Z",
   175  	"BC,DE,EB,FZ,FZ,Z",
   176  	"BC,ED,BE,FZ,FZ,Z",
   177  	"CB,DE,BE,FZ,FZ,Z",
   178  
   179  	"CB,ED,BE,FZ,FZ,Z",
   180  	"BC,ED,EB,FZ,ZF,Z",
   181  	"CB,DE,EB,ZF,FZ,Z",
   182  	"CB,ED,EB,FZ,FZ,Z",
   183  
   184  	"BZ,CD,CD,CE,BZ",
   185  	"EC,DF,FG,ZC,GB,BE,FD",
   186  	"BH,CF,DG,HE,BF,CG,DH,BZ",
   187  }
   188  
   189  // blo describes a block in the generated/interpreted code
   190  type blo struct {
   191  	inc   int64 // increment amount
   192  	cond  bool  // block ends in conditional
   193  	succs [2]int64
   194  }
   195  
   196  // strings2blocks converts a slice of strings specifying
   197  // successors into a slice of blo encoding the blocks in a
   198  // common form easy to execute or interpret.
   199  func strings2blocks(blocks []string, fname string, i int) (bs []blo, cond uint) {
   200  	bs = make([]blo, len(blocks))
   201  	edge := int64(1)
   202  	cond = 0
   203  	k := uint(0)
   204  	for j, s := range blocks {
   205  		if j == 0 {
   206  		} else {
   207  			if (i>>k)&1 != 0 {
   208  				bs[j].inc = edge
   209  				edge *= 10
   210  			}
   211  			k++
   212  		}
   213  		if len(s) > 1 {
   214  			bs[j].succs[1] = int64(blocks[j][1] - 'A')
   215  			bs[j].cond = true
   216  			cond++
   217  		}
   218  		bs[j].succs[0] = int64(blocks[j][0] - 'A')
   219  	}
   220  	return bs, cond
   221  }
   222  
   223  // fmtBlocks writes out the blocks for consumption in the generated test
   224  func fmtBlocks(bs []blo) string {
   225  	s := "[]blo{"
   226  	for _, b := range bs {
   227  		s += fmt.Sprintf("blo{inc:%d, cond:%v, succs:[2]int64{%d, %d}},", b.inc, b.cond, b.succs[0], b.succs[1])
   228  	}
   229  	s += "}"
   230  	return s
   231  }
   232  
   233  func main() {
   234  	fmt.Printf(`// This is a machine-generated test file from flowgraph_generator1.go.
   235  package main
   236  import "fmt"
   237  var glob bool
   238  `)
   239  	s := "var funs []fun = []fun{"
   240  	for _, g := range graphs {
   241  		split, fnameBase := blocks(g)
   242  		nconfigs := 1 << uint(len(split)-1)
   243  
   244  		for i := 0; i < nconfigs; i++ {
   245  			fname := fnameBase + fmt.Sprintf("%b", i)
   246  			bs, k := strings2blocks(split, fname, i)
   247  			fmt.Printf("%s", makeFunctionFromFlowGraph(bs, fname))
   248  			s += `
   249  		{f:` + fname + `, maxin:` + fmt.Sprintf("%d", 1<<k) + `, blocks:` + fmtBlocks(bs) + `},`
   250  		}
   251  
   252  	}
   253  	s += `}
   254  `
   255  	// write types for name+array tables.
   256  	fmt.Printf("%s",
   257  		`
   258  type blo struct {
   259  	inc   int64
   260  	cond  bool
   261  	succs [2]int64
   262  }
   263  type fun struct {
   264  	f      func(int64) int64
   265  	maxin  int64
   266  	blocks []blo
   267  }
   268  `)
   269  	// write table of function names and blo arrays.
   270  	fmt.Printf("%s", s)
   271  
   272  	// write interpreter and main/test
   273  	fmt.Printf("%s", `
   274  func interpret(blocks []blo, x int64) (int64, bool) {
   275  	y := int64(0)
   276  	last := int64(25) // 'Z'-'A'
   277  	j := int64(0)
   278  	for i := 0; i < 4*len(blocks); i++ {
   279  		b := blocks[j]
   280  		y += b.inc
   281  		next := b.succs[0]
   282  		if b.cond {
   283  			c := x&1 != 0
   284  			x = x>>1
   285  			if c {
   286  				next = b.succs[1]
   287  			}
   288  		}
   289  		if next == last {
   290  			return y, true
   291  		}
   292  		j = next
   293  	}
   294  	return -1, false
   295  }
   296  
   297  func main() {
   298  	sum := int64(0)
   299  	for i, f := range funs {
   300  		for x := int64(0); x < 16*f.maxin; x++ {
   301  			y, ok := interpret(f.blocks, x)
   302  			if ok {
   303  				yy := f.f(x)
   304  				if y != yy {
   305  					fmt.Printf("y(%d) != yy(%d), x=%b, i=%d, blocks=%v\n", y, yy, x, i, f.blocks)
   306  					return
   307  				}
   308  				sum += y
   309  			}
   310  		}
   311  	}
   312  //	fmt.Printf("Sum of all returns over all terminating inputs is %d\n", sum)
   313  }
   314  `)
   315  }
   316
View as plain text