1 // Copyright 2015 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.
5 // Register allocation.
7 // We use a version of a linear scan register allocator. We treat the
8 // whole function as a single long basic block and run through
9 // it using a greedy register allocator. Then all merge edges
10 // (those targeting a block with len(Preds)>1) are processed to
11 // shuffle data into the place that the target of the edge expects.
13 // The greedy allocator moves values into registers just before they
14 // are used, spills registers only when necessary, and spills the
15 // value whose next use is farthest in the future.
17 // The register allocator requires that a block is not scheduled until
18 // at least one of its predecessors have been scheduled. The most recent
19 // such predecessor provides the starting register state for a block.
21 // It also requires that there are no critical edges (critical =
22 // comes from a block with >1 successor and goes to a block with >1
23 // predecessor). This makes it easy to add fixup code on merge edges -
24 // the source of a merge edge has only one successor, so we can add
25 // fixup code to the end of that block.
29 // For every value, we generate a spill immediately after the value itself.
32 // While AX still holds x, any uses of x will use that value. When AX is needed
33 // for another value, we simply reuse AX. Spill code has already been generated
34 // so there is no code generated at "spill" time. When x is referenced
35 // subsequently, we issue a load to restore x to a register using x2 as
37 // x3 = Restore x2 : CX
38 // x3 can then be used wherever x is referenced again.
39 // If the spill (x2) is never used, it will be removed at the end of regalloc.
41 // Phi values are special, as always. We define two kinds of phis, those
42 // where the merge happens in a register (a "register" phi) and those where
43 // the merge happens in a stack location (a "stack" phi).
45 // A register phi must have the phi and all of its inputs allocated to the
46 // same register. Register phis are spilled similarly to regular ops:
47 // b1: y = ... : AX b2: z = ... : AX
49 // b3: x = phi(y, z) : AX
52 // A stack phi must have the phi and all of its inputs allocated to the same
53 // stack location. Stack phis start out life already spilled - each phi
54 // input must be a store (using StoreReg) at the end of the corresponding
56 // b1: y = ... : AX b2: z = ... : BX
57 // y2 = StoreReg y z2 = StoreReg z
59 // b3: x = phi(y2, z2)
60 // The stack allocator knows that StoreReg args of stack-allocated phis
61 // must be allocated to the same stack slot as the phi that uses them.
62 // x is now a spilled value and a restore must appear before its first use.
66 // Use an affinity graph to mark two values which should use the
67 // same register. This affinity graph will be used to prefer certain
68 // registers for allocation. This affinity helps eliminate moves that
69 // are required for phi implementations and helps generate allocations
70 // for 2-register architectures.
72 // Note: regalloc generates a not-quite-SSA output. If we have:
76 // ... AX gets reused for something else ...
77 // if ... goto b3 else b4
79 // b3: x3 = LoadReg x2 : BX b4: x4 = LoadReg x2 : CX
80 // ... use x3 ... ... use x4 ...
84 // If b3 is the primary predecessor of b2, then we use x3 in b2 and
85 // add a x4:CX->BX copy at the end of b4.
86 // But the definition of x3 doesn't dominate b2. We should really
87 // insert a dummy phi at the start of b2 (x5=phi(x3,x4):BX) to keep
88 // SSA form. For now, we ignore this problem as remaining in strict
89 // SSA form isn't needed after regalloc. We'll just leave the use
90 // of x3 not dominated by the definition of x3, and the CX->BX copy
91 // will have no use (so don't run deadcode after regalloc!).
92 // TODO: maybe we should introduce these extra phis?
94 // Additional not-quite-SSA output occurs when spills are sunk out
95 // of loops to the targets of exit edges from the loop. Before sinking,
96 // there is one spill site (one StoreReg) targeting stack slot X, after
97 // sinking there may be multiple spill sites targeting stack slot X,
98 // with no phi functions at any join points reachable by the multiple
99 // spill sites. In addition, uses of the spill from copies of the original
100 // will not name the copy in their reference; instead they will name
101 // the original, though both will have the same spill location. The
102 // first sunk spill will be the original, but moved, to an exit block,
103 // thus ensuring that there is a definition somewhere corresponding to
104 // the original spill's uses.
122 // distance is a measure of how far into the future values are used.
123 // distance is measured in units of instructions.
127 unlikelyDistance = 100
130 // regalloc performs register allocation on f. It sets f.RegAlloc
131 // to the resulting allocation.
132 func regalloc(f *Func) {
140 const noRegister register = 255
144 func (m regMask) String() string {
146 for r := register(0); m != 0; r++ {
150 m &^= regMask(1) << r
154 s += fmt.Sprintf("r%d", r)
159 // countRegs returns the number of set bits in the register mask.
160 func countRegs(r regMask) int {
169 // pickReg picks an arbitrary register from the register mask.
170 func pickReg(r regMask) register {
171 // pick the lowest one
173 panic("can't pick a register from an empty set")
175 for i := register(0); ; i++ {
184 dist int32 // distance from start of the block to a use of a value
185 pos src.XPos // source position of the use
186 next *use // linked list of uses of a value in nondecreasing dist order
189 type valState struct {
190 regs regMask // the set of registers holding a Value (usually just one)
191 uses *use // list of uses in this block
192 spill *Value // spilled copy of the Value
194 spillUsedShuffle bool // true if used in shuffling, after ordinary uses
195 needReg bool // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags()
196 rematerializeable bool // cached value of v.rematerializeable()
199 type regState struct {
200 v *Value // Original (preregalloc) Value stored in this register.
201 c *Value // A Value equal to v which is currently in a register. Might be v or a copy of it.
202 // If a register is unused, v==c==nil
205 type regAllocState struct {
215 // for each block, its primary predecessor.
216 // A predecessor of b is primary if it is the closest
217 // predecessor that appears before b in the layout order.
218 // We record the index in the Preds list where the primary predecessor sits.
221 // live values at the end of each block. live[b.ID] is a list of value IDs
222 // which are live at the end of b, together with a count of how many instructions
223 // forward to the next use.
225 // desired register assignments at the end of each block.
226 // Note that this is a static map computed before allocation occurs. Dynamic
227 // register desires (from partially completed allocations) will trump
229 desired []desiredState
231 // current state of each (preregalloc) Value
234 // For each Value, map from its value ID back to the
235 // preregalloc Value it was derived from.
238 // current state of each register
241 // registers that contain values which can't be kicked out
244 // mask of registers currently in use
247 // mask of registers used in the current instruction
250 // current block we're working on
253 // cache of use records
256 // endRegs[blockid] is the register state at the end of each block.
257 // encoded as a set of endReg records.
260 // startRegs[blockid] is the register state at the start of merge blocks.
261 // saved state does not include the state of phi ops in the block.
262 startRegs [][]startReg
264 // spillLive[blockid] is the set of live spills at the end of each block
267 // a set of copies we generated to move things around, and
268 // whether it is used in shuffle. Unused copies will be deleted.
269 copies map[*Value]bool
274 type spillToSink struct {
275 spill *Value // Spill instruction to move (a StoreReg)
276 dests int32 // Bitmask indicating exit blocks from loop in which spill/val is defined. 1<<i set means val is live into loop.exitBlocks[i]
279 func (sts *spillToSink) spilledValue() *Value {
280 return sts.spill.Args[0]
285 v *Value // pre-regalloc value held in this register (TODO: can we use ID here?)
286 c *Value // cached version of the value
289 type startReg struct {
291 vid ID // pre-regalloc value needed in this register
292 pos src.XPos // source position of use of this register
295 // freeReg frees up register r. Any current user of r is kicked out.
296 func (s *regAllocState) freeReg(r register) {
299 s.f.Fatalf("tried to free an already free register %d\n", r)
303 if s.f.pass.debug > regDebug {
304 fmt.Printf("freeReg %s (dump %s/%s)\n", s.registers[r].Name(), v, s.regs[r].c)
306 s.regs[r] = regState{}
307 s.values[v.ID].regs &^= regMask(1) << r
308 s.used &^= regMask(1) << r
311 // freeRegs frees up all registers listed in m.
312 func (s *regAllocState) freeRegs(m regMask) {
314 s.freeReg(pickReg(m & s.used))
318 // setOrig records that c's original value is the same as
319 // v's original value.
320 func (s *regAllocState) setOrig(c *Value, v *Value) {
321 for int(c.ID) >= len(s.orig) {
322 s.orig = append(s.orig, nil)
324 if s.orig[c.ID] != nil {
325 s.f.Fatalf("orig value set twice %s %s", c, v)
327 s.orig[c.ID] = s.orig[v.ID]
330 // assignReg assigns register r to hold c, a copy of v.
332 func (s *regAllocState) assignReg(r register, v *Value, c *Value) {
333 if s.f.pass.debug > regDebug {
334 fmt.Printf("assignReg %s %s/%s\n", s.registers[r].Name(), v, c)
336 if s.regs[r].v != nil {
337 s.f.Fatalf("tried to assign register %d to %s/%s but it is already used by %s", r, v, c, s.regs[r].v)
341 s.regs[r] = regState{v, c}
342 s.values[v.ID].regs |= regMask(1) << r
343 s.used |= regMask(1) << r
344 s.f.setHome(c, &s.registers[r])
347 // allocReg chooses a register from the set of registers in mask.
348 // If there is no unused register, a Value will be kicked out of
349 // a register to make room.
350 func (s *regAllocState) allocReg(mask regMask, v *Value) register {
351 mask &= s.allocatable
354 s.f.Fatalf("no register available for %s", v)
357 // Pick an unused register if one is available.
358 if mask&^s.used != 0 {
359 return pickReg(mask &^ s.used)
362 // Pick a value to spill. Spill the value with the
363 // farthest-in-the-future use.
364 // TODO: Prefer registers with already spilled Values?
365 // TODO: Modify preference using affinity graph.
366 // TODO: if a single value is in multiple registers, spill one of them
367 // before spilling a value in just a single register.
369 // Find a register to spill. We spill the register containing the value
370 // whose next use is as far in the future as possible.
371 // https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
374 for t := register(0); t < s.numRegs; t++ {
379 if n := s.values[v.ID].uses.dist; n > maxuse {
380 // v's next use is farther in the future than any value
381 // we've seen so far. A new best spill candidate.
387 s.f.Fatalf("couldn't find register to spill")
390 // Try to move it around before kicking out, if there is a free register.
391 // We generate a Copy and record it. It will be deleted if never used.
393 m := s.compatRegs(v2.Type) &^ s.used &^ s.tmpused &^ (regMask(1) << r)
394 if m != 0 && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 {
396 c := s.curBlock.NewValue1(v2.Pos, OpCopy, v2.Type, s.regs[r].c)
398 if s.f.pass.debug > regDebug {
399 fmt.Printf("copy %s to %s : %s\n", v2, c, s.registers[r2].Name())
402 s.assignReg(r2, v2, c)
408 // allocValToReg allocates v to a register selected from regMask and
409 // returns the register copy of v. Any previous user is kicked out and spilled
410 // (if necessary). Load code is added at the current pc. If nospill is set the
411 // allocated register is marked nospill so the assignment cannot be
412 // undone until the caller allows it by clearing nospill. Returns a
413 // *Value which is either v or a copy of v allocated to the chosen register.
414 func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, pos src.XPos) *Value {
415 vi := &s.values[v.ID]
417 // Check if v is already in a requested register.
418 if mask&vi.regs != 0 {
419 r := pickReg(mask & vi.regs)
420 if s.regs[r].v != v || s.regs[r].c == nil {
421 panic("bad register state")
424 s.nospill |= regMask(1) << r
429 // Allocate a register.
430 r := s.allocReg(mask, v)
432 // Allocate v to the new register.
435 // Copy from a register that v is already in.
436 r2 := pickReg(vi.regs)
437 if s.regs[r2].v != v {
438 panic("bad register state")
440 c = s.curBlock.NewValue1(pos, OpCopy, v.Type, s.regs[r2].c)
441 } else if v.rematerializeable() {
442 // Rematerialize instead of loading from the spill location.
443 c = v.copyInto(s.curBlock)
446 // Load v from its spill location.
447 case vi.spill != nil:
448 if s.f.pass.debug > logSpills {
449 s.f.Config.Warnl(vi.spill.Pos, "load spill for %v from %v", v, vi.spill)
451 c = s.curBlock.NewValue1(pos, OpLoadReg, v.Type, vi.spill)
454 s.f.Fatalf("attempt to load unspilled value %v", v.LongString())
460 s.nospill |= regMask(1) << r
465 // isLeaf reports whether f performs any calls.
466 func isLeaf(f *Func) bool {
467 for _, b := range f.Blocks {
468 for _, v := range b.Values {
469 if opcodeTable[v.Op].call {
477 func (s *regAllocState) init(f *Func) {
479 s.registers = f.Config.registers
480 if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask(0))*8) {
481 s.f.Fatalf("bad number of registers: %d", nr)
483 s.numRegs = register(nr)
485 // Locate SP, SB, and g registers.
489 for r := register(0); r < s.numRegs; r++ {
490 switch s.registers[r].Name() {
499 // Make sure we found all required registers.
502 s.f.Fatalf("no SP register found")
504 s.f.Fatalf("no SB register found")
506 if f.Config.hasGReg {
507 s.f.Fatalf("no g register found")
511 // Figure out which registers we're allowed to use.
512 s.allocatable = s.f.Config.gpRegMask | s.f.Config.fpRegMask | s.f.Config.specialRegMask
513 s.allocatable &^= 1 << s.SPReg
514 s.allocatable &^= 1 << s.SBReg
515 if s.f.Config.hasGReg {
516 s.allocatable &^= 1 << s.GReg
518 if s.f.Config.ctxt.Framepointer_enabled && s.f.Config.FPReg >= 0 {
519 s.allocatable &^= 1 << uint(s.f.Config.FPReg)
521 if s.f.Config.ctxt.Flag_shared {
522 switch s.f.Config.arch {
523 case "ppc64le": // R2 already reserved.
524 s.allocatable &^= 1 << 12 // R12
527 if s.f.Config.LinkReg != -1 {
529 // Leaf functions don't save/restore the link register.
530 s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
532 if s.f.Config.arch == "arm" && obj.GOARM == 5 {
533 // On ARMv5 we insert softfloat calls at each FP instruction.
534 // This clobbers LR almost everywhere. Disable allocating LR
536 s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
539 if s.f.Config.ctxt.Flag_dynlink {
540 switch s.f.Config.arch {
542 s.allocatable &^= 1 << 15 // R15
544 s.allocatable &^= 1 << 9 // R9
545 case "ppc64le": // R2 already reserved.
546 s.allocatable &^= 1 << 12 // R12
551 // Note that for Flag_shared (position independent code)
552 // we do need to be careful, but that carefulness is hidden
553 // in the rewrite rules so we always have a free register
554 // available for global load/stores. See gen/386.rules (search for Flag_shared).
556 // nothing to do, R10 & R11 already reserved
558 s.f.Config.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch)
562 switch s.f.Config.arch {
564 s.allocatable &^= 1 << 9 // R9 is "thread pointer" on nacl/arm
566 s.allocatable &^= 1 << 5 // BP - reserved for nacl
567 s.allocatable &^= 1 << 15 // R15 - reserved for nacl
570 if s.f.Config.use387 {
571 s.allocatable &^= 1 << 15 // X7 disallowed (one 387 register is used as scratch space during SSE->387 generation in ../x86/387.go)
574 s.regs = make([]regState, s.numRegs)
575 s.values = make([]valState, f.NumValues())
576 s.orig = make([]*Value, f.NumValues())
577 s.copies = make(map[*Value]bool)
578 for _, b := range f.Blocks {
579 for _, v := range b.Values {
580 if !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple() {
581 s.values[v.ID].needReg = true
582 s.values[v.ID].rematerializeable = v.rematerializeable()
585 // Note: needReg is false for values returning Tuple types.
586 // Instead, we mark the corresponding Selects as needReg.
591 // Compute block order. This array allows us to distinguish forward edges
592 // from backward edges and compute how far they go.
593 blockOrder := make([]int32, f.NumBlocks())
594 for i, b := range f.Blocks {
595 blockOrder[b.ID] = int32(i)
598 // Compute primary predecessors.
599 s.primary = make([]int32, f.NumBlocks())
600 for _, b := range f.Blocks {
602 for i, e := range b.Preds {
604 if blockOrder[p.ID] >= blockOrder[b.ID] {
605 continue // backward edge
607 if best == -1 || blockOrder[p.ID] > blockOrder[b.Preds[best].b.ID] {
611 s.primary[b.ID] = int32(best)
614 s.endRegs = make([][]endReg, f.NumBlocks())
615 s.startRegs = make([][]startReg, f.NumBlocks())
616 s.spillLive = make([][]ID, f.NumBlocks())
619 // Adds a use record for id at distance dist from the start of the block.
620 // All calls to addUse must happen with nonincreasing dist.
621 func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) {
622 r := s.freeUseRecords
624 s.freeUseRecords = r.next
630 r.next = s.values[id].uses
631 s.values[id].uses = r
632 if r.next != nil && dist > r.next.dist {
633 s.f.Fatalf("uses added in wrong order")
637 // advanceUses advances the uses of v's args from the state before v to the state after v.
638 // Any values which have no more uses are deallocated from registers.
639 func (s *regAllocState) advanceUses(v *Value) {
640 for _, a := range v.Args {
641 if !s.values[a.ID].needReg {
644 ai := &s.values[a.ID]
648 // Value is dead, free all registers that hold it.
651 r.next = s.freeUseRecords
656 // liveAfterCurrentInstruction reports whether v is live after
657 // the current instruction is completed. v must be used by the
658 // current instruction.
659 func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
660 u := s.values[v.ID].uses
662 for u != nil && u.dist == d {
665 return u != nil && u.dist > d
668 // Sets the state of the registers to that encoded in regs.
669 func (s *regAllocState) setState(regs []endReg) {
671 for _, x := range regs {
672 s.assignReg(x.r, x.v, x.c)
676 // compatRegs returns the set of registers which can store a type t.
677 func (s *regAllocState) compatRegs(t Type) regMask {
679 if t.IsTuple() || t.IsFlags() {
682 if t.IsFloat() || t == TypeInt128 {
683 m = s.f.Config.fpRegMask
685 m = s.f.Config.gpRegMask
687 return m & s.allocatable
690 // loopForBlock returns the loop containing block b,
691 // provided that the loop is "interesting" for purposes
692 // of improving register allocation (= is inner, and does
693 // not contain a call)
694 func (s *regAllocState) loopForBlock(b *Block) *loop {
695 loop := s.loopnest.b2l[b.ID]
697 // Minor for-the-time-being optimization: nothing happens
698 // unless a loop is both inner and call-free, therefore
699 // don't bother with other loops.
700 if loop != nil && (loop.containsCall || !loop.isInner) {
706 func (s *regAllocState) regalloc(f *Func) {
707 liveSet := f.newSparseSet(f.NumValues())
708 defer f.retSparseSet(liveSet)
709 var oldSched []*Value
711 var phiRegs []register
715 var nSpills int // # of spills remaining
716 var nSpillsInner int // # of spills remaining in inner loops
717 var nSpillsSunk int // # of sunk spills remaining
718 var nSpillsChanged int // # of sunk spills lost because of register use change
719 var nSpillsSunkUnused int // # of spills not sunk because they were removed completely
720 var nSpillsNotSunkLateUse int // # of spills not sunk because of very late use (in shuffle)
722 // Data structure used for computing desired registers.
723 var desired desiredState
725 // Desired registers for inputs & outputs for each instruction in the block.
727 out [4]register // desired output registers
728 in [3][4]register // desired input registers (for inputs 0,1, and 2)
732 if f.Entry != f.Blocks[0] {
733 f.Fatalf("entry block must be first")
736 // Get loop nest so that spills in inner loops can be
737 // tracked. When the last block of a loop is processed,
738 // attempt to move spills out of the loop.
739 s.loopnest.findExits()
741 // Spills are moved from one block's slice of values to another's.
742 // This confuses register allocation if it occurs before it is
743 // complete, so candidates are recorded, then rechecked and
744 // moved after all allocation (register and stack) is complete.
745 // Because movement is only within a stack slot's lifetime, it
746 // is safe to do this.
747 var toSink []spillToSink
748 // Will be used to figure out live inputs to exit blocks of inner loops.
749 entryCandidates := newSparseMap(f.NumValues())
751 for _, b := range f.Blocks {
753 loop := s.loopForBlock(b)
755 // Initialize liveSet and uses fields for this block.
756 // Walk backwards through the block doing liveness analysis.
758 for _, e := range s.live[b.ID] {
759 s.addUse(e.ID, int32(len(b.Values))+e.dist, e.pos) // pseudo-uses from beyond end of block
762 if v := b.Control; v != nil && s.values[v.ID].needReg {
763 s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control value
766 for i := len(b.Values) - 1; i >= 0; i-- {
770 // Remove v from the live set, but don't add
771 // any inputs. This is the state the len(b.Preds)>1
772 // case below desires; it wants to process phis specially.
775 for _, a := range v.Args {
776 if !s.values[a.ID].needReg {
779 s.addUse(a.ID, int32(i), v.Pos)
783 if s.f.pass.debug > regDebug {
784 fmt.Printf("uses for %s:%s\n", s.f.Name, b)
785 for i := range s.values {
791 fmt.Printf(" v%d:", i)
793 fmt.Printf(" %d", u.dist)
800 // Make a copy of the block schedule so we can generate a new one in place.
801 // We make a separate copy for phis and regular values.
803 for _, v := range b.Values {
809 phis = append(phis[:0], b.Values[:nphi]...)
810 oldSched = append(oldSched[:0], b.Values[nphi:]...)
811 b.Values = b.Values[:0]
813 // Initialize start state of block.
815 // Regalloc state is empty to start.
817 f.Fatalf("phis in entry block")
819 } else if len(b.Preds) == 1 {
820 // Start regalloc state with the end state of the previous block.
821 s.setState(s.endRegs[b.Preds[0].b.ID])
823 f.Fatalf("phis in single-predecessor block")
825 // Drop any values which are no longer live.
826 // This may happen because at the end of p, a value may be
827 // live but only used by some other successor of p.
828 for r := register(0); r < s.numRegs; r++ {
830 if v != nil && !liveSet.contains(v.ID) {
835 // This is the complicated case. We have more than one predecessor,
836 // which means we may have Phi ops.
838 // Copy phi ops into new schedule.
839 b.Values = append(b.Values, phis...)
841 // Start with the final register state of the primary predecessor
842 idx := s.primary[b.ID]
844 f.Fatalf("block with no primary predecessor %s", b)
847 s.setState(s.endRegs[p.ID])
849 if s.f.pass.debug > regDebug {
850 fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
851 for _, x := range s.endRegs[p.ID] {
852 fmt.Printf(" %s: orig:%s cache:%s\n", s.registers[x.r].Name(), x.v, x.c)
856 // Decide on registers for phi ops. Use the registers determined
857 // by the primary predecessor if we can.
858 // TODO: pick best of (already processed) predecessors?
859 // Majority vote? Deepest nesting level?
860 phiRegs = phiRegs[:0]
862 for _, v := range phis {
863 if !s.values[v.ID].needReg {
864 phiRegs = append(phiRegs, noRegister)
868 // Some instructions target not-allocatable registers.
869 // They're not suitable for further (phi-function) allocation.
870 m := s.values[a.ID].regs &^ phiUsed & s.allocatable
873 phiUsed |= regMask(1) << r
874 phiRegs = append(phiRegs, r)
876 phiRegs = append(phiRegs, noRegister)
880 // Second pass - deallocate any phi inputs which are now dead.
881 for i, v := range phis {
882 if !s.values[v.ID].needReg {
886 if !liveSet.contains(a.ID) {
887 // Input is dead beyond the phi, deallocate
888 // anywhere else it might live.
889 s.freeRegs(s.values[a.ID].regs)
891 // Input is still live.
892 // Try to move it around before kicking out, if there is a free register.
893 // We generate a Copy in the predecessor block and record it. It will be
894 // deleted if never used.
899 // Pick a free register. At this point some registers used in the predecessor
900 // block may have been deallocated. Those are the ones used for Phis. Exclude
901 // them (and they are not going to be helpful anyway).
902 m := s.compatRegs(a.Type) &^ s.used &^ phiUsed
903 if m != 0 && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 {
905 c := p.NewValue1(a.Pos, OpCopy, a.Type, s.regs[r].c)
907 if s.f.pass.debug > regDebug {
908 fmt.Printf("copy %s to %s : %s\n", a, c, s.registers[r2].Name())
911 s.assignReg(r2, a, c)
912 s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c})
918 // Third pass - pick registers for phis whose inputs
919 // were not in a register.
920 for i, v := range phis {
921 if !s.values[v.ID].needReg {
924 if phiRegs[i] != noRegister {
927 if s.f.Config.use387 && v.Type.IsFloat() {
928 continue // 387 can't handle floats in registers between blocks
930 m := s.compatRegs(v.Type) &^ phiUsed &^ s.used
934 phiUsed |= regMask(1) << r
938 // Set registers for phis. Add phi spill code.
939 for i, v := range phis {
940 if !s.values[v.ID].needReg {
946 // Spills will be inserted in all the predecessors below.
947 s.values[v.ID].spill = v // v starts life spilled
948 s.values[v.ID].spillUsed = true // use is guaranteed
951 // register-based phi
953 // Spill the phi in case we need to restore it later.
954 spill := b.NewValue1(v.Pos, OpStoreReg, v.Type, v)
956 s.values[v.ID].spill = spill
957 s.values[v.ID].spillUsed = false
959 loop.spills = append(loop.spills, v)
965 // Save the starting state for use by merge edges.
966 var regList []startReg
967 for r := register(0); r < s.numRegs; r++ {
972 if phiUsed>>r&1 != 0 {
973 // Skip registers that phis used, we'll handle those
974 // specially during merge edge processing.
977 regList = append(regList, startReg{r, v.ID, s.values[v.ID].uses.pos})
979 s.startRegs[b.ID] = regList
981 if s.f.pass.debug > regDebug {
982 fmt.Printf("after phis\n")
983 for _, x := range s.startRegs[b.ID] {
984 fmt.Printf(" %s: v%d\n", s.registers[x.r].Name(), x.vid)
989 // Allocate space to record the desired registers for each value.
991 for i := 0; i < len(oldSched); i++ {
992 dinfo = append(dinfo, dentry{})
995 // Load static desired register info at the end of the block.
996 desired.copy(&s.desired[b.ID])
998 // Check actual assigned registers at the start of the next block(s).
999 // Dynamically assigned registers will trump the static
1000 // desired registers computed during liveness analysis.
1001 // Note that we do this phase after startRegs is set above, so that
1002 // we get the right behavior for a block which branches to itself.
1003 for _, e := range b.Succs {
1005 // TODO: prioritize likely successor?
1006 for _, x := range s.startRegs[succ.ID] {
1007 desired.add(x.vid, x.r)
1009 // Process phi ops in succ.
1011 for _, v := range succ.Values {
1015 if !s.values[v.ID].needReg {
1018 rp, ok := s.f.getHome(v.ID).(*Register)
1022 desired.add(v.Args[pidx].ID, register(rp.num))
1025 // Walk values backwards computing desired register info.
1026 // See computeLive for more comments.
1027 for i := len(oldSched) - 1; i >= 0; i-- {
1029 prefs := desired.remove(v.ID)
1030 desired.clobber(opcodeTable[v.Op].reg.clobbers)
1031 for _, j := range opcodeTable[v.Op].reg.inputs {
1032 if countRegs(j.regs) != 1 {
1035 desired.clobber(j.regs)
1036 desired.add(v.Args[j.idx].ID, pickReg(j.regs))
1038 if opcodeTable[v.Op].resultInArg0 {
1039 if opcodeTable[v.Op].commutative {
1040 desired.addList(v.Args[1].ID, prefs)
1042 desired.addList(v.Args[0].ID, prefs)
1044 // Save desired registers for this value.
1045 dinfo[i].out = prefs
1046 for j, a := range v.Args {
1047 if j >= len(dinfo[i].in) {
1050 dinfo[i].in[j] = desired.get(a.ID)
1054 // Process all the non-phi values.
1055 for idx, v := range oldSched {
1056 if s.f.pass.debug > regDebug {
1057 fmt.Printf(" processing %s\n", v.LongString())
1059 regspec := opcodeTable[v.Op].reg
1061 f.Fatalf("phi %s not at start of block", v)
1064 s.assignReg(s.SPReg, v, v)
1065 b.Values = append(b.Values, v)
1070 s.assignReg(s.SBReg, v, v)
1071 b.Values = append(b.Values, v)
1075 if v.Op == OpSelect0 || v.Op == OpSelect1 {
1076 if s.values[v.ID].needReg {
1078 if v.Op == OpSelect1 {
1081 s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
1083 b.Values = append(b.Values, v)
1087 if v.Op == OpGetG && s.f.Config.hasGReg {
1088 // use hardware g register
1089 if s.regs[s.GReg].v != nil {
1090 s.freeReg(s.GReg) // kick out the old value
1092 s.assignReg(s.GReg, v, v)
1093 b.Values = append(b.Values, v)
1098 // Args are "pre-spilled" values. We don't allocate
1099 // any register here. We just set up the spill pointer to
1100 // point at itself and any later user will restore it to use it.
1101 s.values[v.ID].spill = v
1102 s.values[v.ID].spillUsed = true // use is guaranteed
1103 b.Values = append(b.Values, v)
1107 if v.Op == OpKeepAlive {
1108 // Make sure the argument to v is still live here.
1110 vi := &s.values[v.Args[0].ID]
1112 // Use the spill location.
1113 v.SetArg(0, vi.spill)
1115 // No need to keep unspilled values live.
1116 // These are typically rematerializeable constants like nil,
1117 // or values of a variable that were modified since the last call.
1119 v.SetArgs1(v.Args[1])
1121 b.Values = append(b.Values, v)
1124 if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 {
1125 // No register allocation required (or none specified yet)
1126 s.freeRegs(regspec.clobbers)
1127 b.Values = append(b.Values, v)
1132 if s.values[v.ID].rematerializeable {
1133 // Value is rematerializeable, don't issue it here.
1134 // It will get issued just before each use (see
1135 // allocValueToReg).
1136 for _, a := range v.Args {
1143 if s.f.pass.debug > regDebug {
1144 fmt.Printf("value %s\n", v.LongString())
1146 for _, r := range dinfo[idx].out {
1147 if r != noRegister {
1148 fmt.Printf(" %s", s.registers[r].Name())
1152 for i := 0; i < len(v.Args) && i < 3; i++ {
1153 fmt.Printf(" in%d:", i)
1154 for _, r := range dinfo[idx].in[i] {
1155 if r != noRegister {
1156 fmt.Printf(" %s", s.registers[r].Name())
1163 // Move arguments to registers. Process in an ordering defined
1164 // by the register specification (most constrained first).
1165 args = append(args[:0], v.Args...)
1166 for _, i := range regspec.inputs {
1168 if mask&s.values[args[i.idx].ID].regs == 0 {
1169 // Need a new register for the input.
1170 mask &= s.allocatable
1172 // Used desired register if available.
1174 for _, r := range dinfo[idx].in[i.idx] {
1175 if r != noRegister && (mask&^s.used)>>r&1 != 0 {
1176 // Desired register is allowed and unused.
1177 mask = regMask(1) << r
1182 // Avoid registers we're saving for other values.
1183 if mask&^desired.avoid != 0 {
1184 mask &^= desired.avoid
1187 args[i.idx] = s.allocValToReg(args[i.idx], mask, true, v.Pos)
1190 // If the output clobbers the input register, make sure we have
1191 // at least two copies of the input register so we don't
1192 // have to reload the value from the spill location.
1193 if opcodeTable[v.Op].resultInArg0 {
1195 if !s.liveAfterCurrentInstruction(v.Args[0]) {
1196 // arg0 is dead. We can clobber its register.
1199 if s.values[v.Args[0].ID].rematerializeable {
1200 // We can rematerialize the input, don't worry about clobbering it.
1203 if countRegs(s.values[v.Args[0].ID].regs) >= 2 {
1204 // we have at least 2 copies of arg0. We can afford to clobber one.
1207 if opcodeTable[v.Op].commutative {
1208 if !s.liveAfterCurrentInstruction(v.Args[1]) {
1209 args[0], args[1] = args[1], args[0]
1212 if s.values[v.Args[1].ID].rematerializeable {
1213 args[0], args[1] = args[1], args[0]
1216 if countRegs(s.values[v.Args[1].ID].regs) >= 2 {
1217 args[0], args[1] = args[1], args[0]
1222 // We can't overwrite arg0 (or arg1, if commutative). So we
1223 // need to make a copy of an input so we have a register we can modify.
1225 // Possible new registers to copy into.
1226 m = s.compatRegs(v.Args[0].Type) &^ s.used
1228 // No free registers. In this case we'll just clobber
1229 // an input and future uses of that input must use a restore.
1230 // TODO(khr): We should really do this like allocReg does it,
1231 // spilling the value with the most distant next use.
1235 // Try to move an input to the desired output.
1236 for _, r := range dinfo[idx].out {
1237 if r != noRegister && m>>r&1 != 0 {
1239 args[0] = s.allocValToReg(v.Args[0], m, true, v.Pos)
1240 // Note: we update args[0] so the instruction will
1241 // use the register copy we just made.
1245 // Try to copy input to its desired location & use its old
1246 // location as the result register.
1247 for _, r := range dinfo[idx].in[0] {
1248 if r != noRegister && m>>r&1 != 0 {
1250 c := s.allocValToReg(v.Args[0], m, true, v.Pos)
1252 // Note: no update to args[0] so the instruction will
1253 // use the original copy.
1257 if opcodeTable[v.Op].commutative {
1258 for _, r := range dinfo[idx].in[1] {
1259 if r != noRegister && m>>r&1 != 0 {
1261 c := s.allocValToReg(v.Args[1], m, true, v.Pos)
1263 args[0], args[1] = args[1], args[0]
1268 // Avoid future fixed uses if we can.
1269 if m&^desired.avoid != 0 {
1272 // Save input 0 to a new register so we can clobber it.
1273 c := s.allocValToReg(v.Args[0], m, true, v.Pos)
1278 // Now that all args are in regs, we're ready to issue the value itself.
1279 // Before we pick a register for the output value, allow input registers
1280 // to be deallocated. We do this here so that the output can use the
1281 // same register as a dying input.
1282 if !opcodeTable[v.Op].resultNotInArgs {
1283 s.tmpused = s.nospill
1285 s.advanceUses(v) // frees any registers holding args that are no longer live
1288 // Dump any registers which will be clobbered
1289 s.freeRegs(regspec.clobbers)
1290 s.tmpused |= regspec.clobbers
1292 // Pick registers for outputs.
1294 outRegs := [2]register{noRegister, noRegister}
1296 for _, out := range regspec.outputs {
1297 mask := out.regs & s.allocatable &^ used
1301 if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
1302 if !opcodeTable[v.Op].commutative {
1303 // Output must use the same register as input 0.
1304 r := register(s.f.getHome(args[0].ID).(*Register).num)
1305 mask = regMask(1) << r
1307 // Output must use the same register as input 0 or 1.
1308 r0 := register(s.f.getHome(args[0].ID).(*Register).num)
1309 r1 := register(s.f.getHome(args[1].ID).(*Register).num)
1310 // Check r0 and r1 for desired output register.
1312 for _, r := range dinfo[idx].out {
1313 if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 {
1314 mask = regMask(1) << r
1317 args[0], args[1] = args[1], args[0]
1323 // Neither are desired, pick r0.
1324 mask = regMask(1) << r0
1328 for _, r := range dinfo[idx].out {
1329 if r != noRegister && (mask&^s.used)>>r&1 != 0 {
1330 // Desired register is allowed and unused.
1331 mask = regMask(1) << r
1335 // Avoid registers we're saving for other values.
1336 if mask&^desired.avoid != 0 {
1337 mask &^= desired.avoid
1339 r := s.allocReg(mask, v)
1340 outRegs[out.idx] = r
1341 used |= regMask(1) << r
1342 s.tmpused |= regMask(1) << r
1344 // Record register choices
1345 if v.Type.IsTuple() {
1347 if r := outRegs[0]; r != noRegister {
1348 outLocs[0] = &s.registers[r]
1350 if r := outRegs[1]; r != noRegister {
1351 outLocs[1] = &s.registers[r]
1353 s.f.setHome(v, outLocs)
1354 // Note that subsequent SelectX instructions will do the assignReg calls.
1356 if r := outRegs[0]; r != noRegister {
1357 s.assignReg(r, v, v)
1362 // deallocate dead args, if we have not done so
1363 if opcodeTable[v.Op].resultNotInArgs {
1365 s.advanceUses(v) // frees any registers holding args that are no longer live
1369 // Issue the Value itself.
1370 for i, a := range args {
1371 v.SetArg(i, a) // use register version of arguments
1373 b.Values = append(b.Values, v)
1375 // Issue a spill for this value. We issue spills unconditionally,
1376 // then at the end of regalloc delete the ones we never use.
1377 // TODO: schedule the spill at a point that dominates all restores.
1378 // The restore may be off in an unlikely branch somewhere and it
1379 // would be better to have the spill in that unlikely branch as well.
1384 // It would be good to have both spill and restore inside the IF.
1386 if s.values[v.ID].needReg {
1387 spill := b.NewValue1(v.Pos, OpStoreReg, v.Type, v)
1389 s.values[v.ID].spill = spill
1390 s.values[v.ID].spillUsed = false
1392 loop.spills = append(loop.spills, v)
1399 // Load control value into reg.
1400 if v := b.Control; v != nil && s.values[v.ID].needReg {
1401 if s.f.pass.debug > regDebug {
1402 fmt.Printf(" processing control %s\n", v.LongString())
1404 // We assume that a control input can be passed in any
1405 // type-compatible register. If this turns out not to be true,
1406 // we'll need to introduce a regspec for a block's control value.
1407 b.Control = s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos)
1412 // Remove this use from the uses list.
1413 vi := &s.values[v.ID]
1417 s.freeRegs(vi.regs) // value is dead
1419 u.next = s.freeUseRecords
1420 s.freeUseRecords = u
1423 // Spill any values that can't live across basic block boundaries.
1424 if s.f.Config.use387 {
1425 s.freeRegs(s.f.Config.fpRegMask)
1428 // If we are approaching a merge point and we are the primary
1429 // predecessor of it, find live values that we use soon after
1430 // the merge point and promote them to registers now.
1431 if len(b.Succs) == 1 {
1432 // For this to be worthwhile, the loop must have no calls in it.
1434 loop := s.loopnest.b2l[top.ID]
1435 if loop == nil || loop.header != top || loop.containsCall {
1439 // TODO: sort by distance, pick the closest ones?
1440 for _, live := range s.live[b.ID] {
1441 if live.dist >= unlikelyDistance {
1442 // Don't preload anything live after the loop.
1446 vi := &s.values[vid]
1450 if vi.rematerializeable {
1454 if s.f.Config.use387 && v.Type.IsFloat() {
1455 continue // 387 can't handle floats in registers between blocks
1457 m := s.compatRegs(v.Type) &^ s.used
1458 if m&^desired.avoid != 0 {
1462 s.allocValToReg(v, m, false, b.Pos)
1469 // Save end-of-block register state.
1470 // First count how many, this cuts allocations in half.
1472 for r := register(0); r < s.numRegs; r++ {
1479 regList := make([]endReg, 0, k)
1480 for r := register(0); r < s.numRegs; r++ {
1485 regList = append(regList, endReg{r, v, s.regs[r].c})
1487 s.endRegs[b.ID] = regList
1491 for _, x := range s.live[b.ID] {
1494 for r := register(0); r < s.numRegs; r++ {
1499 if !liveSet.contains(v.ID) {
1500 s.f.Fatalf("val %s is in reg but not live at end of %s", v, b)
1505 // If a value is live at the end of the block and
1506 // isn't in a register, remember that its spill location
1507 // is live. We need to remember this information so that
1508 // the liveness analysis in stackalloc is correct.
1509 for _, e := range s.live[b.ID] {
1510 if s.values[e.ID].regs != 0 {
1511 // in a register, we'll use that source for the merge.
1514 spill := s.values[e.ID].spill
1516 // rematerializeable values will have spill==nil.
1519 s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID)
1520 s.values[e.ID].spillUsed = true
1523 // Keep track of values that are spilled in the loop, but whose spill
1524 // is not used in the loop. It may be possible to move ("sink") the
1525 // spill out of the loop into one or more exit blocks.
1527 loop.scratch++ // increment count of blocks in this loop that have been processed
1528 if loop.scratch == loop.nBlocks { // just processed last block of loop, if it is an inner loop.
1529 // This check is redundant with code at the top of the loop.
1530 // This is definitive; the one at the top of the loop is an optimization.
1531 if loop.isInner && // Common case, easier, most likely to be profitable
1532 !loop.containsCall && // Calls force spills, also lead to puzzling spill info.
1533 len(loop.exits) <= 32 { // Almost no inner loops have more than 32 exits,
1534 // and this allows use of a bitvector and a sparseMap.
1536 // TODO: exit calculation is messed up for non-inner loops
1537 // because of multilevel exits that are not part of the "exit"
1540 // Compute the set of spill-movement candidates live at entry to exit blocks.
1541 // isLoopSpillCandidate filters for
1542 // (1) defined in appropriate loop
1543 // (2) needs a register
1544 // (3) spill not already used (in the loop)
1545 // Condition (3) === "in a register at all loop exits"
1547 entryCandidates.clear()
1549 for whichExit, ss := range loop.exits {
1550 // Start with live at end.
1551 for _, li := range s.live[ss.ID] {
1552 if s.isLoopSpillCandidate(loop, s.orig[li.ID]) {
1553 // s.live contains original IDs, use s.orig above to map back to *Value
1554 entryCandidates.setBit(li.ID, uint(whichExit))
1557 // Control can also be live.
1558 if ss.Control != nil && s.orig[ss.Control.ID] != nil && s.isLoopSpillCandidate(loop, s.orig[ss.Control.ID]) {
1559 entryCandidates.setBit(s.orig[ss.Control.ID].ID, uint(whichExit))
1561 // Walk backwards, filling in locally live values, removing those defined.
1562 for i := len(ss.Values) - 1; i >= 0; i-- {
1564 vorig := s.orig[v.ID]
1566 entryCandidates.remove(vorig.ID) // Cannot be an issue, only keeps the sets smaller.
1568 for _, a := range v.Args {
1569 aorig := s.orig[a.ID]
1570 if aorig != nil && s.isLoopSpillCandidate(loop, aorig) {
1571 entryCandidates.setBit(aorig.ID, uint(whichExit))
1577 for _, e := range loop.spills {
1578 whichblocks := entryCandidates.get(e.ID)
1579 oldSpill := s.values[e.ID].spill
1580 if whichblocks != 0 && whichblocks != -1 { // -1 = not in map.
1581 toSink = append(toSink, spillToSink{spill: oldSpill, dests: whichblocks})
1585 } // loop is inner etc
1586 loop.scratch = 0 // Don't leave a mess, just in case.
1588 } // if scratch == nBlocks
1589 } // if loop is not nil
1591 // Clear any final uses.
1592 // All that is left should be the pseudo-uses added for values which
1593 // are live at the end of b.
1594 for _, e := range s.live[b.ID] {
1595 u := s.values[e.ID].uses
1597 f.Fatalf("live at end, no uses v%d", e.ID)
1600 f.Fatalf("live at end, too many uses v%d", e.ID)
1602 s.values[e.ID].uses = nil
1603 u.next = s.freeUseRecords
1604 s.freeUseRecords = u
1608 // Erase any spills we never used
1609 for i := range s.values {
1612 if s.f.pass.debug > logSpills && vi.spill.Op != OpArg {
1613 s.f.Config.Warnl(vi.spill.Pos, "spilled value at %v remains", vi.spill)
1619 // Constants, SP, SB, ...
1622 loop := s.loopForBlock(spill.Block)
1627 spill.Args[0].Uses--
1632 for _, b := range f.Blocks {
1634 for _, v := range b.Values {
1635 if v.Op == OpInvalid {
1641 b.Values = b.Values[:i]
1642 // TODO: zero b.Values[i:], recycle Values
1643 // Not important now because this is the last phase that manipulates Values
1646 // Must clear these out before any potential recycling, though that's
1647 // not currently implemented.
1648 for i, ts := range toSink {
1650 if vsp.Op == OpInvalid { // This spill was completely eliminated
1651 toSink[i].spill = nil
1655 // Anything that didn't get a register gets a stack location here.
1656 // (StoreReg, stack-based phis, inputs, ...)
1657 stacklive := stackalloc(s.f, s.spillLive)
1659 // Fix up all merge edges.
1660 s.shuffle(stacklive)
1662 // Insert moved spills (that have not been marked invalid above)
1663 // at start of appropriate block and remove the originals from their
1664 // location within loops. Notice that this can break SSA form;
1665 // if a spill is sunk to multiple exits, there will be no phi for that
1666 // spill at a join point downstream of those two exits, though the
1667 // two spills will target the same stack slot. Notice also that this
1668 // takes place after stack allocation, so the stack allocator does
1669 // not need to process these malformed flow graphs.
1671 for _, ts := range toSink {
1673 if vsp == nil { // This spill was completely eliminated
1677 e := ts.spilledValue()
1678 if s.values[e.ID].spillUsedShuffle {
1679 nSpillsNotSunkLateUse++
1683 // move spills to a better (outside of loop) block.
1684 // This would be costly if it occurred very often, but it doesn't.
1686 loop := s.loopnest.b2l[b.ID]
1689 // Pre-check to be sure that spilled value is still in expected register on all exits where live.
1690 check_val_still_in_reg:
1691 for i := uint(0); i < 32 && dests != 0; i++ {
1693 if dests&(1<<i) == 0 {
1698 if len(d.Preds) > 1 {
1699 panic("Should be impossible given critical edges removed")
1701 p := d.Preds[0].b // block in loop exiting to d.
1703 endregs := s.endRegs[p.ID]
1704 for _, regrec := range endregs {
1705 if regrec.v == e && regrec.r != noRegister && regrec.c == e { // TODO: regrec.c != e implies different spill possible.
1706 continue check_val_still_in_reg
1709 // If here, the register assignment was lost down at least one exit and it can't be sunk
1710 if s.f.pass.debug > moveSpills {
1711 s.f.Config.Warnl(e.Pos, "lost register assignment for spill %v in %v at exit %v to %v",
1720 // don't update nSpills, since spill is only moved, and if it is duplicated, the spills-on-a-path is not increased.
1724 // remove vsp from b.Values
1726 for _, w := range b.Values {
1733 b.Values = b.Values[:i]
1736 for i := uint(0); i < 32 && dests != 0; i++ {
1738 if dests&(1<<i) == 0 {
1745 vspnew := vsp // reuse original for first sunk spill, saves tracking down and renaming uses
1746 if !first { // any sunk spills after first must make a copy
1747 vspnew = d.NewValue1(e.Pos, OpStoreReg, e.Type, e)
1748 f.setHome(vspnew, f.getHome(vsp.ID)) // copy stack home
1749 if s.f.pass.debug > moveSpills {
1750 s.f.Config.Warnl(e.Pos, "copied spill %v in %v for %v to %v in %v",
1751 vsp, b, e, vspnew, d)
1756 d.Values = append(d.Values, vspnew)
1757 if s.f.pass.debug > moveSpills {
1758 s.f.Config.Warnl(e.Pos, "moved spill %v in %v for %v to %v in %v",
1759 vsp, b, e, vspnew, d)
1763 // shuffle vspnew to the beginning of its block
1764 copy(d.Values[1:], d.Values[0:len(d.Values)-1])
1765 d.Values[0] = vspnew
1770 // Erase any copies we never used.
1771 // Also, an unused copy might be the only use of another copy,
1772 // so continue erasing until we reach a fixed point.
1775 for c, used := range s.copies {
1776 if !used && c.Uses == 0 {
1777 if s.f.pass.debug > regDebug {
1778 fmt.Printf("delete copied value %s\n", c.LongString())
1791 for _, b := range f.Blocks {
1793 for _, v := range b.Values {
1794 if v.Op == OpInvalid {
1800 b.Values = b.Values[:i]
1803 if f.pass.stats > 0 {
1804 f.LogStat("spills_info",
1805 nSpills, "spills", nSpillsInner, "inner_spills_remaining", nSpillsSunk, "inner_spills_sunk", nSpillsSunkUnused, "inner_spills_unused", nSpillsNotSunkLateUse, "inner_spills_shuffled", nSpillsChanged, "inner_spills_changed")
1809 // isLoopSpillCandidate indicates whether the spill for v satisfies preliminary
1810 // spill-sinking conditions just after the last block of loop has been processed.
1812 // v needs a register.
1813 // v's spill is not (YET) used.
1814 // v's definition is within loop.
1815 // The spill may be used in the future, either by an outright use
1816 // in the code, or by shuffling code inserted after stack allocation.
1817 // Outright uses cause sinking; shuffling (within the loop) inhibits it.
1818 func (s *regAllocState) isLoopSpillCandidate(loop *loop, v *Value) bool {
1819 return s.values[v.ID].needReg && !s.values[v.ID].spillUsed && s.loopnest.b2l[v.Block.ID] == loop
1822 // lateSpillUse notes a late (after stack allocation) use of the spill of value with ID vid.
1823 // This will inhibit spill sinking.
1824 func (s *regAllocState) lateSpillUse(vid ID) {
1825 // TODO investigate why this is necessary.
1826 // It appears that an outside-the-loop use of
1827 // an otherwise sinkable spill makes the spill
1828 // a candidate for shuffling, when it would not
1829 // otherwise have been the case (spillUsed was not
1830 // true when isLoopSpillCandidate was called, yet
1831 // it was shuffled). Such shuffling cuts the amount
1832 // of spill sinking by more than half (in make.bash)
1833 s.values[vid].spillUsedShuffle = true
1836 // shuffle fixes up all the merge edges (those going into blocks of indegree > 1).
1837 func (s *regAllocState) shuffle(stacklive [][]ID) {
1840 e.cache = map[ID][]*Value{}
1841 e.contents = map[Location]contentRecord{}
1842 if s.f.pass.debug > regDebug {
1843 fmt.Printf("shuffle %s\n", s.f.Name)
1844 fmt.Println(s.f.String())
1847 for _, b := range s.f.Blocks {
1848 if len(b.Preds) <= 1 {
1852 for i, edge := range b.Preds {
1855 e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID])
1861 type edgeState struct {
1863 p, b *Block // edge goes from p->b.
1865 // for each pre-regalloc value, a list of equivalent cached values
1866 cache map[ID][]*Value
1867 cachedVals []ID // (superset of) keys of the above map, for deterministic iteration
1869 // map from location to the value it contains
1870 contents map[Location]contentRecord
1872 // desired destination locations
1873 destinations []dstRecord
1876 usedRegs regMask // registers currently holding something
1877 uniqueRegs regMask // registers holding the only copy of a value
1878 finalRegs regMask // registers holding final target
1881 type contentRecord struct {
1882 vid ID // pre-regalloc value
1883 c *Value // cached value
1884 final bool // this is a satisfied destination
1885 pos src.XPos // source position of use of the value
1888 type dstRecord struct {
1889 loc Location // register or stack slot
1890 vid ID // pre-regalloc value it should contain
1891 splice **Value // place to store reference to the generating instruction
1892 pos src.XPos // source position of use of this location
1895 // setup initializes the edge state for shuffling.
1896 func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) {
1897 if e.s.f.pass.debug > regDebug {
1898 fmt.Printf("edge %s->%s\n", e.p, e.b)
1902 for _, vid := range e.cachedVals {
1903 delete(e.cache, vid)
1905 e.cachedVals = e.cachedVals[:0]
1906 for k := range e.contents {
1907 delete(e.contents, k)
1913 // Live registers can be sources.
1914 for _, x := range srcReg {
1915 e.set(&e.s.registers[x.r], x.v.ID, x.c, false, src.NoXPos) // don't care the position of the source
1917 // So can all of the spill locations.
1918 for _, spillID := range stacklive {
1919 v := e.s.orig[spillID]
1920 spill := e.s.values[v.ID].spill
1921 e.set(e.s.f.getHome(spillID), v.ID, spill, false, src.NoXPos) // don't care the position of the source
1924 // Figure out all the destinations we need.
1925 dsts := e.destinations[:0]
1926 for _, x := range dstReg {
1927 dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.vid, nil, x.pos})
1929 // Phis need their args to end up in a specific location.
1930 for _, v := range e.b.Values {
1934 loc := e.s.f.getHome(v.ID)
1938 dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Pos})
1940 e.destinations = dsts
1942 if e.s.f.pass.debug > regDebug {
1943 for _, vid := range e.cachedVals {
1945 for _, c := range a {
1946 fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID).Name(), vid, c)
1949 for _, d := range e.destinations {
1950 fmt.Printf("dst %s: v%d\n", d.loc.Name(), d.vid)
1955 // process generates code to move all the values to the right destination locations.
1956 func (e *edgeState) process() {
1957 dsts := e.destinations
1959 // Process the destinations until they are all satisfied.
1962 for _, d := range dsts {
1963 if !e.processDest(d.loc, d.vid, d.splice, d.pos) {
1964 // Failed - save for next iteration.
1970 // Made some progress. Go around again.
1973 // Append any extras destinations we generated.
1974 dsts = append(dsts, e.extra...)
1975 e.extra = e.extra[:0]
1979 // We made no progress. That means that any
1980 // remaining unsatisfied moves are in simple cycles.
1981 // For example, A -> B -> C -> D -> A.
1988 // To break the cycle, we pick an unused register, say R,
1989 // and put a copy of B there.
1994 // D <---- C <---- R=copyofB
1995 // When we resume the outer loop, the A->B move can now proceed,
1996 // and eventually the whole cycle completes.
1998 // Copy any cycle location to a temp register. This duplicates
1999 // one of the cycle entries, allowing the just duplicated value
2000 // to be overwritten and the cycle to proceed.
2003 vid := e.contents[loc].vid
2004 c := e.contents[loc].c
2005 r := e.findRegFor(c.Type)
2006 if e.s.f.pass.debug > regDebug {
2007 fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc.Name(), c)
2009 if _, isReg := loc.(*Register); isReg {
2010 c = e.p.NewValue1(d.pos, OpCopy, c.Type, c)
2012 e.s.lateSpillUse(vid)
2013 c = e.p.NewValue1(d.pos, OpLoadReg, c.Type, c)
2015 e.set(r, vid, c, false, d.pos)
2019 // processDest generates code to put value vid into location loc. Returns true
2020 // if progress was made.
2021 func (e *edgeState) processDest(loc Location, vid ID, splice **Value, pos src.XPos) bool {
2022 occupant := e.contents[loc]
2023 if occupant.vid == vid {
2024 // Value is already in the correct place.
2025 e.contents[loc] = contentRecord{vid, occupant.c, true, pos}
2028 *splice = occupant.c
2030 if occupant.c.Op == OpStoreReg {
2031 e.s.lateSpillUse(vid)
2034 // Note: if splice==nil then c will appear dead. This is
2035 // non-SSA formed code, so be careful after this pass not to run
2036 // deadcode elimination.
2037 if _, ok := e.s.copies[occupant.c]; ok {
2038 // The copy at occupant.c was used to avoid spill.
2039 e.s.copies[occupant.c] = true
2044 // Check if we're allowed to clobber the destination location.
2045 if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable {
2046 // We can't overwrite the last copy
2047 // of a value that needs to survive.
2051 // Copy from a source of v, register preferred.
2055 if e.s.f.pass.debug > regDebug {
2056 fmt.Printf("moving v%d to %s\n", vid, loc.Name())
2057 fmt.Printf("sources of v%d:", vid)
2059 for _, w := range e.cache[vid] {
2060 h := e.s.f.getHome(w.ID)
2061 if e.s.f.pass.debug > regDebug {
2062 fmt.Printf(" %s:%s", h.Name(), w)
2064 _, isreg := h.(*Register)
2065 if src == nil || isreg {
2070 if e.s.f.pass.debug > regDebug {
2072 fmt.Printf(" [use %s]\n", src.Name())
2074 fmt.Printf(" [no source]\n")
2077 _, dstReg := loc.(*Register)
2080 if !e.s.values[vid].rematerializeable {
2081 e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString())
2086 // Rematerialize into stack slot. Need a free
2087 // register to accomplish this.
2088 e.erase(loc) // see pre-clobber comment below
2089 r := e.findRegFor(v.Type)
2091 e.set(r, vid, x, false, pos)
2092 // Make sure we spill with the size of the slot, not the
2093 // size of x (which might be wider due to our dropping
2094 // of narrowing conversions).
2095 x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, x)
2098 // Emit move from src to dst.
2099 _, srcReg := src.(*Register)
2102 x = e.p.NewValue1(pos, OpCopy, c.Type, c)
2104 x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, c)
2108 e.s.lateSpillUse(vid)
2109 x = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
2111 // mem->mem. Use temp register.
2113 // Pre-clobber destination. This avoids the
2114 // following situation:
2115 // - v is currently held in R0 and stacktmp0.
2116 // - We want to copy stacktmp1 to stacktmp0.
2117 // - We choose R0 as the temporary register.
2118 // During the copy, both R0 and stacktmp0 are
2119 // clobbered, losing both copies of v. Oops!
2120 // Erasing the destination early means R0 will not
2121 // be chosen as the temp register, as it will then
2122 // be the last copy of v.
2125 r := e.findRegFor(c.Type)
2126 e.s.lateSpillUse(vid)
2127 t := e.p.NewValue1(pos, OpLoadReg, c.Type, c)
2128 e.set(r, vid, t, false, pos)
2129 x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, t)
2133 e.set(loc, vid, x, true, pos)
2142 // set changes the contents of location loc to hold the given value and its cached representative.
2143 func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, pos src.XPos) {
2144 e.s.f.setHome(c, loc)
2146 e.contents[loc] = contentRecord{vid, c, final, pos}
2149 e.cachedVals = append(e.cachedVals, vid)
2153 if r, ok := loc.(*Register); ok {
2154 e.usedRegs |= regMask(1) << uint(r.num)
2156 e.finalRegs |= regMask(1) << uint(r.num)
2159 e.uniqueRegs |= regMask(1) << uint(r.num)
2162 if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
2163 e.uniqueRegs &^= regMask(1) << uint(t.num)
2167 if e.s.f.pass.debug > regDebug {
2168 fmt.Printf("%s\n", c.LongString())
2169 fmt.Printf("v%d now available in %s:%s\n", vid, loc.Name(), c)
2173 // erase removes any user of loc.
2174 func (e *edgeState) erase(loc Location) {
2175 cr := e.contents[loc]
2182 // Add a destination to move this value back into place.
2183 // Make sure it gets added to the tail of the destination queue
2184 // so we make progress on other moves first.
2185 e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.pos})
2188 // Remove c from the list of cached values.
2190 for i, c := range a {
2191 if e.s.f.getHome(c.ID) == loc {
2192 if e.s.f.pass.debug > regDebug {
2193 fmt.Printf("v%d no longer available in %s:%s\n", vid, loc.Name(), c)
2195 a[i], a = a[len(a)-1], a[:len(a)-1]
2201 // Update register masks.
2202 if r, ok := loc.(*Register); ok {
2203 e.usedRegs &^= regMask(1) << uint(r.num)
2205 e.finalRegs &^= regMask(1) << uint(r.num)
2209 if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
2210 e.uniqueRegs |= regMask(1) << uint(r.num)
2215 // findRegFor finds a register we can use to make a temp copy of type typ.
2216 func (e *edgeState) findRegFor(typ Type) Location {
2217 // Which registers are possibilities.
2220 m = e.s.compatRegs(e.s.f.Config.fe.TypeFloat64())
2222 m = e.s.compatRegs(e.s.f.Config.fe.TypeInt64())
2225 // Pick a register. In priority order:
2226 // 1) an unused register
2227 // 2) a non-unique register not holding a final value
2228 // 3) a non-unique register
2229 x := m &^ e.usedRegs
2231 return &e.s.registers[pickReg(x)]
2233 x = m &^ e.uniqueRegs &^ e.finalRegs
2235 return &e.s.registers[pickReg(x)]
2237 x = m &^ e.uniqueRegs
2239 return &e.s.registers[pickReg(x)]
2242 // No register is available. Allocate a temp location to spill a register to.
2243 // The type of the slot is immaterial - it will not be live across
2244 // any safepoint. Just use a type big enough to hold any register.
2245 typ = e.s.f.Config.fe.TypeInt64()
2246 t := LocalSlot{e.s.f.Config.fe.Auto(typ), typ, 0}
2247 // TODO: reuse these slots.
2249 // Pick a register to spill.
2250 for _, vid := range e.cachedVals {
2252 for _, c := range a {
2253 if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m>>uint(r.num)&1 != 0 {
2254 x := e.p.NewValue1(c.Pos, OpStoreReg, c.Type, c)
2255 e.set(t, vid, x, false, c.Pos)
2256 if e.s.f.pass.debug > regDebug {
2257 fmt.Printf(" SPILL %s->%s %s\n", r.Name(), t.Name(), x.LongString())
2259 // r will now be overwritten by the caller. At some point
2260 // later, the newly saved value will be moved back to its
2261 // final destination in processDest.
2267 fmt.Printf("m:%d unique:%d final:%d\n", m, e.uniqueRegs, e.finalRegs)
2268 for _, vid := range e.cachedVals {
2270 for _, c := range a {
2271 fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID).Name())
2274 e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b)
2278 // rematerializeable reports whether the register allocator should recompute
2279 // a value instead of spilling/restoring it.
2280 func (v *Value) rematerializeable() bool {
2281 if !opcodeTable[v.Op].rematerializeable {
2284 for _, a := range v.Args {
2285 // SP and SB (generated by OpSP and OpSB) are always available.
2286 if a.Op != OpSP && a.Op != OpSB {
2293 type liveInfo struct {
2294 ID ID // ID of value
2295 dist int32 // # of instructions before next use
2296 pos src.XPos // source position of next use
2299 // dblock contains information about desired & avoid registers at the end of a block.
2300 type dblock struct {
2301 prefers []desiredStateEntry
2305 // computeLive computes a map from block ID to a list of value IDs live at the end
2306 // of that block. Together with the value ID is a count of how many instructions
2307 // to the next use of that value. The resulting map is stored in s.live.
2308 // computeLive also computes the desired register information at the end of each block.
2309 // This desired register information is stored in s.desired.
2310 // TODO: this could be quadratic if lots of variables are live across lots of
2311 // basic blocks. Figure out a way to make this function (or, more precisely, the user
2312 // of this function) require only linear size & time.
2313 func (s *regAllocState) computeLive() {
2315 s.live = make([][]liveInfo, f.NumBlocks())
2316 s.desired = make([]desiredState, f.NumBlocks())
2319 live := newSparseMap(f.NumValues())
2320 t := newSparseMap(f.NumValues())
2322 // Keep track of which value we want in each register.
2323 var desired desiredState
2325 // Instead of iterating over f.Blocks, iterate over their postordering.
2326 // Liveness information flows backward, so starting at the end
2327 // increases the probability that we will stabilize quickly.
2328 // TODO: Do a better job yet. Here's one possibility:
2329 // Calculate the dominator tree and locate all strongly connected components.
2330 // If a value is live in one block of an SCC, it is live in all.
2331 // Walk the dominator tree from end to beginning, just once, treating SCC
2332 // components as single blocks, duplicated calculated liveness information
2333 // out to all of them.
2335 s.loopnest = f.loopnest()
2339 for _, b := range po {
2340 // Start with known live values at the end of the block.
2341 // Add len(b.Values) to adjust from end-of-block distance
2342 // to beginning-of-block distance.
2344 for _, e := range s.live[b.ID] {
2345 live.set(e.ID, e.dist+int32(len(b.Values)), e.pos)
2348 // Mark control value as live
2349 if b.Control != nil && s.values[b.Control.ID].needReg {
2350 live.set(b.Control.ID, int32(len(b.Values)), b.Pos)
2353 // Propagate backwards to the start of the block
2354 // Assumes Values have been scheduled.
2356 for i := len(b.Values) - 1; i >= 0; i-- {
2360 // save phi ops for later
2361 phis = append(phis, v)
2364 if opcodeTable[v.Op].call {
2365 c := live.contents()
2367 c[i].val += unlikelyDistance
2370 for _, a := range v.Args {
2371 if s.values[a.ID].needReg {
2372 live.set(a.ID, int32(i), v.Pos)
2376 // Propagate desired registers backwards.
2377 desired.copy(&s.desired[b.ID])
2378 for i := len(b.Values) - 1; i >= 0; i-- {
2380 prefs := desired.remove(v.ID)
2382 // TODO: if v is a phi, save desired register for phi inputs.
2383 // For now, we just drop it and don't propagate
2384 // desired registers back though phi nodes.
2387 // Cancel desired registers if they get clobbered.
2388 desired.clobber(opcodeTable[v.Op].reg.clobbers)
2389 // Update desired registers if there are any fixed register inputs.
2390 for _, j := range opcodeTable[v.Op].reg.inputs {
2391 if countRegs(j.regs) != 1 {
2394 desired.clobber(j.regs)
2395 desired.add(v.Args[j.idx].ID, pickReg(j.regs))
2397 // Set desired register of input 0 if this is a 2-operand instruction.
2398 if opcodeTable[v.Op].resultInArg0 {
2399 if opcodeTable[v.Op].commutative {
2400 desired.addList(v.Args[1].ID, prefs)
2402 desired.addList(v.Args[0].ID, prefs)
2406 // For each predecessor of b, expand its list of live-at-end values.
2407 // invariant: live contains the values live at the start of b (excluding phi inputs)
2408 for i, e := range b.Preds {
2410 // Compute additional distance for the edge.
2411 // Note: delta must be at least 1 to distinguish the control
2412 // value use from the first user in a successor block.
2413 delta := int32(normalDistance)
2414 if len(p.Succs) == 2 {
2415 if p.Succs[0].b == b && p.Likely == BranchLikely ||
2416 p.Succs[1].b == b && p.Likely == BranchUnlikely {
2417 delta = likelyDistance
2419 if p.Succs[0].b == b && p.Likely == BranchUnlikely ||
2420 p.Succs[1].b == b && p.Likely == BranchLikely {
2421 delta = unlikelyDistance
2425 // Update any desired registers at the end of p.
2426 s.desired[p.ID].merge(&desired)
2428 // Start t off with the previously known live values at the end of p.
2430 for _, e := range s.live[p.ID] {
2431 t.set(e.ID, e.dist, e.pos)
2435 // Add new live values from scanning this block.
2436 for _, e := range live.contents() {
2438 if !t.contains(e.key) || d < t.get(e.key) {
2440 t.set(e.key, d, e.aux)
2443 // Also add the correct arg from the saved phi values.
2444 // All phis are at distance delta (we consider them
2445 // simultaneously happening at the start of the block).
2446 for _, v := range phis {
2448 if s.values[id].needReg && (!t.contains(id) || delta < t.get(id)) {
2450 t.set(id, delta, v.Pos)
2457 // The live set has changed, update it.
2458 l := s.live[p.ID][:0]
2459 if cap(l) < t.size() {
2460 l = make([]liveInfo, 0, t.size())
2462 for _, e := range t.contents() {
2463 l = append(l, liveInfo{e.key, e.val, e.aux})
2474 if f.pass.debug > regDebug {
2475 fmt.Println("live values at end of each block")
2476 for _, b := range f.Blocks {
2477 fmt.Printf(" %s:", b)
2478 for _, x := range s.live[b.ID] {
2479 fmt.Printf(" v%d", x.ID)
2480 for _, e := range s.desired[b.ID].entries {
2486 for _, r := range e.regs {
2487 if r == noRegister {
2493 fmt.Print(s.registers[r].Name())
2499 fmt.Printf(" avoid=%x", int64(s.desired[b.ID].avoid))
2505 // A desiredState represents desired register assignments.
2506 type desiredState struct {
2507 // Desired assignments will be small, so we just use a list
2508 // of valueID+registers entries.
2509 entries []desiredStateEntry
2510 // Registers that other values want to be in. This value will
2511 // contain at least the union of the regs fields of entries, but
2512 // may contain additional entries for values that were once in
2513 // this data structure but are no longer.
2516 type desiredStateEntry struct {
2517 // (pre-regalloc) value
2519 // Registers it would like to be in, in priority order.
2520 // Unused slots are filled with noRegister.
2524 func (d *desiredState) clear() {
2525 d.entries = d.entries[:0]
2529 // get returns a list of desired registers for value vid.
2530 func (d *desiredState) get(vid ID) [4]register {
2531 for _, e := range d.entries {
2536 return [4]register{noRegister, noRegister, noRegister, noRegister}
2539 // add records that we'd like value vid to be in register r.
2540 func (d *desiredState) add(vid ID, r register) {
2541 d.avoid |= regMask(1) << r
2542 for i := range d.entries {
2548 // Already known and highest priority
2551 for j := 1; j < len(e.regs); j++ {
2553 // Move from lower priority to top priority
2554 copy(e.regs[1:], e.regs[:j])
2559 copy(e.regs[1:], e.regs[:])
2563 d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}})
2566 func (d *desiredState) addList(vid ID, regs [4]register) {
2567 // regs is in priority order, so iterate in reverse order.
2568 for i := len(regs) - 1; i >= 0; i-- {
2570 if r != noRegister {
2576 // clobber erases any desired registers in the set m.
2577 func (d *desiredState) clobber(m regMask) {
2578 for i := 0; i < len(d.entries); {
2581 for _, r := range e.regs {
2582 if r != noRegister && m>>r&1 == 0 {
2588 // No more desired registers for this value.
2589 d.entries[i] = d.entries[len(d.entries)-1]
2590 d.entries = d.entries[:len(d.entries)-1]
2593 for ; j < len(e.regs); j++ {
2594 e.regs[j] = noRegister
2601 // copy copies a desired state from another desiredState x.
2602 func (d *desiredState) copy(x *desiredState) {
2603 d.entries = append(d.entries[:0], x.entries...)
2607 // remove removes the desired registers for vid and returns them.
2608 func (d *desiredState) remove(vid ID) [4]register {
2609 for i := range d.entries {
2610 if d.entries[i].ID == vid {
2611 regs := d.entries[i].regs
2612 d.entries[i] = d.entries[len(d.entries)-1]
2613 d.entries = d.entries[:len(d.entries)-1]
2617 return [4]register{noRegister, noRegister, noRegister, noRegister}
2620 // merge merges another desired state x into d.
2621 func (d *desiredState) merge(x *desiredState) {
2623 // There should only be a few desired registers, so
2624 // linear insert is ok.
2625 for _, e := range x.entries {
2626 d.addList(e.ID, e.regs)