-
Notifications
You must be signed in to change notification settings - Fork 22
/
pass_layout.go
122 lines (102 loc) · 3.31 KB
/
pass_layout.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
/*
* Copyright 2022 ByteDance Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package ssa
import (
`sort`
)
type _Successor struct {
bb *BasicBlock
prob Likeliness
}
// Layout flattens the CFG into a linear FuncLayout
type Layout struct{}
func (self Layout) flatten(fn *FuncLayout, bb *BasicBlock) {
var ok bool
var nx []_Successor
/* check for visited blocks */
if _, ok = fn.Start[bb.Id]; ok {
return
}
/* mark the starting position, and the corresponding block */
fn.Start[bb.Id] = len(fn.Ins)
fn.Block[len(fn.Ins)] = bb
/* add instructions and the terminator */
fn.Ins = append(fn.Ins, bb.Ins...)
fn.Ins = append(fn.Ins, bb.Term)
/* get all it's successors */
for it := bb.Term.Successors(); it.Next(); {
nx = append(nx, _Successor {
bb : it.Block(),
prob : it.Likeliness(),
})
}
/* sort the likely blocks at front */
sort.Slice(nx, func(i int, j int) bool {
return nx[i].prob == Likely && nx[j].prob == Unlikely
})
/* visit all the successors */
for _, v := range nx {
self.flatten(fn, v.bb)
}
}
func (self Layout) Apply(cfg *CFG) {
cfg.Func.Layout = new(FuncLayout)
cfg.Func.Layout.Start = make(map[int]int, cfg.MaxBlock())
cfg.Func.Layout.Block = make(map[int]*BasicBlock, cfg.MaxBlock())
/* remove all virtual instructions */
cfg.PostOrder().ForEach(func(bb *BasicBlock) {
ins := bb.Ins
bb.Ins = bb.Ins[:0]
/* filter the instructions */
for _, v := range ins {
if _, ok := v.(*IrEntry) ; ok { continue }
if _, ok := v.(*IrClobberList) ; ok { continue }
bb.Ins = append(bb.Ins, v)
}
})
/* retry until no more intermediate blocks found */
for {
var rt bool
var nb *BasicBlock
/* collapse all the intermediate blocks */
cfg.PostOrder().ForEach(func(bb *BasicBlock) {
tr := bb.Term
it := tr.Successors()
/* scan every successors */
for it.Next() {
nx := it.Block()
st := nx.Term.Successors()
/* must have exactly 1 predecessor, exactly 1 successor, and no instructions
* if so, update the successor to skip the intermediate block */
if st.Next() && len(nx.Ins) == 0 && len(nx.Pred) == 1 {
if nb = st.Block(); !st.Next() {
rt = true
it.UpdateBlock(nb)
}
}
}
})
/* rebuild the CFG if needed */
if !rt {
break
} else {
cfg.Rebuild()
}
}
/* flatten the CFG */
root := cfg.Root
self.flatten(cfg.Func.Layout, root)
}