1
2
3
4
5 package ssa
6
7 import (
8 "cmd/compile/internal/types"
9 "cmd/internal/src"
10 "fmt"
11 "sort"
12 )
13
14
15
16
17 func cse(f *Func) {
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 a := make([]*Value, 0, f.NumValues())
35 if f.auxmap == nil {
36 f.auxmap = auxmap{}
37 }
38 for _, b := range f.Blocks {
39 for _, v := range b.Values {
40 if v.Type.IsMemory() {
41 continue
42 }
43 if f.auxmap[v.Aux] == 0 {
44 f.auxmap[v.Aux] = int32(len(f.auxmap)) + 1
45 }
46 a = append(a, v)
47 }
48 }
49 partition := partitionValues(a, f.auxmap)
50
51
52 valueEqClass := make([]ID, f.NumValues())
53 for _, b := range f.Blocks {
54 for _, v := range b.Values {
55
56 valueEqClass[v.ID] = -v.ID
57 }
58 }
59 var pNum ID = 1
60 for _, e := range partition {
61 if f.pass.debug > 1 && len(e) > 500 {
62 fmt.Printf("CSE.large partition (%d): ", len(e))
63 for j := 0; j < 3; j++ {
64 fmt.Printf("%s ", e[j].LongString())
65 }
66 fmt.Println()
67 }
68
69 for _, v := range e {
70 valueEqClass[v.ID] = pNum
71 }
72 if f.pass.debug > 2 && len(e) > 1 {
73 fmt.Printf("CSE.partition #%d:", pNum)
74 for _, v := range e {
75 fmt.Printf(" %s", v.String())
76 }
77 fmt.Printf("\n")
78 }
79 pNum++
80 }
81
82
83
84
85 var splitPoints []int
86 byArgClass := new(partitionByArgClass)
87 for {
88 changed := false
89
90
91
92 for i := 0; i < len(partition); i++ {
93 e := partition[i]
94
95 if opcodeTable[e[0].Op].commutative {
96
97 for _, v := range e {
98 if valueEqClass[v.Args[0].ID] > valueEqClass[v.Args[1].ID] {
99 v.Args[0], v.Args[1] = v.Args[1], v.Args[0]
100 }
101 }
102 }
103
104
105 byArgClass.a = e
106 byArgClass.eqClass = valueEqClass
107 sort.Sort(byArgClass)
108
109
110 splitPoints = append(splitPoints[:0], 0)
111 for j := 1; j < len(e); j++ {
112 v, w := e[j-1], e[j]
113
114 eqArgs := true
115 for k, a := range v.Args {
116 b := w.Args[k]
117 if valueEqClass[a.ID] != valueEqClass[b.ID] {
118 eqArgs = false
119 break
120 }
121 }
122 if !eqArgs {
123 splitPoints = append(splitPoints, j)
124 }
125 }
126 if len(splitPoints) == 1 {
127 continue
128 }
129
130
131 partition[i] = partition[len(partition)-1]
132 partition = partition[:len(partition)-1]
133 i--
134
135
136 splitPoints = append(splitPoints, len(e))
137 for j := 0; j < len(splitPoints)-1; j++ {
138 f := e[splitPoints[j]:splitPoints[j+1]]
139 if len(f) == 1 {
140
141 valueEqClass[f[0].ID] = -f[0].ID
142 continue
143 }
144 for _, v := range f {
145 valueEqClass[v.ID] = pNum
146 }
147 pNum++
148 partition = append(partition, f)
149 }
150 changed = true
151 }
152
153 if !changed {
154 break
155 }
156 }
157
158 sdom := f.Sdom()
159
160
161
162 rewrite := make([]*Value, f.NumValues())
163 byDom := new(partitionByDom)
164 for _, e := range partition {
165 byDom.a = e
166 byDom.sdom = sdom
167 sort.Sort(byDom)
168 for i := 0; i < len(e)-1; i++ {
169
170 v := e[i]
171 if v == nil {
172 continue
173 }
174
175 e[i] = nil
176
177 for j := i + 1; j < len(e); j++ {
178 w := e[j]
179 if w == nil {
180 continue
181 }
182 if sdom.IsAncestorEq(v.Block, w.Block) {
183 rewrite[w.ID] = v
184 e[j] = nil
185 } else {
186
187 break
188 }
189 }
190 }
191 }
192
193 rewrites := int64(0)
194
195
196 for _, b := range f.Blocks {
197 for _, v := range b.Values {
198 for i, w := range v.Args {
199 if x := rewrite[w.ID]; x != nil {
200 if w.Pos.IsStmt() == src.PosIsStmt {
201
202
203
204 if w.Block == v.Block && w.Pos.Line() == v.Pos.Line() {
205 v.Pos = v.Pos.WithIsStmt()
206 w.Pos = w.Pos.WithNotStmt()
207 }
208 }
209 v.SetArg(i, x)
210 rewrites++
211 }
212 }
213 }
214 for i, v := range b.ControlValues() {
215 if x := rewrite[v.ID]; x != nil {
216 if v.Op == OpNilCheck {
217
218
219 continue
220 }
221 b.ReplaceControl(i, x)
222 }
223 }
224 }
225
226 if f.pass.stats > 0 {
227 f.LogStat("CSE REWRITES", rewrites)
228 }
229 }
230
231
232
233
234 type eqclass []*Value
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250 func partitionValues(a []*Value, auxIDs auxmap) []eqclass {
251 sort.Sort(sortvalues{a, auxIDs})
252
253 var partition []eqclass
254 for len(a) > 0 {
255 v := a[0]
256 j := 1
257 for ; j < len(a); j++ {
258 w := a[j]
259 if cmpVal(v, w, auxIDs) != types.CMPeq {
260 break
261 }
262 }
263 if j > 1 {
264 partition = append(partition, a[:j])
265 }
266 a = a[j:]
267 }
268
269 return partition
270 }
271 func lt2Cmp(isLt bool) types.Cmp {
272 if isLt {
273 return types.CMPlt
274 }
275 return types.CMPgt
276 }
277
278 type auxmap map[interface{}]int32
279
280 func cmpVal(v, w *Value, auxIDs auxmap) types.Cmp {
281
282 if v.Op != w.Op {
283 return lt2Cmp(v.Op < w.Op)
284 }
285 if v.AuxInt != w.AuxInt {
286 return lt2Cmp(v.AuxInt < w.AuxInt)
287 }
288 if len(v.Args) != len(w.Args) {
289 return lt2Cmp(len(v.Args) < len(w.Args))
290 }
291 if v.Op == OpPhi && v.Block != w.Block {
292 return lt2Cmp(v.Block.ID < w.Block.ID)
293 }
294 if v.Type.IsMemory() {
295
296
297 return lt2Cmp(v.ID < w.ID)
298 }
299
300
301
302 if v.Op != OpSelect0 && v.Op != OpSelect1 {
303 if tc := v.Type.Compare(w.Type); tc != types.CMPeq {
304 return tc
305 }
306 }
307
308 if v.Aux != w.Aux {
309 if v.Aux == nil {
310 return types.CMPlt
311 }
312 if w.Aux == nil {
313 return types.CMPgt
314 }
315 return lt2Cmp(auxIDs[v.Aux] < auxIDs[w.Aux])
316 }
317
318 return types.CMPeq
319 }
320
321
322 type sortvalues struct {
323 a []*Value
324 auxIDs auxmap
325 }
326
327 func (sv sortvalues) Len() int { return len(sv.a) }
328 func (sv sortvalues) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] }
329 func (sv sortvalues) Less(i, j int) bool {
330 v := sv.a[i]
331 w := sv.a[j]
332 if cmp := cmpVal(v, w, sv.auxIDs); cmp != types.CMPeq {
333 return cmp == types.CMPlt
334 }
335
336
337 return v.ID < w.ID
338 }
339
340 type partitionByDom struct {
341 a []*Value
342 sdom SparseTree
343 }
344
345 func (sv partitionByDom) Len() int { return len(sv.a) }
346 func (sv partitionByDom) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] }
347 func (sv partitionByDom) Less(i, j int) bool {
348 v := sv.a[i]
349 w := sv.a[j]
350 return sv.sdom.domorder(v.Block) < sv.sdom.domorder(w.Block)
351 }
352
353 type partitionByArgClass struct {
354 a []*Value
355 eqClass []ID
356 }
357
358 func (sv partitionByArgClass) Len() int { return len(sv.a) }
359 func (sv partitionByArgClass) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] }
360 func (sv partitionByArgClass) Less(i, j int) bool {
361 v := sv.a[i]
362 w := sv.a[j]
363 for i, a := range v.Args {
364 b := w.Args[i]
365 if sv.eqClass[a.ID] < sv.eqClass[b.ID] {
366 return true
367 }
368 if sv.eqClass[a.ID] > sv.eqClass[b.ID] {
369 return false
370 }
371 }
372 return false
373 }
374
View as plain text