Debian Codegraph @

go/ir/lift.go

raw
1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package ir
6
7 // This file defines the lifting pass which tries to "lift" Alloc
8 // cells (new/local variables) into SSA registers, replacing loads
9 // with the dominating stored value, eliminating loads and stores, and
10 // inserting φ- and σ-nodes as needed.
11
12 // Cited papers and resources:
13 //
14 // Ron Cytron et al. 1991. Efficiently computing SSA form...
15 // https://doi.acm.org/10.1145/115372.115320
16 //
17 // Cooper, Harvey, Kennedy. 2001. A Simple, Fast Dominance Algorithm.
18 // Software Practice and Experience 2001, 4:1-10.
19 // https://www.hipersoft.rice.edu/grads/publications/dom14.pdf
20 //
21 // Daniel Berlin, llvmdev mailing list, 2012.
22 // https://lists.cs.uiuc.edu/pipermail/llvmdev/2012-January/046638.html
23 // (Be sure to expand the whole thread.)
24 //
25 // C. Scott Ananian. 1997. The static single information form.
26 //
27 // Jeremy Singer. 2006. Static program analysis based on virtual register renaming.
28
29 // TODO(adonovan): opt: there are many optimizations worth evaluating, and
30 // the conventional wisdom for SSA construction is that a simple
31 // algorithm well engineered often beats those of better asymptotic
32 // complexity on all but the most egregious inputs.
33 //
34 // Danny Berlin suggests that the Cooper et al. algorithm for
35 // computing the dominance frontier is superior to Cytron et al.
36 // Furthermore he recommends that rather than computing the DF for the
37 // whole function then renaming all alloc cells, it may be cheaper to
38 // compute the DF for each alloc cell separately and throw it away.
39 //
40 // Consider exploiting liveness information to avoid creating dead
41 // φ-nodes which we then immediately remove.
42 //
43 // Also see many other "TODO: opt" suggestions in the code.
44
45 import (
46 "encoding/binary"
47 "fmt"
48 "os"
49 "slices"
50 )
51
52 // If true, show diagnostic information at each step of lifting.
53 // Very verbose.
54 const debugLifting = false
55
56 // domFrontier maps each block to the set of blocks in its dominance
57 // frontier. The outer slice is conceptually a map keyed by
58 // Block.Index. The inner slice is conceptually a set, possibly
59 // containing duplicates.
60 //
61 // TODO(adonovan): opt: measure impact of dups; consider a packed bit
62 // representation, e.g. big.Int, and bitwise parallel operations for
63 // the union step in the Children loop.
64 //
65 // domFrontier's methods mutate the slice's elements but not its
66 // length, so their receivers needn't be pointers.
67 type domFrontier BlockMap[[]*BasicBlock]
68
69 func (df domFrontier) add(u, v *BasicBlock) {
70 df[u.Index] = append(df[u.Index], v)
71 }
72
73 // build builds the dominance frontier df for the dominator tree of
74 // fn, using the algorithm found in A Simple, Fast Dominance
75 // Algorithm, Figure 5.
76 //
77 // TODO(adonovan): opt: consider Berlin approach, computing pruned SSA
78 // by pruning the entire IDF computation, rather than merely pruning
79 // the DF -> IDF step.
80 func (df domFrontier) build(fn *Function) {
81 for _, b := range fn.Blocks {
82 preds := b.Preds[0:len(b.Preds):len(b.Preds)]
83 if b == fn.Exit {
84 for i, v := range fn.fakeExits.values {
85 if v {
86 preds = append(preds, fn.Blocks[i])
87 }
88 }
89 }
90 if len(preds) >= 2 {
91 for _, p := range preds {
92 runner := p
93 for runner != b.dom.idom {
94 df.add(runner, b)
95 runner = runner.dom.idom
96 }
97 }
98 }
99 }
100 }
101
102 func buildDomFrontier(fn *Function) domFrontier {
103 df := make(domFrontier, len(fn.Blocks))
104 df.build(fn)
105 return df
106 }
107
108 type postDomFrontier BlockMap[[]*BasicBlock]
109
110 func (rdf postDomFrontier) add(u, v *BasicBlock) {
111 rdf[u.Index] = append(rdf[u.Index], v)
112 }
113
114 func (rdf postDomFrontier) build(fn *Function) {
115 for _, b := range fn.Blocks {
116 succs := b.Succs[0:len(b.Succs):len(b.Succs)]
117 if fn.fakeExits.Has(b) {
118 succs = append(succs, fn.Exit)
119 }
120 if len(succs) >= 2 {
121 for _, s := range succs {
122 runner := s
123 for runner != b.pdom.idom {
124 rdf.add(runner, b)
125 runner = runner.pdom.idom
126 }
127 }
128 }
129 }
130 }
131
132 func buildPostDomFrontier(fn *Function) postDomFrontier {
133 rdf := make(postDomFrontier, len(fn.Blocks))
134 rdf.build(fn)
135 return rdf
136 }
137
138 func removeInstr(refs []Instruction, instr Instruction) []Instruction {
139 return removeInstrsIf(refs, func(i Instruction) bool { return i == instr })
140 }
141
142 func removeInstrsIf(refs []Instruction, p func(Instruction) bool) []Instruction {
143 return slices.DeleteFunc(refs, p)
144 }
145
146 func clearInstrs(instrs []Instruction) {
147 for i := range instrs {
148 instrs[i] = nil
149 }
150 }
151
152 func numberNodesPerBlock(f *Function) {
153 for _, b := range f.Blocks {
154 var base ID
155 for _, instr := range b.Instrs {
156 if instr == nil {
157 continue
158 }
159 instr.setID(base)
160 base++
161 }
162 }
163 }
164
165 // lift replaces local and new Allocs accessed only with
166 // load/store by IR registers, inserting φ- and σ-nodes where necessary.
167 // The result is a program in pruned SSI form.
168 //
169 // Preconditions:
170 // - fn has no dead blocks (blockopt has run).
171 // - Def/use info (Operands and Referrers) is up-to-date.
172 // - The dominator tree is up-to-date.
173 func lift(fn *Function) bool {
174 // TODO(adonovan): opt: lots of little optimizations may be
175 // worthwhile here, especially if they cause us to avoid
176 // buildDomFrontier. For example:
177 //
178 // - Alloc never loaded? Eliminate.
179 // - Alloc never stored? Replace all loads with a zero constant.
180 // - Alloc stored once? Replace loads with dominating store;
181 // don't forget that an Alloc is itself an effective store
182 // of zero.
183 // - Alloc used only within a single block?
184 // Use degenerate algorithm avoiding φ-nodes.
185 // - Consider synergy with scalar replacement of aggregates (SRA).
186 // e.g. *(&x.f) where x is an Alloc.
187 // Perhaps we'd get better results if we generated this as x.f
188 // i.e. Field(x, .f) instead of Load(FieldIndex(x, .f)).
189 // Unclear.
190 //
191 // But we will start with the simplest correct code.
192 var df domFrontier
193 var rdf postDomFrontier
194 var closure *closure
195 var newPhis BlockMap[[]newPhi]
196 var newSigmas BlockMap[[]newSigma]
197
198 // During this pass we will replace some BasicBlock.Instrs
199 // (allocs, loads and stores) with nil, keeping a count in
200 // BasicBlock.gaps. At the end we will reset Instrs to the
201 // concatenation of all non-dead newPhis and non-nil Instrs
202 // for the block, reusing the original array if space permits.
203
204 // While we're here, we also eliminate 'rundefers'
205 // instructions and ssa:deferstack() in functions that contain no
206 // 'defer' instructions. Eliminate ssa:deferstack() if it does not
207 // escape.
208 usesDefer := false
209 deferstackAlloc, deferstackCall := deferstackPreamble(fn)
210 eliminateDeferStack := deferstackAlloc != nil && !deferstackAlloc.Heap
211
212 // Determine which allocs we can lift and number them densely.
213 // The renaming phase uses this numbering for compact maps.
214 numAllocs := 0
215
216 instructions := make(BlockMap[liftInstructions], len(fn.Blocks))
217 for i := range instructions {
218 instructions[i].insertInstructions = map[Instruction][]Instruction{}
219 }
220
221 // Number nodes, for liftable
222 numberNodesPerBlock(fn)
223
224 for _, b := range fn.Blocks {
225 b.gaps = 0
226 b.rundefers = 0
227
228 for _, instr := range b.Instrs {
229 switch instr := instr.(type) {
230 case *Alloc:
231 if !liftable(instr, instructions) {
232 instr.index = -1
233 continue
234 }
235
236 if numAllocs == 0 {
237 df = buildDomFrontier(fn)
238 rdf = buildPostDomFrontier(fn)
239 if len(fn.Blocks) > 2 {
240 closure = transitiveClosure(fn)
241 }
242 newPhis = make(BlockMap[[]newPhi], len(fn.Blocks))
243 newSigmas = make(BlockMap[[]newSigma], len(fn.Blocks))
244
245 if debugLifting {
246 title := false
247 for i, blocks := range df {
248 if blocks != nil {
249 if !title {
250 fmt.Fprintf(os.Stderr, "Dominance frontier of %s:\n", fn)
251 title = true
252 }
253 fmt.Fprintf(os.Stderr, "\t%s: %s\n", fn.Blocks[i], blocks)
254 }
255 }
256 }
257 }
258 instr.index = numAllocs
259 numAllocs++
260 case *Defer:
261 usesDefer = true
262 if eliminateDeferStack {
263 // Clear _DeferStack and remove references to loads
264 if instr._DeferStack != nil {
265 if refs := instr._DeferStack.Referrers(); refs != nil {
266 *refs = removeInstr(*refs, instr)
267 }
268 instr._DeferStack = nil
269 }
270 }
271 case *RunDefers:
272 b.rundefers++
273 }
274 }
275 }
276
277 if numAllocs > 0 {
278 for _, b := range fn.Blocks {
279 work := instructions[b.Index]
280 for _, rename := range work.renameAllocs {
281 for _, instr_ := range b.Instrs[rename.startingAt:] {
282 replace(instr_, rename.from, rename.to)
283 }
284 }
285 }
286
287 for _, b := range fn.Blocks {
288 work := instructions[b.Index]
289 if len(work.insertInstructions) != 0 {
290 newInstrs := make([]Instruction, 0, len(fn.Blocks)+len(work.insertInstructions)*3)
291 for _, instr := range b.Instrs {
292 if add, ok := work.insertInstructions[instr]; ok {
293 newInstrs = append(newInstrs, add...)
294 }
295 newInstrs = append(newInstrs, instr)
296 }
297 b.Instrs = newInstrs
298 }
299 }
300
301 // TODO(dh): remove inserted allocs that end up unused after lifting.
302
303 for _, b := range fn.Blocks {
304 for _, instr := range b.Instrs {
305 if instr, ok := instr.(*Alloc); ok && instr.index >= 0 {
306 liftAlloc(closure, df, rdf, instr, newPhis, newSigmas)
307 }
308 }
309 }
310
311 // renaming maps an alloc (keyed by index) to its replacement
312 // value. Initially the renaming contains nil, signifying the
313 // zero constant of the appropriate type; we construct the
314 // Const lazily at most once on each path through the domtree.
315 // TODO(adonovan): opt: cache per-function not per subtree.
316 renaming := make([]Value, numAllocs)
317
318 // Renaming.
319 rename(fn.Blocks[0], renaming, newPhis, newSigmas)
320
321 simplifyPhisAndSigmas(newPhis, newSigmas)
322
323 // Eliminate dead φ- and σ-nodes.
324 markLiveNodes(fn.Blocks, newPhis, newSigmas)
325
326 // Eliminate ssa:deferstack() call.
327 if eliminateDeferStack {
328 b := deferstackCall.block
329 for i, instr := range b.Instrs {
330 if instr == deferstackCall {
331 b.Instrs[i] = nil
332 b.gaps++
333 break
334 }
335 }
336 }
337 }
338
339 // Prepend remaining live φ-nodes to each block and possibly kill rundefers.
340 for _, b := range fn.Blocks {
341 var head []Instruction
342 if numAllocs > 0 {
343 nps := newPhis[b.Index]
344 head = make([]Instruction, 0, len(nps))
345 for _, pred := range b.Preds {
346 nss := newSigmas[pred.Index]
347 idx := pred.succIndex(b)
348 for _, newSigma := range nss {
349 if sigma := newSigma.sigmas[idx]; sigma != nil && sigma.live {
350 head = append(head, sigma)
351
352 // we didn't populate referrers before, as most
353 // sigma nodes will be killed
354 if refs := sigma.X.Referrers(); refs != nil {
355 *refs = append(*refs, sigma)
356 }
357 } else if sigma != nil {
358 sigma.block = nil
359 }
360 }
361 }
362 for _, np := range nps {
363 if np.phi.live {
364 head = append(head, np.phi)
365 } else {
366 for _, edge := range np.phi.Edges {
367 if refs := edge.Referrers(); refs != nil {
368 *refs = removeInstr(*refs, np.phi)
369 }
370 }
371 np.phi.block = nil
372 }
373 }
374 }
375
376 rundefersToKill := b.rundefers
377 if usesDefer {
378 rundefersToKill = 0
379 }
380
381 j := len(head)
382 if j+b.gaps+rundefersToKill == 0 {
383 continue // fast path: no new phis or gaps
384 }
385
386 // We could do straight copies instead of element-wise copies
387 // when both b.gaps and rundefersToKill are zero. However,
388 // that seems to only be the case ~1% of the time, which
389 // doesn't seem worth the extra branch.
390
391 // Remove dead instructions, add phis and sigmas
392 ns := len(b.Instrs) + j - b.gaps - rundefersToKill
393 if ns <= cap(b.Instrs) {
394 // b.Instrs has enough capacity to store all instructions
395
396 // OPT(dh): check cap vs the actually required space; if
397 // there is a big enough difference, it may be worth
398 // allocating a new slice, to avoid pinning memory.
399 dst := b.Instrs[:cap(b.Instrs)]
400 i := len(dst) - 1
401 for n := len(b.Instrs) - 1; n >= 0; n-- {
402 instr := dst[n]
403 if instr == nil {
404 continue
405 }
406 if !usesDefer {
407 if _, ok := instr.(*RunDefers); ok {
408 continue
409 }
410 }
411 dst[i] = instr
412 i--
413 }
414 off := i + 1 - len(head)
415 // aid GC
416 clearInstrs(dst[:off])
417 dst = dst[off:]
418 copy(dst, head)
419 b.Instrs = dst
420 } else {
421 // not enough space, so allocate a new slice and copy
422 // over.
423 dst := make([]Instruction, ns)
424 copy(dst, head)
425
426 for _, instr := range b.Instrs {
427 if instr == nil {
428 continue
429 }
430 if !usesDefer {
431 if _, ok := instr.(*RunDefers); ok {
432 continue
433 }
434 }
435 dst[j] = instr
436 j++
437 }
438 b.Instrs = dst
439 }
440 }
441
442 // Remove any fn.Locals that were lifted.
443 j := 0
444 for _, l := range fn.Locals {
445 if l.index < 0 {
446 fn.Locals[j] = l
447 j++
448 }
449 }
450 // Nil out fn.Locals[j:] to aid GC.
451 for i := j; i < len(fn.Locals); i++ {
452 fn.Locals[i] = nil
453 }
454 fn.Locals = fn.Locals[:j]
455
456 return numAllocs > 0
457 }
458
459 func hasDirectReferrer(instr Instruction) bool {
460 for _, instr := range *instr.Referrers() {
461 switch instr.(type) {
462 case *Phi, *Sigma:
463 // ignore
464 default:
465 return true
466 }
467 }
468 return false
469 }
470
471 func markLiveNodes(blocks []*BasicBlock, newPhis BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {
472 // Phis and sigmas may become dead due to optimization passes. We may also insert more nodes than strictly
473 // necessary, e.g. sigma nodes for constants, which will never be used.
474
475 // Phi and sigma nodes are considered live if a non-phi, non-sigma
476 // node uses them. Once we find a node that is live, we mark all
477 // of its operands as used, too.
478 for _, npList := range newPhis {
479 for _, np := range npList {
480 phi := np.phi
481 if !phi.live && hasDirectReferrer(phi) {
482 markLivePhi(phi)
483 }
484 }
485 }
486 for _, npList := range newSigmas {
487 for _, np := range npList {
488 for _, sigma := range np.sigmas {
489 if sigma != nil && !sigma.live && hasDirectReferrer(sigma) {
490 markLiveSigma(sigma)
491 }
492 }
493 }
494 }
495 // Existing φ-nodes due to && and || operators
496 // are all considered live (see Go issue 19622).
497 for _, b := range blocks {
498 for _, phi := range b.phis() {
499 markLivePhi(phi.(*Phi))
500 }
501 }
502 }
503
504 func markLivePhi(phi *Phi) {
505 phi.live = true
506 for _, rand := range phi.Edges {
507 switch rand := rand.(type) {
508 case *Phi:
509 if !rand.live {
510 markLivePhi(rand)
511 }
512 case *Sigma:
513 if !rand.live {
514 markLiveSigma(rand)
515 }
516 }
517 }
518 }
519
520 func markLiveSigma(sigma *Sigma) {
521 sigma.live = true
522 switch rand := sigma.X.(type) {
523 case *Phi:
524 if !rand.live {
525 markLivePhi(rand)
526 }
527 case *Sigma:
528 if !rand.live {
529 markLiveSigma(rand)
530 }
531 }
532 }
533
534 // simplifyPhisAndSigmas removes duplicate phi and sigma nodes,
535 // and replaces trivial phis with non-phi alternatives. Phi
536 // nodes where all edges are identical, or consist of only the phi
537 // itself and one other value, may be replaced with the value.
538 func simplifyPhisAndSigmas(newPhis BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {
539 // temporary numbering of values used in phis so that we can build map keys
540 var id ID
541 for _, npList := range newPhis {
542 for _, np := range npList {
543 for _, edge := range np.phi.Edges {
544 edge.setID(id)
545 id++
546 }
547 }
548 }
549 // find all phis that are trivial and can be replaced with a
550 // non-phi value. run until we reach a fixpoint, because replacing
551 // a phi may make other phis trivial.
552 for changed := true; changed; {
553 changed = false
554 for _, npList := range newPhis {
555 for _, np := range npList {
556 if np.phi.live {
557 // we're reusing 'live' to mean 'dead' in the context of simplifyPhisAndSigmas
558 continue
559 }
560 if r, ok := isUselessPhi(np.phi); ok {
561 // useless phi, replace its uses with the
562 // replacement value. the dead phi pass will clean
563 // up the phi afterwards.
564 replaceAll(np.phi, r)
565 np.phi.live = true
566 changed = true
567 }
568 }
569 }
570
571 // Replace duplicate sigma nodes with a single node. These nodes exist when multiple allocs get replaced with the
572 // same dominating store.
573 for _, sigmaList := range newSigmas {
574 primarySigmas := map[struct {
575 succ int
576 v Value
577 }]*Sigma{}
578 for _, sigmas := range sigmaList {
579 for succ, sigma := range sigmas.sigmas {
580 if sigma == nil {
581 continue
582 }
583 if sigma.live {
584 // we're reusing 'live' to mean 'dead' in the context of simplifyPhisAndSigmas
585 continue
586 }
587 key := struct {
588 succ int
589 v Value
590 }{succ, sigma.X}
591 if alt, ok := primarySigmas[key]; ok {
592 replaceAll(sigma, alt)
593 sigma.live = true
594 changed = true
595 } else {
596 primarySigmas[key] = sigma
597 }
598 }
599 }
600 }
601
602 // Replace duplicate phi nodes with a single node. As far as we know, these duplicate nodes only ever exist
603 // because of the previous sigma deduplication.
604 keyb := make([]byte, 0, 4*8)
605 for _, npList := range newPhis {
606 primaryPhis := map[string]*Phi{}
607 for _, np := range npList {
608 if np.phi.live {
609 continue
610 }
611 if n := len(np.phi.Edges) * 8; cap(keyb) >= n {
612 keyb = keyb[:n]
613 } else {
614 keyb = make([]byte, n, n*2)
615 }
616 for i, e := range np.phi.Edges {
617 binary.LittleEndian.PutUint64(keyb[i*8:i*8+8], uint64(e.ID()))
618 }
619 if alt, ok := primaryPhis[string(keyb)]; ok {
620 replaceAll(np.phi, alt)
621 np.phi.live = true
622 changed = true
623 } else {
624 primaryPhis[string(keyb)] = np.phi
625 }
626 }
627 }
628
629 }
630
631 for _, npList := range newPhis {
632 for _, np := range npList {
633 np.phi.live = false
634 for _, edge := range np.phi.Edges {
635 edge.setID(0)
636 }
637 }
638 }
639
640 for _, sigmaList := range newSigmas {
641 for _, sigmas := range sigmaList {
642 for _, sigma := range sigmas.sigmas {
643 if sigma != nil {
644 sigma.live = false
645 }
646 }
647 }
648 }
649 }
650
651 type BlockSet struct {
652 idx int
653 values []bool
654 count int
655 }
656
657 func NewBlockSet(size int) *BlockSet {
658 return &BlockSet{values: make([]bool, size)}
659 }
660
661 func (s *BlockSet) Set(s2 *BlockSet) {
662 copy(s.values, s2.values)
663 s.count = 0
664 for _, v := range s.values {
665 if v {
666 s.count++
667 }
668 }
669 }
670
671 func (s *BlockSet) Num() int {
672 return s.count
673 }
674
675 func (s *BlockSet) Has(b *BasicBlock) bool {
676 if b.Index >= len(s.values) {
677 return false
678 }
679 return s.values[b.Index]
680 }
681
682 // add adds b to the set and returns true if the set changed.
683 func (s *BlockSet) Add(b *BasicBlock) bool {
684 if s.values[b.Index] {
685 return false
686 }
687 s.count++
688 s.values[b.Index] = true
689 s.idx = b.Index
690
691 return true
692 }
693
694 func (s *BlockSet) Clear() {
695 for j := range s.values {
696 s.values[j] = false
697 }
698 s.count = 0
699 }
700
701 // take removes an arbitrary element from a set s and
702 // returns its index, or returns -1 if empty.
703 func (s *BlockSet) Take() int {
704 // [i, end]
705 for i := s.idx; i < len(s.values); i++ {
706 if s.values[i] {
707 s.values[i] = false
708 s.idx = i
709 s.count--
710 return i
711 }
712 }
713
714 // [start, i)
715 for i := 0; i < s.idx; i++ {
716 if s.values[i] {
717 s.values[i] = false
718 s.idx = i
719 s.count--
720 return i
721 }
722 }
723
724 return -1
725 }
726
727 type closure struct {
728 span []uint32
729 reachables BlockMap[interval]
730 }
731
732 type interval uint32
733
734 const (
735 flagMask = 1 << 31
736 numBits = 20
737 lengthBits = 32 - numBits - 1
738 lengthMask = (1<<lengthBits - 1) << numBits
739 numMask = 1<<numBits - 1
740 )
741
742 func (c closure) has(s, v *BasicBlock) bool {
743 idx := uint32(v.Index)
744 if idx == 1 || s.Dominates(v) {
745 return true
746 }
747 r := c.reachable(s.Index)
748 for i := 0; i < len(r); i++ {
749 inv := r[i]
750 var start, end uint32
751 if inv&flagMask == 0 {
752 // small interval
753 start = uint32(inv & numMask)
754 end = start + uint32(inv&lengthMask)>>numBits
755 } else {
756 // large interval
757 i++
758 start = uint32(inv & numMask)
759 end = uint32(r[i])
760 }
761 if idx >= start && idx <= end {
762 return true
763 }
764 }
765 return false
766 }
767
768 func (c closure) reachable(id int) []interval {
769 return c.reachables[c.span[id]:c.span[id+1]]
770 }
771
772 func (c closure) walk(current *BasicBlock, b *BasicBlock, visited []bool) {
773 // TODO(dh): the 'current' argument seems to be unused
774 // TODO(dh): there's no reason for this to be a method
775 visited[b.Index] = true
776 for _, succ := range b.Succs {
777 if visited[succ.Index] {
778 continue
779 }
780 visited[succ.Index] = true
781 c.walk(current, succ, visited)
782 }
783 }
784
785 func transitiveClosure(fn *Function) *closure {
786 reachable := make(BlockMap[bool], len(fn.Blocks))
787 c := &closure{}
788 c.span = make([]uint32, len(fn.Blocks)+1)
789
790 addInterval := func(start, end uint32) {
791 if l := end - start; l <= 1<<lengthBits-1 {
792 n := interval(l<<numBits | start)
793 c.reachables = append(c.reachables, n)
794 } else {
795 n1 := interval(1<<31 | start)
796 n2 := interval(end)
797 c.reachables = append(c.reachables, n1, n2)
798 }
799 }
800
801 for i, b := range fn.Blocks[1:] {
802 for i := range reachable {
803 reachable[i] = false
804 }
805
806 c.walk(b, b, reachable)
807 start := ^uint32(0)
808 for id, isReachable := range reachable {
809 if !isReachable {
810 if start != ^uint32(0) {
811 end := uint32(id) - 1
812 addInterval(start, end)
813 start = ^uint32(0)
814 }
815 continue
816 } else if start == ^uint32(0) {
817 start = uint32(id)
818 }
819 }
820 if start != ^uint32(0) {
821 addInterval(start, uint32(len(reachable))-1)
822 }
823
824 c.span[i+2] = uint32(len(c.reachables))
825 }
826
827 return c
828 }
829
830 // newPhi is a pair of a newly introduced φ-node and the lifted Alloc
831 // it replaces.
832 type newPhi struct {
833 phi *Phi
834 alloc *Alloc
835 }
836
837 type newSigma struct {
838 alloc *Alloc
839 sigmas []*Sigma
840 }
841
842 type liftInstructions struct {
843 insertInstructions map[Instruction][]Instruction
844 renameAllocs []struct {
845 from *Alloc
846 to *Alloc
847 startingAt int
848 }
849 }
850
851 // liftable determines if alloc can be lifted, and records instructions to split partially liftable allocs.
852 //
853 // In the trivial case, all uses of the alloc can be lifted. This is the case when it is only used for storing into and
854 // loading from. In that case, no instructions are recorded.
855 //
856 // In the more complex case, the alloc is used for storing into and loading from, but it is also used as a value, for
857 // example because it gets passed to a function, e.g. fn(&x). In this case, uses of the alloc fall into one of two
858 // categories: those that can be lifted and those that can't. A boundary forms between these two categories in the
859 // function's control flow: Once an unliftable use is encountered, the alloc is no longer liftable for the remainder of
860 // the basic block the use is in, nor in any blocks reachable from it.
861 //
862 // We record instructions that split the alloc into two allocs: one that is used in liftable uses, and one that is used
863 // in unliftable uses. Whenever we encounter a boundary between liftable and unliftable uses or blocks, we emit a pair
864 // of Load and Store that copy the value from the liftable alloc into the unliftable alloc. Taking these instructions
865 // into account, the normal lifting machinery will completely lift the liftable alloc, store the correct lifted values
866 // into the unliftable alloc, and will not at all lift the unliftable alloc.
867 //
868 // In Go syntax, the transformation looks somewhat like this:
869 //
870 // func foo() {
871 // x := 32
872 // if cond {
873 // println(x)
874 // escape(&x)
875 // println(x)
876 // } else {
877 // println(x)
878 // }
879 // println(x)
880 // }
881 //
882 // transforms into
883 //
884 // func fooSplitAlloc() {
885 // x := 32
886 // var x_ int
887 // if cond {
888 // println(x)
889 // x_ = x
890 // escape(&x_)
891 // println(x_)
892 // } else {
893 // println(x)
894 // x_ = x
895 // }
896 // println(x_)
897 // }
898 func liftable(alloc *Alloc, instructions BlockMap[liftInstructions]) bool {
899 fn := alloc.block.parent
900
901 // Don't lift result values in functions that defer
902 // calls that may recover from panic.
903 if fn.hasDefer {
904 if slices.Contains(fn.results, alloc) {
905 return false
906 }
907 }
908
909 type blockDesc struct {
910 // is the block (partially) unliftable, because it contains unliftable instructions or is reachable by an unliftable block
911 isUnliftable bool
912 hasLiftableLoad bool
913 hasLiftableOther bool
914 // we need to emit stores in predecessors because the unliftable use is in a phi
915 storeInPreds bool
916
917 lastLiftable int
918 firstUnliftable int
919 }
920 blocks := make(BlockMap[blockDesc], len(fn.Blocks))
921 for _, b := range fn.Blocks {
922 blocks[b.Index].lastLiftable = -1
923 blocks[b.Index].firstUnliftable = len(b.Instrs) + 1
924 }
925
926 // Look at all uses of the alloc and deduce which blocks have liftable or unliftable instructions.
927 for _, instr := range alloc.referrers {
928 // Find the first unliftable use
929
930 desc := &blocks[instr.Block().Index]
931 hasUnliftable := false
932 inHead := false
933 switch instr := instr.(type) {
934 case *Store:
935 if instr.Val == alloc {
936 hasUnliftable = true
937 }
938 case *Load:
939 case *DebugRef:
940 case *Phi, *Sigma:
941 inHead = true
942 hasUnliftable = true
943 default:
944 hasUnliftable = true
945 }
946
947 if hasUnliftable {
948 desc.isUnliftable = true
949 if int(instr.ID()) < desc.firstUnliftable {
950 desc.firstUnliftable = int(instr.ID())
951 }
952 if inHead {
953 desc.storeInPreds = true
954 desc.firstUnliftable = 0
955 }
956 }
957 }
958
959 for _, instr := range alloc.referrers {
960 // Find the last liftable use, taking the previously calculated firstUnliftable into consideration
961
962 desc := &blocks[instr.Block().Index]
963 if int(instr.ID()) >= desc.firstUnliftable {
964 continue
965 }
966 hasLiftable := false
967 switch instr := instr.(type) {
968 case *Store:
969 if instr.Val != alloc {
970 desc.hasLiftableOther = true
971 hasLiftable = true
972 }
973 case *Load:
974 desc.hasLiftableLoad = true
975 hasLiftable = true
976 case *DebugRef:
977 desc.hasLiftableOther = true
978 }
979 if hasLiftable {
980 if int(instr.ID()) > desc.lastLiftable {
981 desc.lastLiftable = int(instr.ID())
982 }
983 }
984 }
985
986 for i := range blocks {
987 // Update firstUnliftable to be one after lastLiftable. We do this to include the unliftable's preceding
988 // DebugRefs in the renaming.
989 if blocks[i].lastLiftable == -1 && !blocks[i].storeInPreds {
990 // There are no liftable instructions (for this alloc) in this block. Set firstUnliftable to the
991 // first non-head instruction to avoid inserting the store before phi instructions, which would
992 // fail validation.
993 first := -1
994 instrLoop:
995 for i, instr := range fn.Blocks[i].Instrs {
996 switch instr.(type) {
997 case *Phi, *Sigma:
998 default:
999 first = i
1000 break instrLoop
1001 }
1002 }
1003 blocks[i].firstUnliftable = first
1004 } else {
1005 blocks[i].firstUnliftable = blocks[i].lastLiftable + 1
1006 }
1007 }
1008
1009 // If a block is reachable by a (partially) unliftable block, then the entirety of the block is unliftable. In that
1010 // case, stores have to be inserted in the predecessors.
1011 //
1012 // TODO(dh): this isn't always necessary. If the block is reachable by itself, i.e. part of a loop, then if the
1013 // Alloc instruction is itself part of that loop, then there is a subset of instructions in the loop that can be
1014 // lifted. For example:
1015 //
1016 // for {
1017 // x := 42
1018 // println(x)
1019 // escape(&x)
1020 // }
1021 //
1022 // The x that escapes in one iteration of the loop isn't the same x that we read from on the next iteration.
1023 seen := make(BlockMap[bool], len(fn.Blocks))
1024 var dfs func(b *BasicBlock)
1025 dfs = func(b *BasicBlock) {
1026 if seen[b.Index] {
1027 return
1028 }
1029 seen[b.Index] = true
1030 desc := &blocks[b.Index]
1031 desc.hasLiftableLoad = false
1032 desc.hasLiftableOther = false
1033 desc.isUnliftable = true
1034 desc.firstUnliftable = 0
1035 desc.storeInPreds = true
1036 for _, succ := range b.Succs {
1037 dfs(succ)
1038 }
1039 }
1040 for _, b := range fn.Blocks {
1041 if blocks[b.Index].isUnliftable {
1042 for _, succ := range b.Succs {
1043 dfs(succ)
1044 }
1045 }
1046 }
1047
1048 hasLiftableLoad := false
1049 hasLiftableOther := false
1050 hasUnliftable := false
1051 for _, b := range fn.Blocks {
1052 desc := blocks[b.Index]
1053 hasLiftableLoad = hasLiftableLoad || desc.hasLiftableLoad
1054 hasLiftableOther = hasLiftableOther || desc.hasLiftableOther
1055 if desc.isUnliftable {
1056 hasUnliftable = true
1057 }
1058 }
1059 if !hasLiftableLoad && !hasLiftableOther {
1060 // There are no liftable uses
1061 return false
1062 } else if !hasUnliftable {
1063 // The alloc is entirely liftable without splitting
1064 return true
1065 } else if !hasLiftableLoad {
1066 // The alloc is not entirely liftable, and the only liftable uses are stores. While some of those stores could
1067 // get lifted away, it would also lead to an infinite loop when lifting to a fixpoint, because the newly created
1068 // allocs also get stored into repeatable and that's their only liftable uses.
1069 return false
1070 }
1071
1072 // We need to insert stores for the new alloc. If a (partially) unliftable block has no unliftable
1073 // predecessors and the use isn't in a phi node, then the store can be inserted right before the unliftable use.
1074 // Otherwise, stores have to be inserted at the end of all liftable predecessors.
1075
1076 newAlloc := &Alloc{Heap: true}
1077 newAlloc.setBlock(alloc.block)
1078 newAlloc.setType(alloc.typ)
1079 newAlloc.setSource(alloc.source)
1080 newAlloc.index = -1
1081 newAlloc.comment = "split alloc"
1082
1083 {
1084 work := instructions[alloc.block.Index]
1085 work.insertInstructions[alloc] = append(work.insertInstructions[alloc], newAlloc)
1086 }
1087
1088 predHasStore := make(BlockMap[bool], len(fn.Blocks))
1089 for _, b := range fn.Blocks {
1090 desc := &blocks[b.Index]
1091 bWork := &instructions[b.Index]
1092
1093 if desc.isUnliftable {
1094 bWork.renameAllocs = append(bWork.renameAllocs, struct {
1095 from *Alloc
1096 to *Alloc
1097 startingAt int
1098 }{
1099 alloc, newAlloc, int(desc.firstUnliftable),
1100 })
1101 }
1102
1103 if !desc.isUnliftable {
1104 continue
1105 }
1106
1107 propagate := func(in *BasicBlock, before Instruction) {
1108 load := &Load{
1109 X: alloc,
1110 }
1111 store := &Store{
1112 Addr: newAlloc,
1113 Val: load,
1114 }
1115 load.setType(deref(alloc.typ))
1116 load.setBlock(in)
1117 load.comment = "split alloc"
1118 store.setBlock(in)
1119 updateOperandReferrers(load)
1120 updateOperandReferrers(store)
1121 store.comment = "split alloc"
1122
1123 entry := &instructions[in.Index]
1124 entry.insertInstructions[before] = append(entry.insertInstructions[before], load, store)
1125 }
1126
1127 if desc.storeInPreds {
1128 // emit stores at the end of liftable preds
1129 for _, pred := range b.Preds {
1130 if blocks[pred.Index].isUnliftable {
1131 continue
1132 }
1133
1134 if !alloc.block.Dominates(pred) {
1135 // Consider this cfg:
1136 //
1137 // 1
1138 // /|
1139 // / |
1140 // ↙ ↓
1141 // 2--→3
1142 //
1143 // with an Alloc in block 2. It doesn't make sense to insert a store in block 1 for the jump to
1144 // block 3, because 1 can never see the Alloc in the first place.
1145 //
1146 // Ignoring phi nodes, an Alloc always dominates all of its uses, and phi nodes don't matter here,
1147 // because for the incoming edges that do matter, we do emit the stores.
1148
1149 continue
1150 }
1151
1152 if predHasStore[pred.Index] {
1153 // Don't generate redundant propagations. Not only is it unnecessary, it can lead to infinite loops
1154 // when trying to lift to a fix point, because redundant stores are liftable.
1155 continue
1156 }
1157
1158 predHasStore[pred.Index] = true
1159
1160 before := pred.Instrs[len(pred.Instrs)-1]
1161 propagate(pred, before)
1162 }
1163 } else {
1164 // emit store before the first unliftable use
1165 before := b.Instrs[desc.firstUnliftable]
1166 propagate(b, before)
1167 }
1168 }
1169
1170 return true
1171 }
1172
1173 // liftAlloc lifts alloc into registers and populates newPhis and newSigmas with all the φ- and σ-nodes it may require.
1174 func liftAlloc(closure *closure, df domFrontier, rdf postDomFrontier, alloc *Alloc, newPhis BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {
1175 fn := alloc.Parent()
1176
1177 defblocks := fn.blockset(0)
1178 useblocks := fn.blockset(1)
1179 Aphi := fn.blockset(2)
1180 Asigma := fn.blockset(3)
1181 W := fn.blockset(4)
1182
1183 // Compute defblocks, the set of blocks containing a
1184 // definition of the alloc cell.
1185 for _, instr := range *alloc.Referrers() {
1186 switch instr := instr.(type) {
1187 case *Store:
1188 defblocks.Add(instr.Block())
1189 case *Load:
1190 useblocks.Add(instr.Block())
1191 for _, ref := range *instr.Referrers() {
1192 useblocks.Add(ref.Block())
1193 }
1194 }
1195 }
1196 // The Alloc itself counts as a (zero) definition of the cell.
1197 defblocks.Add(alloc.Block())
1198
1199 if debugLifting {
1200 fmt.Fprintln(os.Stderr, "\tlifting ", alloc, alloc.Name())
1201 }
1202
1203 // Φ-insertion.
1204 //
1205 // What follows is the body of the main loop of the insert-φ
1206 // function described by Cytron et al, but instead of using
1207 // counter tricks, we just reset the 'hasAlready' and 'work'
1208 // sets each iteration. These are bitmaps so it's pretty cheap.
1209
1210 // Initialize W and work to defblocks.
1211
1212 for change := true; change; {
1213 change = false
1214 {
1215 // Traverse iterated dominance frontier, inserting φ-nodes.
1216 W.Set(defblocks)
1217
1218 for i := W.Take(); i != -1; i = W.Take() {
1219 n := fn.Blocks[i]
1220 for _, y := range df[n.Index] {
1221 if Aphi.Add(y) {
1222 if len(*alloc.Referrers()) == 0 {
1223 continue
1224 }
1225 live := false
1226 if closure == nil {
1227 live = true
1228 } else {
1229 for _, ref := range *alloc.Referrers() {
1230 if _, ok := ref.(*Load); ok {
1231 if closure.has(y, ref.Block()) {
1232 live = true
1233 break
1234 }
1235 }
1236 }
1237 }
1238 if !live {
1239 continue
1240 }
1241
1242 // Create φ-node.
1243 // It will be prepended to v.Instrs later, if needed.
1244 if len(y.Preds) == 0 {
1245 // The exit block may be unreachable if the function doesn't
1246 // return, e.g. due to an infinite loop. In that case we
1247 // should not replace loads in the exit block with ϕ node that
1248 // have no edges. Such loads exist when the function has named
1249 // return parameters, as the exit block loads them to turn
1250 // them into a Return instruction. By not replacing the loads
1251 // with ϕ nodes, they will later be replaced by zero
1252 // constants. This is arguably more correct, and more
1253 // importantly, it doesn't break code that assumes that phis
1254 // have at least one edge.
1255 //
1256 // For one instance of breakage see
1257 // https://staticcheck.dev/issues/1533
1258 continue
1259 }
1260 phi := &Phi{
1261 Edges: make([]Value, len(y.Preds)),
1262 }
1263 phi.comment = alloc.comment
1264 phi.source = alloc.source
1265 phi.setType(deref(alloc.Type()))
1266 phi.block = y
1267 if debugLifting {
1268 fmt.Fprintf(os.Stderr, "\tplace %s = %s at block %s\n", phi.Name(), phi, y)
1269 }
1270 newPhis[y.Index] = append(newPhis[y.Index], newPhi{phi, alloc})
1271
1272 for _, p := range y.Preds {
1273 useblocks.Add(p)
1274 }
1275 change = true
1276 if defblocks.Add(y) {
1277 W.Add(y)
1278 }
1279 }
1280 }
1281 }
1282 }
1283
1284 {
1285 W.Set(useblocks)
1286 for i := W.Take(); i != -1; i = W.Take() {
1287 n := fn.Blocks[i]
1288 for _, y := range rdf[n.Index] {
1289 if Asigma.Add(y) {
1290 sigmas := make([]*Sigma, 0, len(y.Succs))
1291 anyLive := false
1292 for _, succ := range y.Succs {
1293 live := false
1294 for _, ref := range *alloc.Referrers() {
1295 if closure == nil || closure.has(succ, ref.Block()) {
1296 live = true
1297 anyLive = true
1298 break
1299 }
1300 }
1301 if live {
1302 sigma := &Sigma{
1303 From: y,
1304 X: alloc,
1305 }
1306 sigma.comment = alloc.comment
1307 sigma.source = alloc.source
1308 sigma.setType(deref(alloc.Type()))
1309 sigma.block = succ
1310 sigmas = append(sigmas, sigma)
1311 } else {
1312 sigmas = append(sigmas, nil)
1313 }
1314 }
1315
1316 if anyLive {
1317 newSigmas[y.Index] = append(newSigmas[y.Index], newSigma{alloc, sigmas})
1318 for _, s := range y.Succs {
1319 defblocks.Add(s)
1320 }
1321 change = true
1322 if useblocks.Add(y) {
1323 W.Add(y)
1324 }
1325 }
1326 }
1327 }
1328 }
1329 }
1330 }
1331 }
1332
1333 // replaceAll replaces all intraprocedural uses of x with y,
1334 // updating x.Referrers and y.Referrers.
1335 // Precondition: x.Referrers() != nil, i.e. x must be local to some function.
1336 func replaceAll(x, y Value) {
1337 var rands []*Value
1338 pxrefs := x.Referrers()
1339 pyrefs := y.Referrers()
1340 for _, instr := range *pxrefs {
1341 switch instr := instr.(type) {
1342 case *CompositeValue:
1343 // Special case CompositeValue because it might have very large lists of operands
1344 //
1345 // OPT(dh): this loop is still expensive for large composite values
1346 for i, rand := range instr.Values {
1347 if rand == x {
1348 instr.Values[i] = y
1349 }
1350 }
1351 default:
1352 rands = instr.Operands(rands[:0]) // recycle storage
1353 for _, rand := range rands {
1354 if *rand != nil {
1355 if *rand == x {
1356 *rand = y
1357 }
1358 }
1359 }
1360 }
1361 if pyrefs != nil {
1362 *pyrefs = append(*pyrefs, instr) // dups ok
1363 }
1364 }
1365 *pxrefs = nil // x is now unreferenced
1366 }
1367
1368 func replace(instr Instruction, x, y Value) {
1369 args := instr.Operands(nil)
1370 matched := false
1371 for _, arg := range args {
1372 if *arg == x {
1373 *arg = y
1374 matched = true
1375 }
1376 }
1377 if matched {
1378 yrefs := y.Referrers()
1379 if yrefs != nil {
1380 *yrefs = append(*yrefs, instr)
1381 }
1382
1383 xrefs := x.Referrers()
1384 if xrefs != nil {
1385 *xrefs = removeInstr(*xrefs, instr)
1386 }
1387 }
1388 }
1389
1390 // renamed returns the value to which alloc is being renamed,
1391 // constructing it lazily if it's the implicit zero initialization.
1392 func renamed(fn *Function, renaming []Value, alloc *Alloc) Value {
1393 v := renaming[alloc.index]
1394 if v == nil {
1395 v = emitConst(fn, zeroConst(deref(alloc.Type()), alloc.source))
1396 renaming[alloc.index] = v
1397 }
1398 return v
1399 }
1400
1401 func copyValue(v Value, why Instruction, info CopyInfo) *Copy {
1402 c := &Copy{
1403 X: v,
1404 Why: why,
1405 Info: info,
1406 }
1407 if refs := v.Referrers(); refs != nil {
1408 *refs = append(*refs, c)
1409 }
1410 c.setType(v.Type())
1411 c.setSource(v.Source())
1412 return c
1413 }
1414
1415 func splitOnNewInformation(u *BasicBlock, renaming *StackMap) {
1416 renaming.Push()
1417 defer renaming.Pop()
1418
1419 rename := func(v Value, why Instruction, info CopyInfo, i int) {
1420 c := copyValue(v, why, info)
1421 c.setBlock(u)
1422 renaming.Set(v, c)
1423 u.Instrs = append(u.Instrs, nil)
1424 copy(u.Instrs[i+2:], u.Instrs[i+1:])
1425 u.Instrs[i+1] = c
1426 }
1427
1428 replacement := func(v Value) (Value, bool) {
1429 r, ok := renaming.Get(v)
1430 if !ok {
1431 return nil, false
1432 }
1433 for {
1434 rr, ok := renaming.Get(r)
1435 if !ok {
1436 // Store replacement in the map so that future calls to replacement(v) don't have to go through the
1437 // iterative process again.
1438 renaming.Set(v, r)
1439 return r, true
1440 }
1441 r = rr
1442 }
1443 }
1444
1445 var hasInfo func(v Value, info CopyInfo) bool
1446 hasInfo = func(v Value, info CopyInfo) bool {
1447 switch v := v.(type) {
1448 case *Copy:
1449 return (v.Info&info) == info || hasInfo(v.X, info)
1450 case *FieldAddr, *IndexAddr, *TypeAssert, *MakeChan, *MakeMap, *MakeSlice, *Alloc:
1451 return info == CopyInfoNotNil
1452 case Member, *Builtin:
1453 return info == CopyInfoNotNil
1454 case *Sigma:
1455 return hasInfo(v.X, info)
1456 default:
1457 return false
1458 }
1459 }
1460
1461 var args []*Value
1462 for i := 0; i < len(u.Instrs); i++ {
1463 instr := u.Instrs[i]
1464 if instr == nil {
1465 continue
1466 }
1467 args = instr.Operands(args[:0])
1468 for _, arg := range args {
1469 if *arg == nil {
1470 continue
1471 }
1472 if r, ok := replacement(*arg); ok {
1473 *arg = r
1474 replace(instr, *arg, r)
1475 }
1476 }
1477
1478 // TODO write some bits on why we copy values instead of encoding the actual control flow and panics
1479
1480 switch instr := instr.(type) {
1481 case *IndexAddr:
1482 // Note that we rename instr.Index and instr.X even if they're already copies, because unique combinations
1483 // of X and Index may lead to unique information.
1484
1485 // OPT we should rename both variables at once and avoid one memmove
1486 rename(instr.Index, instr, CopyInfoNotNegative, i)
1487 rename(instr.X, instr, CopyInfoNotNil, i)
1488 i += 2 // skip over instructions we just inserted
1489 case *FieldAddr:
1490 if !hasInfo(instr.X, CopyInfoNotNil) {
1491 rename(instr.X, instr, CopyInfoNotNil, i)
1492 i++
1493 }
1494 case *TypeAssert:
1495 // If we've already type asserted instr.X without comma-ok before, then it can only contain a single type,
1496 // and successive type assertions, no matter the type, don't tell us anything new.
1497 if !hasInfo(instr.X, CopyInfoNotNil|CopyInfoSingleConcreteType) {
1498 rename(instr.X, instr, CopyInfoNotNil|CopyInfoSingleConcreteType, i)
1499 i++ // skip over instruction we just inserted
1500 }
1501 case *Load:
1502 if !hasInfo(instr.X, CopyInfoNotNil) {
1503 rename(instr.X, instr, CopyInfoNotNil, i)
1504 i++
1505 }
1506 case *Store:
1507 if !hasInfo(instr.Addr, CopyInfoNotNil) {
1508 rename(instr.Addr, instr, CopyInfoNotNil, i)
1509 i++
1510 }
1511 case *MapUpdate:
1512 if !hasInfo(instr.Map, CopyInfoNotNil) {
1513 rename(instr.Map, instr, CopyInfoNotNil, i)
1514 i++
1515 }
1516 case CallInstruction:
1517 off := 0
1518 if !instr.Common().IsInvoke() && !hasInfo(instr.Common().Value, CopyInfoNotNil) {
1519 rename(instr.Common().Value, instr, CopyInfoNotNil, i)
1520 off++
1521 }
1522 if f, ok := instr.Common().Value.(*Builtin); ok {
1523 switch f.name {
1524 case "close":
1525 arg := instr.Common().Args[0]
1526 if !hasInfo(arg, CopyInfoNotNil|CopyInfoClosed) {
1527 rename(arg, instr, CopyInfoNotNil|CopyInfoClosed, i)
1528 off++
1529 }
1530 }
1531 }
1532 i += off
1533 case *SliceToArrayPointer:
1534 // A slice to array pointer conversion tells us the minimum length of the slice
1535 rename(instr.X, instr, CopyInfoUnspecified, i)
1536 i++
1537 case *SliceToArray:
1538 // A slice to array conversion tells us the minimum length of the slice
1539 rename(instr.X, instr, CopyInfoUnspecified, i)
1540 i++
1541 case *Slice:
1542 // Slicing tells us about some of the bounds
1543 off := 0
1544 if instr.Low == nil && instr.High == nil && instr.Max == nil {
1545 // If all indices are unspecified, then we can only learn something about instr.X if it might've been
1546 // nil.
1547 if !hasInfo(instr.X, CopyInfoNotNil) {
1548 rename(instr.X, instr, CopyInfoUnspecified, i)
1549 off++
1550 }
1551 } else {
1552 rename(instr.X, instr, CopyInfoUnspecified, i)
1553 off++
1554 }
1555 // We copy the indices even if we already know they are not negative, because we can associate numeric
1556 // ranges with them.
1557 if instr.Low != nil {
1558 rename(instr.Low, instr, CopyInfoNotNegative, i)
1559 off++
1560 }
1561 if instr.High != nil {
1562 rename(instr.High, instr, CopyInfoNotNegative, i)
1563 off++
1564 }
1565 if instr.Max != nil {
1566 rename(instr.Max, instr, CopyInfoNotNegative, i)
1567 off++
1568 }
1569 i += off
1570 case *StringLookup:
1571 rename(instr.X, instr, CopyInfoUnspecified, i)
1572 rename(instr.Index, instr, CopyInfoNotNegative, i)
1573 i += 2
1574 case *Recv:
1575 if !hasInfo(instr.Chan, CopyInfoNotNil) {
1576 // Receiving from a nil channel never completes
1577 rename(instr.Chan, instr, CopyInfoNotNil, i)
1578 i++
1579 }
1580 case *Send:
1581 if !hasInfo(instr.Chan, CopyInfoNotNil) {
1582 // Sending to a nil channel never completes. Sending to a closed channel panics, but whether a channel
1583 // is closed isn't local to this function, so we didn't learn anything.
1584 rename(instr.Chan, instr, CopyInfoNotNil, i)
1585 i++
1586 }
1587 }
1588 }
1589
1590 for _, v := range u.dom.children {
1591 splitOnNewInformation(v, renaming)
1592 }
1593 }
1594
1595 // rename implements the Cytron et al-based SSI renaming algorithm, a
1596 // preorder traversal of the dominator tree replacing all loads of
1597 // Alloc cells with the value stored to that cell by the dominating
1598 // store instruction.
1599 //
1600 // renaming is a map from *Alloc (keyed by index number) to its
1601 // dominating stored value; newPhis[x] is the set of new φ-nodes to be
1602 // prepended to block x.
1603 func rename(u *BasicBlock, renaming []Value, newPhis BlockMap[[]newPhi], newSigmas BlockMap[[]newSigma]) {
1604 // Each φ-node becomes the new name for its associated Alloc.
1605 for _, np := range newPhis[u.Index] {
1606 phi := np.phi
1607 alloc := np.alloc
1608 renaming[alloc.index] = phi
1609 }
1610
1611 // Rename loads and stores of allocs.
1612 for i, instr := range u.Instrs {
1613 switch instr := instr.(type) {
1614 case *Alloc:
1615 if instr.index >= 0 { // store of zero to Alloc cell
1616 // Replace dominated loads by the zero value.
1617 renaming[instr.index] = nil
1618 if debugLifting {
1619 fmt.Fprintf(os.Stderr, "\tkill alloc %s\n", instr)
1620 }
1621 // Delete the Alloc.
1622 u.Instrs[i] = nil
1623 u.gaps++
1624 }
1625
1626 case *Store:
1627 if alloc, ok := instr.Addr.(*Alloc); ok && alloc.index >= 0 { // store to Alloc cell
1628 // Replace dominated loads by the stored value.
1629 renaming[alloc.index] = instr.Val
1630 if debugLifting {
1631 fmt.Fprintf(os.Stderr, "\tkill store %s; new value: %s\n",
1632 instr, instr.Val.Name())
1633 }
1634 if refs := instr.Addr.Referrers(); refs != nil {
1635 *refs = removeInstr(*refs, instr)
1636 }
1637 if refs := instr.Val.Referrers(); refs != nil {
1638 *refs = removeInstr(*refs, instr)
1639 }
1640 // Delete the Store.
1641 u.Instrs[i] = nil
1642 u.gaps++
1643 }
1644
1645 case *Load:
1646 if alloc, ok := instr.X.(*Alloc); ok && alloc.index >= 0 { // load of Alloc cell
1647 // In theory, we wouldn't be able to replace loads directly, because a loaded value could be used in
1648 // different branches, in which case it should be replaced with different sigma nodes. But we can't
1649 // simply defer replacement, either, because then later stores might incorrectly affect this load.
1650 //
1651 // To avoid doing renaming on _all_ values (instead of just loads and stores like we're doing), we make
1652 // sure during code generation that each load is only used in one block. For example, in constant switch
1653 // statements, where the tag is only evaluated once, we store it in a temporary and load it for each
1654 // comparison, so that we have individual loads to replace.
1655 //
1656 // Because we only rename stores and loads, the end result will not contain sigma nodes for all
1657 // constants. Some constants may be used directly, e.g. in comparisons such as 'x == 5'. We may still
1658 // end up inserting dead sigma nodes in branches, but these will never get used in renaming and will be
1659 // cleaned up when we remove dead phis and sigmas.
1660 newval := renamed(u.Parent(), renaming, alloc)
1661 if debugLifting {
1662 fmt.Fprintf(os.Stderr, "\tupdate load %s = %s with %s\n",
1663 instr.Name(), instr, newval)
1664 }
1665 replaceAll(instr, newval)
1666 u.Instrs[i] = nil
1667 u.gaps++
1668 }
1669
1670 case *DebugRef:
1671 if x, ok := instr.X.(*Alloc); ok && x.index >= 0 {
1672 if instr.IsAddr {
1673 instr.X = renamed(u.Parent(), renaming, x)
1674 instr.IsAddr = false
1675
1676 // Add DebugRef to instr.X's referrers.
1677 if refs := instr.X.Referrers(); refs != nil {
1678 *refs = append(*refs, instr)
1679 }
1680 } else {
1681 // A source expression denotes the address
1682 // of an Alloc that was optimized away.
1683 instr.X = nil
1684
1685 // Delete the DebugRef.
1686 u.Instrs[i] = nil
1687 u.gaps++
1688 }
1689 }
1690 }
1691 }
1692
1693 // update all outgoing sigma nodes with the dominating store
1694 for _, sigmas := range newSigmas[u.Index] {
1695 for _, sigma := range sigmas.sigmas {
1696 if sigma == nil {
1697 continue
1698 }
1699 sigma.X = renamed(u.Parent(), renaming, sigmas.alloc)
1700 }
1701 }
1702
1703 // For each φ-node in a CFG successor, rename the edge.
1704 for succi, v := range u.Succs {
1705 phis := newPhis[v.Index]
1706 if len(phis) == 0 {
1707 continue
1708 }
1709 i := v.predIndex(u)
1710 for _, np := range phis {
1711 phi := np.phi
1712 alloc := np.alloc
1713 // if there's a sigma node, use it, else use the dominating value
1714 var newval Value
1715 for _, sigmas := range newSigmas[u.Index] {
1716 if sigmas.alloc == alloc && sigmas.sigmas[succi] != nil {
1717 newval = sigmas.sigmas[succi]
1718 break
1719 }
1720 }
1721 if newval == nil {
1722 newval = renamed(u.Parent(), renaming, alloc)
1723 }
1724 if debugLifting {
1725 fmt.Fprintf(os.Stderr, "\tsetphi %s edge %s -> %s (#%d) (alloc=%s) := %s\n",
1726 phi.Name(), u, v, i, alloc.Name(), newval.Name())
1727 }
1728 phi.Edges[i] = newval
1729 if prefs := newval.Referrers(); prefs != nil {
1730 *prefs = append(*prefs, phi)
1731 }
1732 }
1733 }
1734
1735 // Continue depth-first recursion over domtree, pushing a
1736 // fresh copy of the renaming map for each subtree.
1737 r := make([]Value, len(renaming))
1738 for _, v := range u.dom.children {
1739 copy(r, renaming)
1740
1741 // on entry to a block, the incoming sigma nodes become the new values for their alloc
1742 if idx := u.succIndex(v); idx != -1 {
1743 for _, sigma := range newSigmas[u.Index] {
1744 if sigma.sigmas[idx] != nil {
1745 r[sigma.alloc.index] = sigma.sigmas[idx]
1746 }
1747 }
1748 }
1749 rename(v, r, newPhis, newSigmas)
1750 }
1751
1752 }
1753
1754 func simplifyConstantCompositeValues(fn *Function) bool {
1755 changed := false
1756
1757 for _, b := range fn.Blocks {
1758 n := 0
1759 for _, instr := range b.Instrs {
1760 replaced := false
1761
1762 if cv, ok := instr.(*CompositeValue); ok {
1763 ac := &AggregateConst{}
1764 ac.typ = cv.typ
1765 replaced = true
1766 for _, v := range cv.Values {
1767 if c, ok := v.(Constant); ok {
1768 ac.Values = append(ac.Values, c)
1769 } else {
1770 replaced = false
1771 break
1772 }
1773 }
1774 if replaced {
1775 replaceAll(cv, emitConst(fn, ac))
1776 killInstruction(cv)
1777 }
1778
1779 }
1780
1781 if replaced {
1782 changed = true
1783 } else {
1784 b.Instrs[n] = instr
1785 n++
1786 }
1787 }
1788
1789 clearInstrs(b.Instrs[n:])
1790 b.Instrs = b.Instrs[:n]
1791 }
1792
1793 return changed
1794 }
1795
1796 func updateOperandReferrers(instr Instruction) {
1797 for _, op := range instr.Operands(nil) {
1798 refs := (*op).Referrers()
1799 if refs != nil {
1800 *refs = append(*refs, instr)
1801 }
1802 }
1803 }
1804
1805 // deferstackPreamble returns the *Alloc and ssa:deferstack() call for fn.deferstack.
1806 func deferstackPreamble(fn *Function) (*Alloc, *Call) {
1807 if alloc, _ := fn.vars[fn.deferstack].(*Alloc); alloc != nil {
1808 for _, ref := range *alloc.Referrers() {
1809 if ref, _ := ref.(*Store); ref != nil && ref.Addr == alloc {
1810 if call, _ := ref.Val.(*Call); call != nil {
1811 return alloc, call
1812 }
1813 }
1814 }
1815 }
1816 return nil, nil
1817 }