-
Notifications
You must be signed in to change notification settings - Fork 14
/
build.go
158 lines (135 loc) · 3.57 KB
/
build.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
package acc
import (
"fmt"
"github.com/mmcloughlin/addchain/acc/ast"
"github.com/mmcloughlin/addchain/acc/ir"
"github.com/mmcloughlin/addchain/acc/pass"
"github.com/mmcloughlin/addchain/internal/errutil"
)
// complexitylimit is the maximum number of operators the builder will allow an
// expression to have.
const complexitylimit = 5
// Build AST from a program in intermediate representation.
func Build(p *ir.Program) (*ast.Chain, error) {
// Run some analysis passes first.
err := pass.Exec(p,
pass.Func(pass.ReadCounts),
pass.NameByteValues,
pass.NameXRuns,
)
if err != nil {
return nil, err
}
// Delegate to builder.
b := newbuilder(p)
if err := b.process(); err != nil {
return nil, err
}
return b.chain, nil
}
type builder struct {
chain *ast.Chain
prog *ir.Program
expr map[int]ast.Expr
}
func newbuilder(p *ir.Program) *builder {
return &builder{
chain: &ast.Chain{},
prog: p,
expr: map[int]ast.Expr{},
}
}
func (b *builder) process() error {
insts := b.prog.Instructions
n := len(insts)
complexity := 0
for i := 0; i < n; i++ {
complexity++
inst := insts[i]
out := inst.Output
// Build expression for the result of this instruction.
e, err := b.operator(inst.Op)
if err != nil {
return err
}
b.expr[out.Index] = e
// If this output is read only by the following instruction, we don't need to
// commit it to a variable.
anon := out.Identifier == ""
usedonce := b.prog.ReadCount[out.Index] == 1
usednext := i+1 < n && ir.HasInput(insts[i+1].Op, out.Index)
if anon && usedonce && usednext && complexity < complexitylimit {
continue
}
// Otherwise write a statement for it.
b.commit(inst.Output)
complexity = 0
}
// Clear the name of the final statement.
b.chain.Statements[len(b.chain.Statements)-1].Name = ""
return nil
}
func (b *builder) operator(op ir.Op) (ast.Expr, error) {
switch o := op.(type) {
case ir.Add:
return b.add(o)
case ir.Double:
return ast.Double{
X: b.operand(o.X),
}, nil
case ir.Shift:
return ast.Shift{
X: b.operand(o.X),
S: o.S,
}, nil
default:
return nil, errutil.UnexpectedType(op)
}
}
func (b *builder) add(a ir.Add) (ast.Expr, error) {
// Addition operator construction is slightly delcate, since operand order
// determines ordering of execution. By the design of instruction processing
// above, the only way we can have multi-operator expressions is with a
// sequence of operands that are used only once and in the following
// instruction. This implies that only one of x and y can be an operator
// expression. In order to preserve execution order, whichever one that is
// needs to be the first operand.
x := b.operand(a.X)
y := b.operand(a.Y)
switch {
case ast.IsOp(x) && ast.IsOp(y):
return nil, errutil.AssertionFailure("only one of x and y should be an operator expression")
case ast.IsOp(y):
x, y = y, x
case ast.IsOp(x):
// Nothing, it's already the first operand.
}
return ast.Add{
X: x,
Y: y,
}, nil
}
func (b *builder) commit(op *ir.Operand) {
name := ast.Identifier(b.name(op))
stmt := ast.Statement{
Name: name,
Expr: b.operand(op),
}
b.chain.Statements = append(b.chain.Statements, stmt)
b.expr[op.Index] = name
}
// name returns the name for this operand. This is the identifier if available,
// otherwise a sensible default based on the index.
func (b *builder) name(op *ir.Operand) string {
if op.Identifier != "" {
return op.Identifier
}
return fmt.Sprintf("i%d", op.Index)
}
func (b *builder) operand(op *ir.Operand) ast.Expr {
e, ok := b.expr[op.Index]
if !ok {
return ast.Operand(op.Index)
}
return e
}