1
2
3
4
5 package ssa
6
7 import (
8 "cmd/compile/internal/ir"
9 "cmd/compile/internal/types"
10 )
11
12
13
14
15
16 func dse(f *Func) {
17 var stores []*Value
18 loadUse := f.newSparseSet(f.NumValues())
19 defer f.retSparseSet(loadUse)
20 storeUse := f.newSparseSet(f.NumValues())
21 defer f.retSparseSet(storeUse)
22 shadowed := f.newSparseMap(f.NumValues())
23 defer f.retSparseMap(shadowed)
24
25 localAddrs := map[any]*Value{}
26 for _, b := range f.Blocks {
27
28
29
30 loadUse.clear()
31 storeUse.clear()
32 clear(localAddrs)
33 stores = stores[:0]
34 for _, v := range b.Values {
35 if v.Op == OpPhi {
36
37 continue
38 }
39 if v.Type.IsMemory() {
40 stores = append(stores, v)
41 for _, a := range v.Args {
42 if a.Block == b && a.Type.IsMemory() {
43 storeUse.add(a.ID)
44 if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef {
45
46
47 loadUse.add(a.ID)
48 }
49 }
50 }
51 } else {
52 if v.Op == OpLocalAddr {
53 if _, ok := localAddrs[v.Aux]; !ok {
54 localAddrs[v.Aux] = v
55 }
56 continue
57 }
58 if v.Op == OpInlMark || v.Op == OpConvert {
59
60 continue
61 }
62 for _, a := range v.Args {
63 if a.Block == b && a.Type.IsMemory() {
64 loadUse.add(a.ID)
65 }
66 }
67 }
68 }
69 if len(stores) == 0 {
70 continue
71 }
72
73
74 var last *Value
75 for _, v := range stores {
76 if storeUse.contains(v.ID) {
77 continue
78 }
79 if last != nil {
80 b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
81 }
82 last = v
83 }
84 if last == nil {
85 b.Fatalf("no last store found - cycle?")
86 }
87
88
89
90
91
92
93
94 shadowed.clear()
95 v := last
96
97 walkloop:
98 if loadUse.contains(v.ID) {
99
100
101 shadowed.clear()
102 }
103 if v.Op == OpStore || v.Op == OpZero {
104 ptr := v.Args[0]
105 var off int64
106 for ptr.Op == OpOffPtr {
107 off += ptr.AuxInt
108 ptr = ptr.Args[0]
109 }
110 var sz int64
111 if v.Op == OpStore {
112 sz = v.Aux.(*types.Type).Size()
113 } else {
114 sz = v.AuxInt
115 }
116 if ptr.Op == OpLocalAddr {
117 if la, ok := localAddrs[ptr.Aux]; ok {
118 ptr = la
119 }
120 }
121 srNum, _ := shadowed.get(ptr.ID)
122 sr := shadowRange(srNum)
123 if sr.contains(off, off+sz) {
124
125
126 if v.Op == OpStore {
127
128 v.SetArgs1(v.Args[2])
129 } else {
130
131 v.SetArgs1(v.Args[1])
132 }
133 v.Aux = nil
134 v.AuxInt = 0
135 v.Op = OpCopy
136 } else {
137
138 shadowed.set(ptr.ID, int32(sr.merge(off, off+sz)))
139 }
140 }
141
142 if v.Op == OpPhi {
143
144
145
146
147 continue
148 }
149 for _, a := range v.Args {
150 if a.Block == b && a.Type.IsMemory() {
151 v = a
152 goto walkloop
153 }
154 }
155 }
156 }
157
158
159
160
161 type shadowRange int32
162
163 func (sr shadowRange) lo() int64 {
164 return int64(sr & 0xffff)
165 }
166
167 func (sr shadowRange) hi() int64 {
168 return int64((sr >> 16) & 0xffff)
169 }
170
171
172 func (sr shadowRange) contains(lo, hi int64) bool {
173 return lo >= sr.lo() && hi <= sr.hi()
174 }
175
176
177
178 func (sr shadowRange) merge(lo, hi int64) shadowRange {
179 if lo < 0 || hi > 0xffff {
180
181 return sr
182 }
183 if sr.lo() == sr.hi() {
184
185 return shadowRange(lo + hi<<16)
186 }
187 if hi < sr.lo() || lo > sr.hi() {
188
189
190
191 if sr.hi()-sr.lo() >= hi-lo {
192 return sr
193 }
194 return shadowRange(lo + hi<<16)
195 }
196
197 return shadowRange(min(lo, sr.lo()) + max(hi, sr.hi())<<16)
198 }
199
200
201
202
203
204 func elimDeadAutosGeneric(f *Func) {
205 addr := make(map[*Value]*ir.Name)
206 elim := make(map[*Value]*ir.Name)
207 var used ir.NameSet
208
209
210 visit := func(v *Value) (changed bool) {
211 args := v.Args
212 switch v.Op {
213 case OpAddr, OpLocalAddr:
214
215 n, ok := v.Aux.(*ir.Name)
216 if !ok || n.Class != ir.PAUTO {
217 return
218 }
219 if addr[v] == nil {
220 addr[v] = n
221 changed = true
222 }
223 return
224 case OpVarDef:
225
226 n, ok := v.Aux.(*ir.Name)
227 if !ok || n.Class != ir.PAUTO {
228 return
229 }
230 if elim[v] == nil {
231 elim[v] = n
232 changed = true
233 }
234 return
235 case OpVarLive:
236
237
238
239
240
241
242 n, ok := v.Aux.(*ir.Name)
243 if !ok || n.Class != ir.PAUTO {
244 return
245 }
246 if !used.Has(n) {
247 used.Add(n)
248 changed = true
249 }
250 return
251 case OpStore, OpMove, OpZero:
252
253 n, ok := addr[args[0]]
254 if ok && elim[v] == nil {
255 elim[v] = n
256 changed = true
257 }
258
259 args = args[1:]
260 }
261
262
263
264
265 if v.Op.SymEffect() != SymNone && v.Op != OpArg {
266 panic("unhandled op with sym effect")
267 }
268
269 if v.Uses == 0 && v.Op != OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() || len(args) == 0 {
270
271
272 return
273 }
274
275
276
277
278 if v.Type.IsMemory() || v.Type.IsFlags() || v.Op == OpPhi || v.MemoryArg() != nil {
279 for _, a := range args {
280 if n, ok := addr[a]; ok {
281 if !used.Has(n) {
282 used.Add(n)
283 changed = true
284 }
285 }
286 }
287 return
288 }
289
290
291 var node *ir.Name
292 for _, a := range args {
293 if n, ok := addr[a]; ok && !used.Has(n) {
294 if node == nil {
295 node = n
296 } else if node != n {
297
298
299
300
301
302 used.Add(n)
303 changed = true
304 }
305 }
306 }
307 if node == nil {
308 return
309 }
310 if addr[v] == nil {
311
312 addr[v] = node
313 changed = true
314 return
315 }
316 if addr[v] != node {
317
318 used.Add(node)
319 changed = true
320 }
321 return
322 }
323
324 iterations := 0
325 for {
326 if iterations == 4 {
327
328 return
329 }
330 iterations++
331 changed := false
332 for _, b := range f.Blocks {
333 for _, v := range b.Values {
334 changed = visit(v) || changed
335 }
336
337 for _, c := range b.ControlValues() {
338 if n, ok := addr[c]; ok && !used.Has(n) {
339 used.Add(n)
340 changed = true
341 }
342 }
343 }
344 if !changed {
345 break
346 }
347 }
348
349
350 for v, n := range elim {
351 if used.Has(n) {
352 continue
353 }
354
355 v.SetArgs1(v.MemoryArg())
356 v.Aux = nil
357 v.AuxInt = 0
358 v.Op = OpCopy
359 }
360 }
361
362
363
364 func elimUnreadAutos(f *Func) {
365
366
367
368 var seen ir.NameSet
369 var stores []*Value
370 for _, b := range f.Blocks {
371 for _, v := range b.Values {
372 n, ok := v.Aux.(*ir.Name)
373 if !ok {
374 continue
375 }
376 if n.Class != ir.PAUTO {
377 continue
378 }
379
380 effect := v.Op.SymEffect()
381 switch effect {
382 case SymNone, SymWrite:
383
384
385
386 if !seen.Has(n) {
387 stores = append(stores, v)
388 }
389 default:
390
391
392
393
394
395 if v.Uses > 0 {
396 seen.Add(n)
397 }
398 }
399 }
400 }
401
402
403 for _, store := range stores {
404 n, _ := store.Aux.(*ir.Name)
405 if seen.Has(n) {
406 continue
407 }
408
409
410 store.SetArgs1(store.MemoryArg())
411 store.Aux = nil
412 store.AuxInt = 0
413 store.Op = OpCopy
414 }
415 }
416
View as plain text