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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
// 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
// layout orders basic blocks in f with the goal of minimizing control flow instructions.
// After this phase returns, the order of f.Blocks matters and is the order
// in which those blocks will appear in the assembly output.
func layout(f *Func) {
f.Blocks = layoutOrder(f)
}
// Register allocation may use a different order which has constraints
// imposed by the linear-scan algorithm. Note that f.pass here is
// regalloc, so the switch is conditional on -d=ssa/regalloc/test=N
func layoutRegallocOrder(f *Func) []*Block {
switch f.pass.test {
case 0: // layout order
return layoutOrder(f)
case 1: // existing block order
return f.Blocks
case 2: // reverse of postorder; legal, but usually not good.
po := f.postorder()
visitOrder := make([]*Block, len(po))
for i, b := range po {
j := len(po) - i - 1
visitOrder[j] = b
}
return visitOrder
}
return nil
}
func layoutOrder(f *Func) []*Block {
order := make([]*Block, 0, f.NumBlocks())
scheduled := make([]bool, f.NumBlocks())
idToBlock := make([]*Block, f.NumBlocks())
indegree := make([]int, f.NumBlocks())
posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
defer f.retSparseSet(posdegree)
zerodegree := f.newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
defer f.retSparseSet(zerodegree)
exit := f.newSparseSet(f.NumBlocks()) // exit blocks
defer f.retSparseSet(exit)
// Populate idToBlock and find exit blocks.
for _, b := range f.Blocks {
idToBlock[b.ID] = b
if b.Kind == BlockExit {
exit.add(b.ID)
}
}
// Expand exit to include blocks post-dominated by exit blocks.
for {
changed := false
for _, id := range exit.contents() {
b := idToBlock[id]
NextPred:
for _, pe := range b.Preds {
p := pe.b
if exit.contains(p.ID) {
continue
}
for _, s := range p.Succs {
if !exit.contains(s.b.ID) {
continue NextPred
}
}
// All Succs are in exit; add p.
exit.add(p.ID)
changed = true
}
}
if !changed {
break
}
}
// Initialize indegree of each block
for _, b := range f.Blocks {
if exit.contains(b.ID) {
// exit blocks are always scheduled last
continue
}
indegree[b.ID] = len(b.Preds)
if len(b.Preds) == 0 {
zerodegree.add(b.ID)
} else {
posdegree.add(b.ID)
}
}
bid := f.Entry.ID
blockloop:
for {
// add block to schedule
b := idToBlock[bid]
order = append(order, b)
scheduled[bid] = true
if len(order) == len(f.Blocks) {
break
}
for _, e := range b.Succs {
c := e.b
indegree[c.ID]--
if indegree[c.ID] == 0 {
posdegree.remove(c.ID)
zerodegree.add(c.ID)
}
}
// Pick the next block to schedule
// Pick among the successor blocks that have not been scheduled yet.
// Use likely direction if we have it.
var likely *Block
switch b.Likely {
case BranchLikely:
likely = b.Succs[0].b
case BranchUnlikely:
likely = b.Succs[1].b
}
if likely != nil && !scheduled[likely.ID] {
bid = likely.ID
continue
}
// Use degree for now.
bid = 0
mindegree := f.NumBlocks()
for _, e := range order[len(order)-1].Succs {
c := e.b
if scheduled[c.ID] || c.Kind == BlockExit {
continue
}
if indegree[c.ID] < mindegree {
mindegree = indegree[c.ID]
bid = c.ID
}
}
if bid != 0 {
continue
}
// TODO: improve this part
// No successor of the previously scheduled block works.
// Pick a zero-degree block if we can.
for zerodegree.size() > 0 {
cid := zerodegree.pop()
if !scheduled[cid] {
bid = cid
continue blockloop
}
}
// Still nothing, pick any non-exit block.
for posdegree.size() > 0 {
cid := posdegree.pop()
if !scheduled[cid] {
bid = cid
continue blockloop
}
}
// Pick any exit block.
// TODO: Order these to minimize jump distances?
for {
cid := exit.pop()
if !scheduled[cid] {
bid = cid
continue blockloop
}
}
}
f.laidout = true
return order
//f.Blocks = order
}
|
