-
Notifications
You must be signed in to change notification settings - Fork 0
/
dependent.go
78 lines (71 loc) · 2 KB
/
dependent.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
package optimize
import (
"github.com/andrewarchi/graph"
"github.com/andrewarchi/nebula/ir"
)
// ControlFlowGraph creates a directed graph with edges representing the
// connections between basic blocks.
func ControlFlowGraph(p *ir.Program) graph.Graph {
ids := make(map[*ir.BasicBlock]int)
for _, block := range p.Blocks {
ids[block] = block.ID
}
g := graph.NewGraph(uint(len(p.Blocks)))
for i, block := range p.Blocks {
for _, exit := range block.Succs() {
g.Add(uint(i), uint(ids[exit]))
}
}
return g
}
// DependenceGraph creates an undirected graph with edges representing
// dependencies between nodes.
func DependenceGraph(block *ir.BasicBlock) graph.Graph {
g := graph.NewGraph(uint(len(block.Nodes)))
for i, ni := range block.Nodes {
for j, nj := range block.Nodes[i+1:] {
if Dependent(ni, nj) {
g.AddUndirected(uint(i), uint(j))
}
}
}
return g
}
// Dependent returns whether two non-branching nodes are dependent. True
// is returned when node B is dependent on node A. Nodes are dependent
// when both are I/O instructions, one is I/O and the other can throw,
// both assign to the same value, or one reads the value assigned to by
// the other. Dependent is reflexive.
func Dependent(a, b ir.Inst) bool {
aIO, bIO := isIO(a), isIO(b)
return aIO && bIO ||
aIO && canThrow(b) || bIO && canThrow(a) ||
references(a, b) || references(b, a)
}
func isIO(inst ir.Inst) bool {
switch inst.(type) {
case *ir.PrintStmt, *ir.ReadExpr:
return true
}
return false
}
// canThrow returns whether the node is a division with a non-constant
// RHS.
// TODO: create div trap to replace this.
func canThrow(inst ir.Inst) bool {
if bin, ok := inst.(*ir.BinaryExpr); ok && bin.Op == ir.Div {
_, ok := bin.Operand(1).Def().(*ir.IntConst)
return !ok
}
return false
}
// references returns whether node B references the assignment of
// node A.
func references(a, b ir.Inst) bool {
if val, ok := a.(ir.Value); ok {
if user, ok := b.(ir.User); ok {
return user.UsesValue(val)
}
}
return false
}