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
5package main
6
7import (
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
97var labels string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
98
99func 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
106func 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 += `
114func ` + 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 += `
150Z:
151	return y
152}
153`
154	return s
155}
156
157var 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
190type 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.
199func 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
224func 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
233func main() {
234	fmt.Printf(`// This is a machine-generated test file from flowgraph_generator1.go.
235package main
236import "fmt"
237var 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		`
258type blo struct {
259	inc   int64
260	cond  bool
261	succs [2]int64
262}
263type 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", `
274func 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
297func 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