1
2
3
4
5 package ssacompile
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 import (
34 "cmd/compile/internal/ir"
35 "cmd/compile/internal/ssa"
36 "cmd/compile/internal/ssa/ssaop"
37 "cmd/compile/internal/types"
38 "fmt"
39 "slices"
40 )
41
42 type leafField struct {
43 off int64
44 typ *types.Type
45 }
46
47 type decomposeCandidate struct {
48 n *ir.Name
49 leaves []leafField
50 leavesByOff map[int64]leafField
51 localAddrs []*ssa.Value
52 unDecomposable bool
53 }
54
55 var decomposeAddrDummyValue = &ssa.Value{}
56
57
58
59
60
61
62
63
64
65
66 func zeroValueForType(f *ssa.Func, t *types.Type) *ssa.Value {
67 switch {
68 case t.IsBoolean():
69 if f == nil {
70 return decomposeAddrDummyValue
71 }
72 return f.ConstBool(t, false)
73 case t.IsInteger():
74 if f == nil {
75 return decomposeAddrDummyValue
76 }
77 switch t.Size() {
78 case 1:
79 return f.ConstInt8(t, 0)
80 case 2:
81 return f.ConstInt16(t, 0)
82 case 4:
83 return f.ConstInt32(t, 0)
84 default:
85 return f.ConstInt64(t, 0)
86 }
87 case t.IsFloat():
88 if f == nil {
89 return decomposeAddrDummyValue
90 }
91 switch t.Size() {
92 case 4:
93 return f.ConstFloat32(t, 0)
94 default:
95 return f.ConstFloat64(t, 0)
96 }
97 case t.IsPtrShaped():
98 if f == nil {
99 return decomposeAddrDummyValue
100 }
101 return f.ConstNil(t)
102 case t.IsString():
103 if f == nil {
104 return decomposeAddrDummyValue
105 }
106 return f.ConstEmptyString(t)
107 case t.IsSlice():
108 if f == nil {
109 return decomposeAddrDummyValue
110 }
111 return f.ConstSlice(t)
112 case t.IsInterface():
113 if f == nil {
114 return decomposeAddrDummyValue
115 }
116 return f.ConstInterface(t)
117 case t.IsSIMD():
118 if f == nil {
119 return decomposeAddrDummyValue
120 }
121 return f.ConstSIMD(t)
122 default:
123
124
125
126 return nil
127 }
128 }
129
130
131
132
133 func decomposeAddr(f *ssa.Func) {
134
135
136
137 demographics, localAddrs, uses := variableDemographics(f)
138 if uses == nil {
139 return
140 }
141 defer func() { uses.free(f) }()
142
143 st := f.NewStats("decomposeAddr")
144
145
146
147
148 maxPartitions := f.Pass.Val("maxpartitions", 64)
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171 maxActivePartitions := f.Pass.Val("maxactivepartitions", 4)
172
173 type partitionStatus int
174 const (
175 partSuccess partitionStatus = iota
176 partTooMany
177 partLarge
178 )
179
180
181 var getLeafFields func(t *types.Type, base int64) (leaves []leafField, status partitionStatus)
182 getLeafFields = func(t *types.Type, base int64) (leaves []leafField, status partitionStatus) {
183
184
185 checkField := func(t2 *types.Type, offset int64) partitionStatus {
186 ls, s := getLeafFields(t2, offset)
187 if s != partSuccess {
188 return s
189 }
190 if int64(len(leaves)+len(ls)) > maxPartitions {
191 return partTooMany
192 }
193 leaves = append(leaves, ls...)
194 return partSuccess
195 }
196 if t.IsStruct() && !t.IsSIMD() {
197 for i := range t.NumFields() {
198 fld := t.Field(i)
199 if s := checkField(fld.Type, base+fld.Offset); s != partSuccess {
200 return nil, s
201 }
202 }
203 } else if t.IsArray() {
204
205 if t.NumElem() > maxPartitions {
206 return nil, partTooMany
207 }
208 for i := range t.NumElem() {
209 if s := checkField(t.Elem(), base+int64(i)*t.Elem().Size()); s != partSuccess {
210 return nil, s
211 }
212 }
213 } else if t.IsString() {
214
215
216
217
218 ptrType := f.Config.Types.BytePtr
219 lenType := types.Types[types.TINT]
220 if s := checkField(ptrType, base); s != partSuccess {
221 return nil, s
222 }
223 if s := checkField(lenType, base+ptrType.Size()); s != partSuccess {
224 return nil, s
225 }
226 } else if t.IsSlice() {
227
228 ptrType := types.NewPtr(t.Elem())
229 lenType := types.Types[types.TINT]
230 if s := checkField(ptrType, base); s != partSuccess {
231 return nil, s
232 }
233 if s := checkField(lenType, base+ptrType.Size()); s != partSuccess {
234 return nil, s
235 }
236 if s := checkField(lenType, base+ptrType.Size()+lenType.Size()); s != partSuccess {
237 return nil, s
238 }
239 } else if t.IsInterface() {
240
241
242
243 itabType := types.Types[types.TUINTPTR]
244 dataType := f.Config.Types.BytePtr
245 if s := checkField(itabType, base); s != partSuccess {
246 return nil, s
247 }
248 if s := checkField(dataType, base+itabType.Size()); s != partSuccess {
249 return nil, s
250 }
251 } else if t.IsComplex() {
252
253 elemType := types.Types[types.TFLOAT32]
254 if t.Size() == 16 {
255 elemType = types.Types[types.TFLOAT64]
256 }
257 if s := checkField(elemType, base); s != partSuccess {
258 return nil, s
259 }
260 if s := checkField(elemType, base+elemType.Size()); s != partSuccess {
261 return nil, s
262 }
263 } else {
264
265 if !t.IsSIMD() && t.Size() > f.Config.RegSize {
266
267
268
269
270 return nil, partLarge
271 }
272 if t.Size() == 0 {
273
274
275
276 f.Fatalf("zero-sized leaf field of type %v in decomposeAddr", t)
277 }
278 return []leafField{{base, t}}, partSuccess
279 }
280 return leaves, partSuccess
281 }
282
283
284 candidates := make(map[*ir.Name]*decomposeCandidate)
285
286
287 stringToNames := make(map[string][]*ir.Name)
288 localAddrsByName := make(map[*ir.Name][]*ssa.Value)
289 seenNames := make(map[*ir.Name]bool)
290 for _, v := range localAddrs {
291 n := v.Aux.(*ir.Name)
292 if !seenNames[n] {
293 stringToNames[n.Sym().Name] = append(stringToNames[n.Sym().Name], n)
294 seenNames[n] = true
295 }
296 localAddrsByName[n] = append(localAddrsByName[n], v)
297 }
298
299 namesOrdered := []*ir.Name{}
300 for n, las := range localAddrsByName {
301 namesOrdered = append(namesOrdered, n)
302 slices.SortFunc(las, func(a, b *ssa.Value) int { return int(a.ID - b.ID) })
303 }
304 slices.SortFunc(namesOrdered, func(a, b *ir.Name) int {
305 return int(localAddrsByName[a][0].ID - localAddrsByName[b][0].ID)
306 })
307 NameLoop:
308 for _, n := range namesOrdered {
309 if dg, ok := demographics[n]; !ok || !dg.lszmco {
310 st.Record("non qualifying variable", 1)
311 continue
312 }
313
314 if n.Class != ir.PAUTO {
315 st.Record("params", 1)
316 continue
317 }
318 t := n.Type()
319 splittable := (t.IsStruct() && !t.IsSIMD()) || t.IsArray() ||
320 t.IsString() || t.IsSlice() || t.IsInterface() || t.IsComplex()
321 if !splittable {
322
323
324
325
326 st.Record("non composite", 1)
327 continue
328 }
329 if n.NonMergeable() || n.OpenDeferSlot() {
330
331
332
333 st.Record("non mergeable or open defer slot", 1)
334 continue
335 }
336 leaves, status := getLeafFields(n.Type(), 0)
337 if status != partSuccess {
338 switch status {
339 case partTooMany:
340 st.Record("too many partitions", 1)
341 case partLarge:
342 st.Record("large leaf field", 1)
343 default:
344 f.Fatalf("unknown leaf status in decomposeAddr")
345 }
346 continue
347 }
348 if len(leaves) == 0 {
349 st.Record("no partition", 1)
350 continue
351 }
352 leavesByOff := make(map[int64]leafField, len(leaves))
353 for _, lf := range leaves {
354 if _, ok := leavesByOff[lf.off]; ok {
355
356
357 st.Record("duplicate leaf field offset", 1)
358 continue NameLoop
359 }
360 leavesByOff[lf.off] = lf
361 }
362
363 ok := true
364 for _, lf := range leaves {
365 if zeroValueForType(nil, lf.typ) == nil {
366 ok = false
367 break
368 }
369 }
370 if !ok {
371 continue
372 }
373
374 candidates[n] = &decomposeCandidate{n: n, leaves: leaves, localAddrs: localAddrsByName[n], leavesByOff: leavesByOff}
375 }
376
377 if len(candidates) == 0 {
378 return
379 }
380
381
382 var entryMem, entrySP *ssa.Value
383 for _, v := range f.Entry.Values {
384 if v.Op == ssaop.OpSP {
385 entrySP = v
386 }
387 if v.Op == ssaop.OpInitMem {
388 entryMem = v
389 }
390 if entryMem != nil && entrySP != nil {
391 break
392 }
393 }
394 if entryMem == nil || entrySP == nil {
395
396
397
398 f.Fatalf("entry mem or sp is not found but there are local variables")
399 }
400
401
402 isDerivedFrom := func(v *ssa.Value, n *ir.Name) bool {
403 for {
404 if v.Op == ssaop.OpLocalAddr && v.Aux == n {
405 return true
406 }
407 if v.Op != ssaop.OpOffPtr && v.Op != ssaop.OpCopy {
408 return false
409 }
410 v = v.Args[0]
411 }
412 }
413
414
415
416 localAddrBase := func(v *ssa.Value) *ssa.Value {
417 for {
418 switch v.Op {
419 case ssaop.OpLocalAddr:
420 return v
421 case ssaop.OpOffPtr, ssaop.OpCopy:
422 v = v.Args[0]
423 default:
424 return nil
425 }
426 }
427 }
428
429
430 findOffset := func(ptr *ssa.Value) int64 {
431 var offset int64
432 for {
433 switch ptr.Op {
434 case ssaop.OpLocalAddr:
435 return offset
436 case ssaop.OpOffPtr:
437 offset += ptr.AuxInt
438 ptr = ptr.Args[0]
439 case ssaop.OpCopy:
440 ptr = ptr.Args[0]
441 default:
442
443 f.Fatalf("not derived from local address: %v", ptr)
444 return -1
445 }
446 }
447 }
448
449 matchToLeaf := func(c *decomposeCandidate, v *ssa.Value, offset int64) (leafField, bool) {
450 var sz int64
451 if v.Op == ssaop.OpLoad {
452 sz = v.Type.Size()
453 } else if v.Op == ssaop.OpStore {
454 sz = ssa.AuxToType(v.Aux).Size()
455 } else {
456 return leafField{}, false
457 }
458 if lf, ok := c.leavesByOff[offset]; ok {
459
460 if lf.typ.Size() == sz {
461
462 return lf, true
463 }
464 }
465 return leafField{}, false
466 }
467
468
469
470
471 movedLeaves := func(c *decomposeCandidate, off, size int64) (leaves []leafField, ok bool) {
472 end := off + size
473 for _, lf := range c.leaves {
474 lend := lf.off + lf.typ.Size()
475 if lf.off >= end || lend <= off {
476 continue
477 }
478 if lf.off < off || lend > end {
479 return nil, false
480 }
481 leaves = append(leaves, leafField{lf.off - off, lf.typ})
482 }
483 return leaves, true
484 }
485
486
487
488
489
490
491
492 brokenDown := make(map[*ssa.Value]bool)
493
494
495
496
497
498
499
500
501 changed := false
502 var mutations []func()
503 NamesLoop:
504 for _, n := range namesOrdered {
505 usedLeaf := make(map[int64]struct{})
506 c, ok := candidates[n]
507 if !ok || c.unDecomposable {
508
509
510
511 continue
512 }
513 mutations = mutations[:0]
514
515
516
517
518
519 var partnerDisq []*decomposeCandidate
520
521
522 localBrokenDown := make(map[*ssa.Value]bool)
523 derived := []*ssa.Value{}
524 var collectDerived func(v *ssa.Value)
525 collectDerived = func(v *ssa.Value) {
526 derived = append(derived, v)
527 for _, use := range uses.of(v) {
528
529
530
531
532
533 if use.Op == ssaop.OpOffPtr || (use.Op == ssaop.OpCopy && use.Type.IsPtrShaped()) {
534 collectDerived(use)
535 }
536 }
537 }
538 for _, vAddr := range c.localAddrs {
539 collectDerived(vAddr)
540 }
541 slices.SortFunc(derived, func(a, b *ssa.Value) int { return int(a.ID - b.ID) })
542
543 for _, d := range derived {
544 for _, use := range uses.of(d) {
545 if brokenDown[use] || localBrokenDown[use] {
546 continue
547 }
548 switch use.Op {
549 case ssaop.OpOffPtr, ssaop.OpCopy:
550
551 case ssaop.OpLoad, ssaop.OpStore:
552 leaf, ok := matchToLeaf(c, use, findOffset(use.Args[0]))
553 if !ok {
554
555 if f.Pass.Debug > 1 {
556 f.Warnl(n.Pos(), "decomposeAddr: %v has a load or store not on leaf level", n)
557 }
558 st.Record("load or store not on leaf level", 1)
559 c.unDecomposable = true
560 continue NamesLoop
561 }
562 if use.Op == ssaop.OpLoad {
563
564 if _, ok := usedLeaf[leaf.off]; !ok {
565 usedLeaf[leaf.off] = struct{}{}
566 if int64(len(usedLeaf)) > maxActivePartitions {
567 st.Record("too many active partitions", 1)
568 c.unDecomposable = true
569 continue NamesLoop
570 }
571 }
572 }
573 case ssaop.OpZero:
574 off := findOffset(use.Args[0])
575 size := use.AuxInt
576 end := off + size
577
578 if off < 0 || end > n.Type().Size() {
579 st.Record("zero range out of bounds", 1)
580 c.unDecomposable = true
581 continue NamesLoop
582 }
583
584
585
586
587 for _, lf := range c.leaves {
588 lend := lf.off + lf.typ.Size()
589 if lf.off < end && lend > off {
590 if lf.off < off || lend > end {
591 st.Record("partially zeroed", 1)
592 c.unDecomposable = true
593 continue NamesLoop
594 }
595 }
596 }
597
598 memIn := use.MemoryArg()
599 curM := memIn
600 for _, lf := range c.leaves {
601 if lf.off >= off && lf.off+lf.typ.Size() <= end {
602 mutations = append(mutations, func() {
603 newPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), lf.off-off, use.Args[0])
604 curM = use.Block.NewValue3A(use.Pos, ssaop.OpStore, types.TypeMem, lf.typ, newPtr, zeroValueForType(f, lf.typ), curM)
605 })
606 }
607 }
608 mutations = append(mutations, func() {
609 use.Reset(ssaop.OpCopy)
610 use.Aux = nil
611 use.SetArgs1(curM)
612 })
613 localBrokenDown[use] = true
614 case ssaop.OpMove:
615 isDst := isDerivedFrom(use.Args[0], n)
616 isSrc := isDerivedFrom(use.Args[1], n)
617 if !isDst && !isSrc {
618 f.Fatalf("non of move's operands is derived from local address: %v", use)
619 }
620
621
622
623
624
625
626 nSide := use.Args[0]
627 oSide := use.Args[1]
628 if !isDst {
629 nSide = use.Args[1]
630 oSide = use.Args[0]
631 }
632 if base := localAddrBase(oSide); base != nil {
633 on := base.Aux.(*ir.Name)
634 if oc, ok := candidates[on]; ok && !oc.unDecomposable {
635
636
637
638
639
640
641
642 nLeaves, nOk := movedLeaves(c, findOffset(nSide), use.AuxInt)
643 oLeaves, oOk := movedLeaves(oc, findOffset(oSide), use.AuxInt)
644 compatible := nOk && oOk && len(nLeaves) == len(oLeaves)
645 for i := 0; compatible && i < len(nLeaves); i++ {
646 if nLeaves[i].off != oLeaves[i].off || nLeaves[i].typ.Size() != oLeaves[i].typ.Size() {
647 compatible = false
648 }
649 }
650 if !compatible {
651 if oc == c {
652 st.Record("self move with straddled leaves", 1)
653 c.unDecomposable = true
654 continue NamesLoop
655 }
656 partnerDisq = append(partnerDisq, oc)
657 }
658 }
659 }
660
661 moved := []int64{}
662 if isDst {
663 moved = append(moved, findOffset(use.Args[0]))
664 }
665 if isSrc {
666 moved = append(moved, findOffset(use.Args[1]))
667 }
668 if len(moved) == 2 {
669
670
671
672 if moved[1] < moved[0]+use.AuxInt && moved[0] < moved[1]+use.AuxInt {
673 st.Record("overlapping move", 1)
674 c.unDecomposable = true
675 continue NamesLoop
676 }
677 }
678 size := use.AuxInt
679
680
681 for _, m := range moved {
682 end := m + size
683 if m < 0 || end > n.Type().Size() {
684 st.Record("move range out of bounds", 1)
685 c.unDecomposable = true
686 continue NamesLoop
687 }
688 for _, lf := range c.leaves {
689 lend := lf.off + lf.typ.Size()
690 if lf.off < end && lend > m {
691 if lf.off < m || lend > end {
692 st.Record("partially moved", 1)
693 c.unDecomposable = true
694 continue NamesLoop
695 }
696 }
697 }
698 }
699
700
701
702
703
704
705
706
707
708
709
710 memIn := use.MemoryArg()
711 curM := memIn
712 for _, lf := range c.leaves {
713
714 offInMove := lf.off - moved[0]
715 if offInMove >= 0 && offInMove+lf.typ.Size() <= size {
716 mutations = append(mutations, func() {
717
718 newSrcPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), offInMove, use.Args[1])
719 newDstPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), offInMove, use.Args[0])
720 val := use.Block.NewValue2(use.Pos, ssaop.OpLoad, lf.typ, newSrcPtr, memIn)
721 curM = use.Block.NewValue3A(use.Pos, ssaop.OpStore, types.TypeMem, lf.typ, newDstPtr, val, curM)
722 })
723 }
724 }
725 mutations = append(mutations, func() {
726 use.Reset(ssaop.OpCopy)
727 use.Aux = nil
728 use.SetArgs1(curM)
729 })
730 localBrokenDown[use] = true
731 }
732 }
733 }
734 for _, m := range mutations {
735 m()
736 }
737 for _, oc := range partnerDisq {
738 if oc.unDecomposable {
739 continue
740 }
741 if f.Pass.Debug > 1 {
742 f.Warnl(oc.n.Pos(), "decomposeAddr: %v has leaves straddled by a move of %v; disqualified", oc.n, n)
743 }
744 st.Record("move partner with straddled leaves", 1)
745 oc.unDecomposable = true
746 }
747 for u := range localBrokenDown {
748 brokenDown[u] = true
749 }
750 if len(mutations) > 0 {
751 changed = true
752 }
753 }
754
755 if changed {
756
757
758
759
760
761 uses.free(f)
762 demographics, localAddrs, uses = variableDemographics(f)
763 if uses == nil {
764
765
766 return
767 }
768 }
769
770
771
772
773 for _, n := range namesOrdered {
774 c, ok := candidates[n]
775 if !ok || c.unDecomposable {
776 continue
777 }
778 if dg, ok := demographics[n]; !ok || !dg.lszmco {
779
780
781 f.Fatalf("zero and move breakdown disqualify %v from decomposeAddr", n)
782 }
783
784 type pAccess struct {
785 a *ssa.Value
786 off int64
787 }
788 var accesses []pAccess
789 var collectSimpleUses func(v *ssa.Value, offset int64)
790 collectSimpleUses = func(v *ssa.Value, offset int64) {
791 for _, use := range uses.of(v) {
792 switch use.Op {
793 case ssaop.OpOffPtr:
794 collectSimpleUses(use, offset+use.AuxInt)
795 case ssaop.OpLoad, ssaop.OpStore:
796 accesses = append(accesses, pAccess{use, offset})
797 case ssaop.OpCopy:
798 collectSimpleUses(use, offset)
799 default:
800 f.Fatalf("unhandled uses: %s", use.Op.String())
801 }
802 }
803 }
804 for _, vAddr := range c.localAddrs {
805 collectSimpleUses(vAddr, 0)
806 }
807 if len(accesses) == 0 {
808 st.Record("no accesses", 1)
809 continue
810 }
811
812 type partition struct {
813 offset int64
814 typ *types.Type
815 newAddr *ssa.Value
816 newName *ir.Name
817 }
818 partitions := make(map[int64]*partition)
819 partitionsValid := true
820 for _, a := range accesses {
821 if lf, ok := matchToLeaf(c, a.a, a.off); ok {
822 partitions[a.off] = &partition{offset: a.off, typ: lf.typ}
823 continue
824 }
825
826 partitionsValid = false
827 break
828 }
829 if !partitionsValid || len(partitions) == 0 {
830 f.Fatalf("not all accesses are on leaf level")
831 }
832
833 if f.Pass.Debug > 0 {
834 f.Warnl(n.Pos(), "promoted %v", n)
835 }
836 st.Record("promoted variable", 1)
837
838
839 var partOffsets []int64
840 for off := range partitions {
841 partOffsets = append(partOffsets, off)
842 }
843 slices.Sort(partOffsets)
844
845
846
847 nameIdx := -1
848 ns := stringToNames[n.Sym().Name]
849 if len(ns) > 1 {
850 for i, nn := range ns {
851 if nn == n {
852 nameIdx = i
853 break
854 }
855 }
856 }
857
858 for _, off := range partOffsets {
859 p := partitions[off]
860
861
862
863 var newSymName string
864 if nameIdx >= 0 {
865 newSymName = fmt.Sprintf("%s#%d.part.%d", n.Sym().Name, nameIdx, p.offset)
866 } else {
867 newSymName = fmt.Sprintf("%s.part.%d", n.Sym().Name, p.offset)
868 }
869 newSym := &types.Sym{Name: newSymName, Pkg: n.Sym().Pkg}
870
871
872 newName := n.Curfn.NewLocal(n.Pos(), newSym, p.typ)
873 newName.SetUsed(true)
874
875 newName.SetAutoTemp(n.AutoTemp())
876 p.newName = newName
877
878 p.newAddr = f.Entry.NewValue2A(n.Pos(), ssaop.OpLocalAddr, types.NewPtr(p.typ), newName, entrySP, entryMem)
879 }
880
881
882 for _, a := range accesses {
883 p := partitions[a.off]
884 a.a.SetArg(0, p.newAddr)
885 }
886
887
888
889
890 dg, ok := demographics[n]
891 if !ok {
892 f.Fatalf("decomposeAddr candidate variable unseen: %v", dg)
893 }
894 for _, v := range dg.varDefs {
895 curM := v.MemoryArg()
896 for _, off := range partOffsets {
897 p := partitions[off]
898 if p.newName.Type().HasPointers() || ssa.IsMergeCandidate(p.newName) {
899 curM = v.Block.NewValue1A(v.Pos, ssaop.OpVarDef, types.TypeMem, p.newName, curM)
900 }
901 }
902 v.Reset(ssaop.OpCopy)
903 v.Aux = nil
904 v.SetArgs1(curM)
905 }
906 changed = true
907 }
908
909 if changed {
910 deadcode(f)
911 }
912 }
913
View as plain text