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
|
// Copyright 2015 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 ssa
// critical splits critical edges (those that go from a block with
// more than one outedge to a block with more than one inedge).
// Regalloc wants a critical-edge-free CFG so it can implement phi values.
func critical(f *Func) {
// maps from phi arg ID to the new block created for that argument
blocks := f.Cache.allocBlockSlice(f.NumValues())
defer f.Cache.freeBlockSlice(blocks)
// need to iterate over f.Blocks without range, as we might
// need to split critical edges on newly constructed blocks
for j := 0; j < len(f.Blocks); j++ {
b := f.Blocks[j]
if len(b.Preds) <= 1 {
continue
}
var phi *Value
// determine if we've only got a single phi in this
// block, this is easier to handle than the general
// case of a block with multiple phi values.
for _, v := range b.Values {
if v.Op == OpPhi {
if phi != nil {
phi = nil
break
}
phi = v
}
}
// reset our block map
if phi != nil {
for _, v := range phi.Args {
blocks[v.ID] = nil
}
}
// split input edges coming from multi-output blocks.
for i := 0; i < len(b.Preds); {
e := b.Preds[i]
p := e.b
pi := e.i
if p.Kind == BlockPlain {
i++
continue // only single output block
}
var d *Block // new block used to remove critical edge
reusedBlock := false // if true, then this is not the first use of this block
if phi != nil {
argID := phi.Args[i].ID
// find or record the block that we used to split
// critical edges for this argument
if d = blocks[argID]; d == nil {
// splitting doesn't necessarily remove the critical edge,
// since we're iterating over len(f.Blocks) above, this forces
// the new blocks to be re-examined.
d = f.NewBlock(BlockPlain)
d.Pos = p.Pos
blocks[argID] = d
if f.pass.debug > 0 {
f.Warnl(p.Pos, "split critical edge")
}
} else {
reusedBlock = true
}
} else {
// no existing block, so allocate a new block
// to place on the edge
d = f.NewBlock(BlockPlain)
d.Pos = p.Pos
if f.pass.debug > 0 {
f.Warnl(p.Pos, "split critical edge")
}
}
// if this not the first argument for the
// block, then we need to remove the
// corresponding elements from the block
// predecessors and phi args
if reusedBlock {
// Add p->d edge
p.Succs[pi] = Edge{d, len(d.Preds)}
d.Preds = append(d.Preds, Edge{p, pi})
// Remove p as a predecessor from b.
b.removePred(i)
// Update corresponding phi args
b.removePhiArg(phi, i)
// splitting occasionally leads to a phi having
// a single argument (occurs with -N)
// Don't increment i in this case because we moved
// an unprocessed predecessor down into slot i.
} else {
// splice it in
p.Succs[pi] = Edge{d, 0}
b.Preds[i] = Edge{d, 0}
d.Preds = append(d.Preds, Edge{p, pi})
d.Succs = append(d.Succs, Edge{b, i})
i++
}
}
}
}
|
