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.
121 // distance is a measure of how far into the future values are used.
122 // distance is measured in units of instructions.
126 unlikelyDistance = 100
129 // regalloc performs register allocation on f. It sets f.RegAlloc
130 // to the resulting allocation.
131 func regalloc(f *Func) {
139 const noRegister register = 255
143 func (m regMask) String() string {
145 for r := register(0); m != 0; r++ {
149 m &^= regMask(1) << r
153 s += fmt.Sprintf("r%d", r)
158 // countRegs returns the number of set bits in the register mask.
159 func countRegs(r regMask) int {
168 // pickReg picks an arbitrary register from the register mask.
169 func pickReg(r regMask) register {
170 // pick the lowest one
172 panic("can't pick a register from an empty set")
174 for i := register(0); ; i++ {
183 dist int32 // distance from start of the block to a use of a value
184 line int32 // line number of the use
185 next *use // linked list of uses of a value in nondecreasing dist order
188 type valState struct {
189 regs regMask // the set of registers holding a Value (usually just one)
190 uses *use // list of uses in this block
191 spill *Value // spilled copy of the Value
193 spillUsedShuffle bool // true if used in shuffling, after ordinary uses
194 needReg bool // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags()
195 rematerializeable bool // cached value of v.rematerializeable()
198 type regState struct {
199 v *Value // Original (preregalloc) Value stored in this register.
200 c *Value // A Value equal to v which is currently in a register. Might be v or a copy of it.
201 // If a register is unused, v==c==nil
204 type regAllocState struct {
214 // for each block, its primary predecessor.
215 // A predecessor of b is primary if it is the closest
216 // predecessor that appears before b in the layout order.
217 // We record the index in the Preds list where the primary predecessor sits.
220 // live values at the end of each block. live[b.ID] is a list of value IDs
221 // which are live at the end of b, together with a count of how many instructions
222 // forward to the next use.
224 // desired register assignments at the end of each block.
225 // Note that this is a static map computed before allocation occurs. Dynamic
226 // register desires (from partially completed allocations) will trump
228 desired []desiredState
230 // current state of each (preregalloc) Value
233 // For each Value, map from its value ID back to the
234 // preregalloc Value it was derived from.
237 // current state of each register
240 // registers that contain values which can't be kicked out
243 // mask of registers currently in use
246 // mask of registers used in the current instruction
249 // current block we're working on
252 // cache of use records
255 // endRegs[blockid] is the register state at the end of each block.
256 // encoded as a set of endReg records.
259 // startRegs[blockid] is the register state at the start of merge blocks.
260 // saved state does not include the state of phi ops in the block.
261 startRegs [][]startReg
263 // spillLive[blockid] is the set of live spills at the end of each block
266 // a set of copies we generated to move things around, and
267 // whether it is used in shuffle. Unused copies will be deleted.
268 copies map[*Value]bool
273 type spillToSink struct {
274 spill *Value // Spill instruction to move (a StoreReg)
275 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]
278 func (sts *spillToSink) spilledValue() *Value {
279 return sts.spill.Args[0]
284 v *Value // pre-regalloc value held in this register (TODO: can we use ID here?)
285 c *Value // cached version of the value
288 type startReg struct {
290 vid ID // pre-regalloc value needed in this register
291 line int32 // line number of use of this register
294 // freeReg frees up register r. Any current user of r is kicked out.
295 func (s *regAllocState) freeReg(r register) {
298 s.f.Fatalf("tried to free an already free register %d\n", r)
302 if s.f.pass.debug > regDebug {
303 fmt.Printf("freeReg %s (dump %s/%s)\n", s.registers[r].Name(), v, s.regs[r].c)
305 s.regs[r] = regState{}
306 s.values[v.ID].regs &^= regMask(1) << r
307 s.used &^= regMask(1) << r
310 // freeRegs frees up all registers listed in m.
311 func (s *regAllocState) freeRegs(m regMask) {
313 s.freeReg(pickReg(m & s.used))
317 // setOrig records that c's original value is the same as
318 // v's original value.
319 func (s *regAllocState) setOrig(c *Value, v *Value) {
320 for int(c.ID) >= len(s.orig) {
321 s.orig = append(s.orig, nil)
323 if s.orig[c.ID] != nil {
324 s.f.Fatalf("orig value set twice %s %s", c, v)
326 s.orig[c.ID] = s.orig[v.ID]
329 // assignReg assigns register r to hold c, a copy of v.
331 func (s *regAllocState) assignReg(r register, v *Value, c *Value) {
332 if s.f.pass.debug > regDebug {
333 fmt.Printf("assignReg %s %s/%s\n", s.registers[r].Name(), v, c)
335 if s.regs[r].v != nil {
336 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)
340 s.regs[r] = regState{v, c}
341 s.values[v.ID].regs |= regMask(1) << r
342 s.used |= regMask(1) << r
343 s.f.setHome(c, &s.registers[r])
346 // allocReg chooses a register from the set of registers in mask.
347 // If there is no unused register, a Value will be kicked out of
348 // a register to make room.
349 func (s *regAllocState) allocReg(mask regMask, v *Value) register {
350 mask &= s.allocatable
353 s.f.Fatalf("no register available for %s", v)
356 // Pick an unused register if one is available.
357 if mask&^s.used != 0 {
358 return pickReg(mask &^ s.used)
361 // Pick a value to spill. Spill the value with the
362 // farthest-in-the-future use.
363 // TODO: Prefer registers with already spilled Values?
364 // TODO: Modify preference using affinity graph.
365 // TODO: if a single value is in multiple registers, spill one of them
366 // before spilling a value in just a single register.
368 // Find a register to spill. We spill the register containing the value
369 // whose next use is as far in the future as possible.
370 // https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
373 for t := register(0); t < s.numRegs; t++ {
378 if n := s.values[v.ID].uses.dist; n > maxuse {
379 // v's next use is farther in the future than any value
380 // we've seen so far. A new best spill candidate.
386 s.f.Fatalf("couldn't find register to spill")
389 // Try to move it around before kicking out, if there is a free register.
390 // We generate a Copy and record it. It will be deleted if never used.
392 m := s.compatRegs(v2.Type) &^ s.used &^ s.tmpused &^ (regMask(1) << r)
393 if m != 0 && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 {
395 c := s.curBlock.NewValue1(v2.Line, OpCopy, v2.Type, s.regs[r].c)
397 if s.f.pass.debug > regDebug {
398 fmt.Printf("copy %s to %s : %s\n", v2, c, s.registers[r2].Name())
401 s.assignReg(r2, v2, c)
407 // allocValToReg allocates v to a register selected from regMask and
408 // returns the register copy of v. Any previous user is kicked out and spilled
409 // (if necessary). Load code is added at the current pc. If nospill is set the
410 // allocated register is marked nospill so the assignment cannot be
411 // undone until the caller allows it by clearing nospill. Returns a
412 // *Value which is either v or a copy of v allocated to the chosen register.
413 func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, line int32) *Value {
414 vi := &s.values[v.ID]
416 // Check if v is already in a requested register.
417 if mask&vi.regs != 0 {
418 r := pickReg(mask & vi.regs)
419 if s.regs[r].v != v || s.regs[r].c == nil {
420 panic("bad register state")
423 s.nospill |= regMask(1) << r
428 // Allocate a register.
429 r := s.allocReg(mask, v)
431 // Allocate v to the new register.
434 // Copy from a register that v is already in.
435 r2 := pickReg(vi.regs)
436 if s.regs[r2].v != v {
437 panic("bad register state")
439 c = s.curBlock.NewValue1(line, OpCopy, v.Type, s.regs[r2].c)
440 } else if v.rematerializeable() {
441 // Rematerialize instead of loading from the spill location.
442 c = v.copyInto(s.curBlock)
445 // Load v from its spill location.
446 case vi.spill != nil:
447 if s.f.pass.debug > logSpills {
448 s.f.Config.Warnl(vi.spill.Line, "load spill for %v from %v", v, vi.spill)
450 c = s.curBlock.NewValue1(line, OpLoadReg, v.Type, vi.spill)
453 s.f.Fatalf("attempt to load unspilled value %v", v.LongString())
459 s.nospill |= regMask(1) << r
464 // isLeaf reports whether f performs any calls.
465 func isLeaf(f *Func) bool {
466 for _, b := range f.Blocks {
467 for _, v := range b.Values {
468 if opcodeTable[v.Op].call {
476 func (s *regAllocState) init(f *Func) {
478 s.registers = f.Config.registers
479 if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask(0))*8) {
480 s.f.Fatalf("bad number of registers: %d", nr)
482 s.numRegs = register(nr)
484 // Locate SP, SB, and g registers.
488 for r := register(0); r < s.numRegs; r++ {
489 switch s.registers[r].Name() {
498 // Make sure we found all required registers.
501 s.f.Fatalf("no SP register found")
503 s.f.Fatalf("no SB register found")
505 if f.Config.hasGReg {
506 s.f.Fatalf("no g register found")
510 // Figure out which registers we're allowed to use.
511 s.allocatable = s.f.Config.gpRegMask | s.f.Config.fpRegMask | s.f.Config.specialRegMask
512 s.allocatable &^= 1 << s.SPReg
513 s.allocatable &^= 1 << s.SBReg
514 if s.f.Config.hasGReg {
515 s.allocatable &^= 1 << s.GReg
517 if s.f.Config.ctxt.Framepointer_enabled && s.f.Config.FPReg >= 0 {
518 s.allocatable &^= 1 << uint(s.f.Config.FPReg)
520 if s.f.Config.ctxt.Flag_shared {
521 switch s.f.Config.arch {
522 case "ppc64le": // R2 already reserved.
523 s.allocatable &^= 1 << 12 // R12
526 if s.f.Config.LinkReg != -1 {
528 // Leaf functions don't save/restore the link register.
529 s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
531 if s.f.Config.arch == "arm" && obj.GOARM == 5 {
532 // On ARMv5 we insert softfloat calls at each FP instruction.
533 // This clobbers LR almost everywhere. Disable allocating LR
535 s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
538 if s.f.Config.ctxt.Flag_dynlink {
539 switch s.f.Config.arch {
541 s.allocatable &^= 1 << 15 // R15
543 s.allocatable &^= 1 << 9 // R9
544 case "ppc64le": // R2 already reserved.
545 s.allocatable &^= 1 << 12 // R12
550 // Note that for Flag_shared (position independent code)
551 // we do need to be careful, but that carefulness is hidden
552 // in the rewrite rules so we always have a free register
553 // available for global load/stores. See gen/386.rules (search for Flag_shared).
555 // nothing to do, R10 & R11 already reserved
557 s.f.Config.fe.Fatalf(0, "arch %s not implemented", s.f.Config.arch)
561 switch s.f.Config.arch {
563 s.allocatable &^= 1 << 9 // R9 is "thread pointer" on nacl/arm
565 s.allocatable &^= 1 << 5 // BP - reserved for nacl
566 s.allocatable &^= 1 << 15 // R15 - reserved for nacl
569 if s.f.Config.use387 {
570 s.allocatable &^= 1 << 15 // X7 disallowed (one 387 register is used as scratch space during SSE->387 generation in ../x86/387.go)
573 s.regs = make([]regState, s.numRegs)
574 s.values = make([]valState, f.NumValues())
575 s.orig = make([]*Value, f.NumValues())
576 s.copies = make(map[*Value]bool)
577 for _, b := range f.Blocks {
578 for _, v := range b.Values {
579 if !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple() {
580 s.values[v.ID].needReg = true
581 s.values[v.ID].rematerializeable = v.rematerializeable()
584 // Note: needReg is false for values returning Tuple types.
585 // Instead, we mark the corresponding Selects as needReg.
590 // Compute block order. This array allows us to distinguish forward edges
591 // from backward edges and compute how far they go.
592 blockOrder := make([]int32, f.NumBlocks())
593 for i, b := range f.Blocks {
594 blockOrder[b.ID] = int32(i)
597 // Compute primary predecessors.
598 s.primary = make([]int32, f.NumBlocks())
599 for _, b := range f.Blocks {
601 for i, e := range b.Preds {
603 if blockOrder[p.ID] >= blockOrder[b.ID] {
604 continue // backward edge
606 if best == -1 || blockOrder[p.ID] > blockOrder[b.Preds[best].b.ID] {
610 s.primary[b.ID] = int32(best)
613 s.endRegs = make([][]endReg, f.NumBlocks())
614 s.startRegs = make([][]startReg, f.NumBlocks())
615 s.spillLive = make([][]ID, f.NumBlocks())
618 // Adds a use record for id at distance dist from the start of the block.
619 // All calls to addUse must happen with nonincreasing dist.
620 func (s *regAllocState) addUse(id ID, dist int32, line int32) {
621 r := s.freeUseRecords
623 s.freeUseRecords = r.next
629 r.next = s.values[id].uses
630 s.values[id].uses = r
631 if r.next != nil && dist > r.next.dist {
632 s.f.Fatalf("uses added in wrong order")
636 // advanceUses advances the uses of v's args from the state before v to the state after v.
637 // Any values which have no more uses are deallocated from registers.
638 func (s *regAllocState) advanceUses(v *Value) {
639 for _, a := range v.Args {
640 if !s.values[a.ID].needReg {
643 ai := &s.values[a.ID]
647 // Value is dead, free all registers that hold it.
650 r.next = s.freeUseRecords
655 // liveAfterCurrentInstruction reports whether v is live after
656 // the current instruction is completed. v must be used by the
657 // current instruction.
658 func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
659 u := s.values[v.ID].uses
661 for u != nil && u.dist == d {
664 return u != nil && u.dist > d
667 // Sets the state of the registers to that encoded in regs.
668 func (s *regAllocState) setState(regs []endReg) {
670 for _, x := range regs {
671 s.assignReg(x.r, x.v, x.c)
675 // compatRegs returns the set of registers which can store a type t.
676 func (s *regAllocState) compatRegs(t Type) regMask {
678 if t.IsTuple() || t.IsFlags() {
681 if t.IsFloat() || t == TypeInt128 {
682 m = s.f.Config.fpRegMask
684 m = s.f.Config.gpRegMask
686 return m & s.allocatable
689 // loopForBlock returns the loop containing block b,
690 // provided that the loop is "interesting" for purposes
691 // of improving register allocation (= is inner, and does
692 // not contain a call)
693 func (s *regAllocState) loopForBlock(b *Block) *loop {
694 loop := s.loopnest.b2l[b.ID]
696 // Minor for-the-time-being optimization: nothing happens
697 // unless a loop is both inner and call-free, therefore
698 // don't bother with other loops.
699 if loop != nil && (loop.containsCall || !loop.isInner) {
705 func (s *regAllocState) regalloc(f *Func) {
706 liveSet := f.newSparseSet(f.NumValues())
707 defer f.retSparseSet(liveSet)
708 var oldSched []*Value
710 var phiRegs []register
714 var nSpills int // # of spills remaining
715 var nSpillsInner int // # of spills remaining in inner loops
716 var nSpillsSunk int // # of sunk spills remaining
717 var nSpillsChanged int // # of sunk spills lost because of register use change
718 var nSpillsSunkUnused int // # of spills not sunk because they were removed completely
719 var nSpillsNotSunkLateUse int // # of spills not sunk because of very late use (in shuffle)
721 // Data structure used for computing desired registers.
722 var desired desiredState
724 // Desired registers for inputs & outputs for each instruction in the block.
726 out [4]register // desired output registers
727 in [3][4]register // desired input registers (for inputs 0,1, and 2)
731 if f.Entry != f.Blocks[0] {
732 f.Fatalf("entry block must be first")
735 // Get loop nest so that spills in inner loops can be
736 // tracked. When the last block of a loop is processed,
737 // attempt to move spills out of the loop.
738 s.loopnest.findExits()
740 // Spills are moved from one block's slice of values to another's.
741 // This confuses register allocation if it occurs before it is
742 // complete, so candidates are recorded, then rechecked and
743 // moved after all allocation (register and stack) is complete.
744 // Because movement is only within a stack slot's lifetime, it
745 // is safe to do this.
746 var toSink []spillToSink
747 // Will be used to figure out live inputs to exit blocks of inner loops.
748 entryCandidates := newSparseMap(f.NumValues())
750 for _, b := range f.Blocks {
752 loop := s.loopForBlock(b)
754 // Initialize liveSet and uses fields for this block.
755 // Walk backwards through the block doing liveness analysis.
757 for _, e := range s.live[b.ID] {
758 s.addUse(e.ID, int32(len(b.Values))+e.dist, e.line) // pseudo-uses from beyond end of block
761 if v := b.Control; v != nil && s.values[v.ID].needReg {
762 s.addUse(v.ID, int32(len(b.Values)), b.Line) // pseudo-use by control value
765 for i := len(b.Values) - 1; i >= 0; i-- {
769 // Remove v from the live set, but don't add
770 // any inputs. This is the state the len(b.Preds)>1
771 // case below desires; it wants to process phis specially.
774 for _, a := range v.Args {
775 if !s.values[a.ID].needReg {
778 s.addUse(a.ID, int32(i), v.Line)
782 if s.f.pass.debug > regDebug {
783 fmt.Printf("uses for %s:%s\n", s.f.Name, b)
784 for i := range s.values {
790 fmt.Printf(" v%d:", i)
792 fmt.Printf(" %d", u.dist)
799 // Make a copy of the block schedule so we can generate a new one in place.
800 // We make a separate copy for phis and regular values.
802 for _, v := range b.Values {
808 phis = append(phis[:0], b.Values[:nphi]...)
809 oldSched = append(oldSched[:0], b.Values[nphi:]...)
810 b.Values = b.Values[:0]
812 // Initialize start state of block.
814 // Regalloc state is empty to start.
816 f.Fatalf("phis in entry block")
818 } else if len(b.Preds) == 1 {
819 // Start regalloc state with the end state of the previous block.
820 s.setState(s.endRegs[b.Preds[0].b.ID])
822 f.Fatalf("phis in single-predecessor block")
824 // Drop any values which are no longer live.
825 // This may happen because at the end of p, a value may be
826 // live but only used by some other successor of p.
827 for r := register(0); r < s.numRegs; r++ {
829 if v != nil && !liveSet.contains(v.ID) {
834 // This is the complicated case. We have more than one predecessor,
835 // which means we may have Phi ops.
837 // Copy phi ops into new schedule.
838 b.Values = append(b.Values, phis...)
840 // Start with the final register state of the primary predecessor
841 idx := s.primary[b.ID]
843 f.Fatalf("block with no primary predecessor %s", b)
846 s.setState(s.endRegs[p.ID])
848 if s.f.pass.debug > regDebug {
849 fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
850 for _, x := range s.endRegs[p.ID] {
851 fmt.Printf(" %s: orig:%s cache:%s\n", s.registers[x.r].Name(), x.v, x.c)
855 // Decide on registers for phi ops. Use the registers determined
856 // by the primary predecessor if we can.
857 // TODO: pick best of (already processed) predecessors?
858 // Majority vote? Deepest nesting level?
859 phiRegs = phiRegs[:0]
861 for _, v := range phis {
862 if !s.values[v.ID].needReg {
863 phiRegs = append(phiRegs, noRegister)
867 // Some instructions target not-allocatable registers.
868 // They're not suitable for further (phi-function) allocation.
869 m := s.values[a.ID].regs &^ phiUsed & s.allocatable
872 phiUsed |= regMask(1) << r
873 phiRegs = append(phiRegs, r)
875 phiRegs = append(phiRegs, noRegister)
879 // Second pass - deallocate any phi inputs which are now dead.
880 for i, v := range phis {
881 if !s.values[v.ID].needReg {
885 if !liveSet.contains(a.ID) {
886 // Input is dead beyond the phi, deallocate
887 // anywhere else it might live.
888 s.freeRegs(s.values[a.ID].regs)
890 // Input is still live.
891 // Try to move it around before kicking out, if there is a free register.
892 // We generate a Copy in the predecessor block and record it. It will be
893 // deleted if never used.
898 // Pick a free register. At this point some registers used in the predecessor
899 // block may have been deallocated. Those are the ones used for Phis. Exclude
900 // them (and they are not going to be helpful anyway).
901 m := s.compatRegs(a.Type) &^ s.used &^ phiUsed
902 if m != 0 && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 {
904 c := p.NewValue1(a.Line, OpCopy, a.Type, s.regs[r].c)
906 if s.f.pass.debug > regDebug {
907 fmt.Printf("copy %s to %s : %s\n", a, c, s.registers[r2].Name())
910 s.assignReg(r2, a, c)
911 s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c})
917 // Third pass - pick registers for phis whose inputs
918 // were not in a register.
919 for i, v := range phis {
920 if !s.values[v.ID].needReg {
923 if phiRegs[i] != noRegister {
926 if s.f.Config.use387 && v.Type.IsFloat() {
927 continue // 387 can't handle floats in registers between blocks
929 m := s.compatRegs(v.Type) &^ phiUsed &^ s.used
933 phiUsed |= regMask(1) << r
937 // Set registers for phis. Add phi spill code.
938 for i, v := range phis {
939 if !s.values[v.ID].needReg {
945 // Spills will be inserted in all the predecessors below.
946 s.values[v.ID].spill = v // v starts life spilled
947 s.values[v.ID].spillUsed = true // use is guaranteed
950 // register-based phi
952 // Spill the phi in case we need to restore it later.
953 spill := b.NewValue1(v.Line, OpStoreReg, v.Type, v)
955 s.values[v.ID].spill = spill
956 s.values[v.ID].spillUsed = false
958 loop.spills = append(loop.spills, v)
964 // Save the starting state for use by merge edges.
965 var regList []startReg
966 for r := register(0); r < s.numRegs; r++ {
971 if phiUsed>>r&1 != 0 {
972 // Skip registers that phis used, we'll handle those
973 // specially during merge edge processing.
976 regList = append(regList, startReg{r, v.ID, s.values[v.ID].uses.line})
978 s.startRegs[b.ID] = regList
980 if s.f.pass.debug > regDebug {
981 fmt.Printf("after phis\n")
982 for _, x := range s.startRegs[b.ID] {
983 fmt.Printf(" %s: v%d\n", s.registers[x.r].Name(), x.vid)
988 // Allocate space to record the desired registers for each value.
990 for i := 0; i < len(oldSched); i++ {
991 dinfo = append(dinfo, dentry{})
994 // Load static desired register info at the end of the block.
995 desired.copy(&s.desired[b.ID])
997 // Check actual assigned registers at the start of the next block(s).
998 // Dynamically assigned registers will trump the static
999 // desired registers computed during liveness analysis.
1000 // Note that we do this phase after startRegs is set above, so that
1001 // we get the right behavior for a block which branches to itself.
1002 for _, e := range b.Succs {
1004 // TODO: prioritize likely successor?
1005 for _, x := range s.startRegs[succ.ID] {
1006 desired.add(x.vid, x.r)
1008 // Process phi ops in succ.
1010 for _, v := range succ.Values {
1014 if !s.values[v.ID].needReg {
1017 rp, ok := s.f.getHome(v.ID).(*Register)
1021 desired.add(v.Args[pidx].ID, register(rp.num))
1024 // Walk values backwards computing desired register info.
1025 // See computeLive for more comments.
1026 for i := len(oldSched) - 1; i >= 0; i-- {
1028 prefs := desired.remove(v.ID)
1029 desired.clobber(opcodeTable[v.Op].reg.clobbers)
1030 for _, j := range opcodeTable[v.Op].reg.inputs {
1031 if countRegs(j.regs) != 1 {
1034 desired.clobber(j.regs)
1035 desired.add(v.Args[j.idx].ID, pickReg(j.regs))
1037 if opcodeTable[v.Op].resultInArg0 {
1038 if opcodeTable[v.Op].commutative {
1039 desired.addList(v.Args[1].ID, prefs)
1041 desired.addList(v.Args[0].ID, prefs)
1043 // Save desired registers for this value.
1044 dinfo[i].out = prefs
1045 for j, a := range v.Args {
1046 if j >= len(dinfo[i].in) {
1049 dinfo[i].in[j] = desired.get(a.ID)
1053 // Process all the non-phi values.
1054 for idx, v := range oldSched {
1055 if s.f.pass.debug > regDebug {
1056 fmt.Printf(" processing %s\n", v.LongString())
1058 regspec := opcodeTable[v.Op].reg
1060 f.Fatalf("phi %s not at start of block", v)
1063 s.assignReg(s.SPReg, v, v)
1064 b.Values = append(b.Values, v)
1069 s.assignReg(s.SBReg, v, v)
1070 b.Values = append(b.Values, v)
1074 if v.Op == OpSelect0 || v.Op == OpSelect1 {
1075 if s.values[v.ID].needReg {
1077 if v.Op == OpSelect1 {
1080 s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
1082 b.Values = append(b.Values, v)
1086 if v.Op == OpGetG && s.f.Config.hasGReg {
1087 // use hardware g register
1088 if s.regs[s.GReg].v != nil {
1089 s.freeReg(s.GReg) // kick out the old value
1091 s.assignReg(s.GReg, v, v)
1092 b.Values = append(b.Values, v)
1097 // Args are "pre-spilled" values. We don't allocate
1098 // any register here. We just set up the spill pointer to
1099 // point at itself and any later user will restore it to use it.
1100 s.values[v.ID].spill = v
1101 s.values[v.ID].spillUsed = true // use is guaranteed
1102 b.Values = append(b.Values, v)
1106 if v.Op == OpKeepAlive {
1107 // Make sure the argument to v is still live here.
1109 vi := &s.values[v.Args[0].ID]
1111 // Use the spill location.
1112 v.SetArg(0, vi.spill)
1114 // No need to keep unspilled values live.
1115 // These are typically rematerializeable constants like nil,
1116 // or values of a variable that were modified since the last call.
1118 v.SetArgs1(v.Args[1])
1120 b.Values = append(b.Values, v)
1123 if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 {
1124 // No register allocation required (or none specified yet)
1125 s.freeRegs(regspec.clobbers)
1126 b.Values = append(b.Values, v)
1131 if s.values[v.ID].rematerializeable {
1132 // Value is rematerializeable, don't issue it here.
1133 // It will get issued just before each use (see
1134 // allocValueToReg).
1135 for _, a := range v.Args {
1142 if s.f.pass.debug > regDebug {
1143 fmt.Printf("value %s\n", v.LongString())
1145 for _, r := range dinfo[idx].out {
1146 if r != noRegister {
1147 fmt.Printf(" %s", s.registers[r].Name())
1151 for i := 0; i < len(v.Args) && i < 3; i++ {
1152 fmt.Printf(" in%d:", i)
1153 for _, r := range dinfo[idx].in[i] {
1154 if r != noRegister {
1155 fmt.Printf(" %s", s.registers[r].Name())
1162 // Move arguments to registers. Process in an ordering defined
1163 // by the register specification (most constrained first).
1164 args = append(args[:0], v.Args...)
1165 for _, i := range regspec.inputs {
1167 if mask&s.values[args[i.idx].ID].regs == 0 {
1168 // Need a new register for the input.
1169 mask &= s.allocatable
1171 // Used desired register if available.
1173 for _, r := range dinfo[idx].in[i.idx] {
1174 if r != noRegister && (mask&^s.used)>>r&1 != 0 {
1175 // Desired register is allowed and unused.
1176 mask = regMask(1) << r
1181 // Avoid registers we're saving for other values.
1182 if mask&^desired.avoid != 0 {
1183 mask &^= desired.avoid
1186 args[i.idx] = s.allocValToReg(args[i.idx], mask, true, v.Line)
1189 // If the output clobbers the input register, make sure we have
1190 // at least two copies of the input register so we don't
1191 // have to reload the value from the spill location.
1192 if opcodeTable[v.Op].resultInArg0 {
1194 if !s.liveAfterCurrentInstruction(v.Args[0]) {
1195 // arg0 is dead. We can clobber its register.
1198 if s.values[v.Args[0].ID].rematerializeable {
1199 // We can rematerialize the input, don't worry about clobbering it.
1202 if countRegs(s.values[v.Args[0].ID].regs) >= 2 {
1203 // we have at least 2 copies of arg0. We can afford to clobber one.
1206 if opcodeTable[v.Op].commutative {
1207 if !s.liveAfterCurrentInstruction(v.Args[1]) {
1208 args[0], args[1] = args[1], args[0]
1211 if s.values[v.Args[1].ID].rematerializeable {
1212 args[0], args[1] = args[1], args[0]
1215 if countRegs(s.values[v.Args[1].ID].regs) >= 2 {
1216 args[0], args[1] = args[1], args[0]
1221 // We can't overwrite arg0 (or arg1, if commutative). So we
1222 // need to make a copy of an input so we have a register we can modify.
1224 // Possible new registers to copy into.
1225 m = s.compatRegs(v.Args[0].Type) &^ s.used
1227 // No free registers. In this case we'll just clobber
1228 // an input and future uses of that input must use a restore.
1229 // TODO(khr): We should really do this like allocReg does it,
1230 // spilling the value with the most distant next use.
1234 // Try to move an input to the desired output.
1235 for _, r := range dinfo[idx].out {
1236 if r != noRegister && m>>r&1 != 0 {
1238 args[0] = s.allocValToReg(v.Args[0], m, true, v.Line)
1239 // Note: we update args[0] so the instruction will
1240 // use the register copy we just made.
1244 // Try to copy input to its desired location & use its old
1245 // location as the result register.
1246 for _, r := range dinfo[idx].in[0] {
1247 if r != noRegister && m>>r&1 != 0 {
1249 c := s.allocValToReg(v.Args[0], m, true, v.Line)
1251 // Note: no update to args[0] so the instruction will
1252 // use the original copy.
1256 if opcodeTable[v.Op].commutative {
1257 for _, r := range dinfo[idx].in[1] {
1258 if r != noRegister && m>>r&1 != 0 {
1260 c := s.allocValToReg(v.Args[1], m, true, v.Line)
1262 args[0], args[1] = args[1], args[0]
1267 // Avoid future fixed uses if we can.
1268 if m&^desired.avoid != 0 {
1271 // Save input 0 to a new register so we can clobber it.
1272 c := s.allocValToReg(v.Args[0], m, true, v.Line)
1277 // Now that all args are in regs, we're ready to issue the value itself.
1278 // Before we pick a register for the output value, allow input registers
1279 // to be deallocated. We do this here so that the output can use the
1280 // same register as a dying input.
1281 if !opcodeTable[v.Op].resultNotInArgs {
1282 s.tmpused = s.nospill
1284 s.advanceUses(v) // frees any registers holding args that are no longer live
1287 // Dump any registers which will be clobbered
1288 s.freeRegs(regspec.clobbers)
1289 s.tmpused |= regspec.clobbers
1291 // Pick registers for outputs.
1293 outRegs := [2]register{noRegister, noRegister}
1295 for _, out := range regspec.outputs {
1296 mask := out.regs & s.allocatable &^ used
1300 if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
1301 if !opcodeTable[v.Op].commutative {
1302 // Output must use the same register as input 0.
1303 r := register(s.f.getHome(args[0].ID).(*Register).num)
1304 mask = regMask(1) << r
1306 // Output must use the same register as input 0 or 1.
1307 r0 := register(s.f.getHome(args[0].ID).(*Register).num)
1308 r1 := register(s.f.getHome(args[1].ID).(*Register).num)
1309 // Check r0 and r1 for desired output register.
1311 for _, r := range dinfo[idx].out {
1312 if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 {
1313 mask = regMask(1) << r
1316 args[0], args[1] = args[1], args[0]
1322 // Neither are desired, pick r0.
1323 mask = regMask(1) << r0
1327 for _, r := range dinfo[idx].out {
1328 if r != noRegister && (mask&^s.used)>>r&1 != 0 {
1329 // Desired register is allowed and unused.
1330 mask = regMask(1) << r
1334 // Avoid registers we're saving for other values.
1335 if mask&^desired.avoid != 0 {
1336 mask &^= desired.avoid
1338 r := s.allocReg(mask, v)
1339 outRegs[out.idx] = r
1340 used |= regMask(1) << r
1341 s.tmpused |= regMask(1) << r
1343 // Record register choices
1344 if v.Type.IsTuple() {
1346 if r := outRegs[0]; r != noRegister {
1347 outLocs[0] = &s.registers[r]
1349 if r := outRegs[1]; r != noRegister {
1350 outLocs[1] = &s.registers[r]
1352 s.f.setHome(v, outLocs)
1353 // Note that subsequent SelectX instructions will do the assignReg calls.
1355 if r := outRegs[0]; r != noRegister {
1356 s.assignReg(r, v, v)
1361 // deallocate dead args, if we have not done so
1362 if opcodeTable[v.Op].resultNotInArgs {
1364 s.advanceUses(v) // frees any registers holding args that are no longer live
1368 // Issue the Value itself.
1369 for i, a := range args {
1370 v.SetArg(i, a) // use register version of arguments
1372 b.Values = append(b.Values, v)
1374 // Issue a spill for this value. We issue spills unconditionally,
1375 // then at the end of regalloc delete the ones we never use.
1376 // TODO: schedule the spill at a point that dominates all restores.
1377 // The restore may be off in an unlikely branch somewhere and it
1378 // would be better to have the spill in that unlikely branch as well.
1383 // It would be good to have both spill and restore inside the IF.
1385 if s.values[v.ID].needReg {
1386 spill := b.NewValue1(v.Line, OpStoreReg, v.Type, v)
1388 s.values[v.ID].spill = spill
1389 s.values[v.ID].spillUsed = false
1391 loop.spills = append(loop.spills, v)
1398 // Load control value into reg.
1399 if v := b.Control; v != nil && s.values[v.ID].needReg {
1400 if s.f.pass.debug > regDebug {
1401 fmt.Printf(" processing control %s\n", v.LongString())
1403 // We assume that a control input can be passed in any
1404 // type-compatible register. If this turns out not to be true,
1405 // we'll need to introduce a regspec for a block's control value.
1406 b.Control = s.allocValToReg(v, s.compatRegs(v.Type), false, b.Line)
1411 // Remove this use from the uses list.
1412 vi := &s.values[v.ID]
1416 s.freeRegs(vi.regs) // value is dead
1418 u.next = s.freeUseRecords
1419 s.freeUseRecords = u
1422 // Spill any values that can't live across basic block boundaries.
1423 if s.f.Config.use387 {
1424 s.freeRegs(s.f.Config.fpRegMask)
1427 // If we are approaching a merge point and we are the primary
1428 // predecessor of it, find live values that we use soon after
1429 // the merge point and promote them to registers now.
1430 if len(b.Succs) == 1 {
1431 // For this to be worthwhile, the loop must have no calls in it.
1433 loop := s.loopnest.b2l[top.ID]
1434 if loop == nil || loop.header != top || loop.containsCall {
1438 // TODO: sort by distance, pick the closest ones?
1439 for _, live := range s.live[b.ID] {
1440 if live.dist >= unlikelyDistance {
1441 // Don't preload anything live after the loop.
1445 vi := &s.values[vid]
1449 if vi.rematerializeable {
1453 if s.f.Config.use387 && v.Type.IsFloat() {
1454 continue // 387 can't handle floats in registers between blocks
1456 m := s.compatRegs(v.Type) &^ s.used
1457 if m&^desired.avoid != 0 {
1461 s.allocValToReg(v, m, false, b.Line)
1468 // Save end-of-block register state.
1469 // First count how many, this cuts allocations in half.
1471 for r := register(0); r < s.numRegs; r++ {
1478 regList := make([]endReg, 0, k)
1479 for r := register(0); r < s.numRegs; r++ {
1484 regList = append(regList, endReg{r, v, s.regs[r].c})
1486 s.endRegs[b.ID] = regList
1490 for _, x := range s.live[b.ID] {
1493 for r := register(0); r < s.numRegs; r++ {
1498 if !liveSet.contains(v.ID) {
1499 s.f.Fatalf("val %s is in reg but not live at end of %s", v, b)
1504 // If a value is live at the end of the block and
1505 // isn't in a register, remember that its spill location
1506 // is live. We need to remember this information so that
1507 // the liveness analysis in stackalloc is correct.
1508 for _, e := range s.live[b.ID] {
1509 if s.values[e.ID].regs != 0 {
1510 // in a register, we'll use that source for the merge.
1513 spill := s.values[e.ID].spill
1515 // rematerializeable values will have spill==nil.
1518 s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID)
1519 s.values[e.ID].spillUsed = true
1522 // Keep track of values that are spilled in the loop, but whose spill
1523 // is not used in the loop. It may be possible to move ("sink") the
1524 // spill out of the loop into one or more exit blocks.
1526 loop.scratch++ // increment count of blocks in this loop that have been processed
1527 if loop.scratch == loop.nBlocks { // just processed last block of loop, if it is an inner loop.
1528 // This check is redundant with code at the top of the loop.
1529 // This is definitive; the one at the top of the loop is an optimization.
1530 if loop.isInner && // Common case, easier, most likely to be profitable
1531 !loop.containsCall && // Calls force spills, also lead to puzzling spill info.
1532 len(loop.exits) <= 32 { // Almost no inner loops have more than 32 exits,
1533 // and this allows use of a bitvector and a sparseMap.
1535 // TODO: exit calculation is messed up for non-inner loops
1536 // because of multilevel exits that are not part of the "exit"
1539 // Compute the set of spill-movement candidates live at entry to exit blocks.
1540 // isLoopSpillCandidate filters for
1541 // (1) defined in appropriate loop
1542 // (2) needs a register
1543 // (3) spill not already used (in the loop)
1544 // Condition (3) === "in a register at all loop exits"
1546 entryCandidates.clear()
1548 for whichExit, ss := range loop.exits {
1549 // Start with live at end.
1550 for _, li := range s.live[ss.ID] {
1551 if s.isLoopSpillCandidate(loop, s.orig[li.ID]) {
1552 // s.live contains original IDs, use s.orig above to map back to *Value
1553 entryCandidates.setBit(li.ID, uint(whichExit))
1556 // Control can also be live.
1557 if ss.Control != nil && s.orig[ss.Control.ID] != nil && s.isLoopSpillCandidate(loop, s.orig[ss.Control.ID]) {
1558 entryCandidates.setBit(s.orig[ss.Control.ID].ID, uint(whichExit))
1560 // Walk backwards, filling in locally live values, removing those defined.
1561 for i := len(ss.Values) - 1; i >= 0; i-- {
1563 vorig := s.orig[v.ID]
1565 entryCandidates.remove(vorig.ID) // Cannot be an issue, only keeps the sets smaller.
1567 for _, a := range v.Args {
1568 aorig := s.orig[a.ID]
1569 if aorig != nil && s.isLoopSpillCandidate(loop, aorig) {
1570 entryCandidates.setBit(aorig.ID, uint(whichExit))
1576 for _, e := range loop.spills {
1577 whichblocks := entryCandidates.get(e.ID)
1578 oldSpill := s.values[e.ID].spill
1579 if whichblocks != 0 && whichblocks != -1 { // -1 = not in map.
1580 toSink = append(toSink, spillToSink{spill: oldSpill, dests: whichblocks})
1584 } // loop is inner etc
1585 loop.scratch = 0 // Don't leave a mess, just in case.
1587 } // if scratch == nBlocks
1588 } // if loop is not nil
1590 // Clear any final uses.
1591 // All that is left should be the pseudo-uses added for values which
1592 // are live at the end of b.
1593 for _, e := range s.live[b.ID] {
1594 u := s.values[e.ID].uses
1596 f.Fatalf("live at end, no uses v%d", e.ID)
1599 f.Fatalf("live at end, too many uses v%d", e.ID)
1601 s.values[e.ID].uses = nil
1602 u.next = s.freeUseRecords
1603 s.freeUseRecords = u
1607 // Erase any spills we never used
1608 for i := range s.values {
1611 if s.f.pass.debug > logSpills && vi.spill.Op != OpArg {
1612 s.f.Config.Warnl(vi.spill.Line, "spilled value at %v remains", vi.spill)
1618 // Constants, SP, SB, ...
1621 loop := s.loopForBlock(spill.Block)
1626 spill.Args[0].Uses--
1631 for _, b := range f.Blocks {
1633 for _, v := range b.Values {
1634 if v.Op == OpInvalid {
1640 b.Values = b.Values[:i]
1641 // TODO: zero b.Values[i:], recycle Values
1642 // Not important now because this is the last phase that manipulates Values
1645 // Must clear these out before any potential recycling, though that's
1646 // not currently implemented.
1647 for i, ts := range toSink {
1649 if vsp.Op == OpInvalid { // This spill was completely eliminated
1650 toSink[i].spill = nil
1654 // Anything that didn't get a register gets a stack location here.
1655 // (StoreReg, stack-based phis, inputs, ...)
1656 stacklive := stackalloc(s.f, s.spillLive)
1658 // Fix up all merge edges.
1659 s.shuffle(stacklive)
1661 // Insert moved spills (that have not been marked invalid above)
1662 // at start of appropriate block and remove the originals from their
1663 // location within loops. Notice that this can break SSA form;
1664 // if a spill is sunk to multiple exits, there will be no phi for that
1665 // spill at a join point downstream of those two exits, though the
1666 // two spills will target the same stack slot. Notice also that this
1667 // takes place after stack allocation, so the stack allocator does
1668 // not need to process these malformed flow graphs.
1670 for _, ts := range toSink {
1672 if vsp == nil { // This spill was completely eliminated
1676 e := ts.spilledValue()
1677 if s.values[e.ID].spillUsedShuffle {
1678 nSpillsNotSunkLateUse++
1682 // move spills to a better (outside of loop) block.
1683 // This would be costly if it occurred very often, but it doesn't.
1685 loop := s.loopnest.b2l[b.ID]
1688 // Pre-check to be sure that spilled value is still in expected register on all exits where live.
1689 check_val_still_in_reg:
1690 for i := uint(0); i < 32 && dests != 0; i++ {
1692 if dests&(1<<i) == 0 {
1697 if len(d.Preds) > 1 {
1698 panic("Should be impossible given critical edges removed")
1700 p := d.Preds[0].b // block in loop exiting to d.
1702 endregs := s.endRegs[p.ID]
1703 for _, regrec := range endregs {
1704 if regrec.v == e && regrec.r != noRegister && regrec.c == e { // TODO: regrec.c != e implies different spill possible.
1705 continue check_val_still_in_reg
1708 // If here, the register assignment was lost down at least one exit and it can't be sunk
1709 if s.f.pass.debug > moveSpills {
1710 s.f.Config.Warnl(e.Line, "lost register assignment for spill %v in %v at exit %v to %v",
1719 // don't update nSpills, since spill is only moved, and if it is duplicated, the spills-on-a-path is not increased.
1723 // remove vsp from b.Values
1725 for _, w := range b.Values {
1732 b.Values = b.Values[:i]
1735 for i := uint(0); i < 32 && dests != 0; i++ {
1737 if dests&(1<<i) == 0 {
1744 vspnew := vsp // reuse original for first sunk spill, saves tracking down and renaming uses
1745 if !first { // any sunk spills after first must make a copy
1746 vspnew = d.NewValue1(e.Line, OpStoreReg, e.Type, e)
1747 f.setHome(vspnew, f.getHome(vsp.ID)) // copy stack home
1748 if s.f.pass.debug > moveSpills {
1749 s.f.Config.Warnl(e.Line, "copied spill %v in %v for %v to %v in %v",
1750 vsp, b, e, vspnew, d)
1755 d.Values = append(d.Values, vspnew)
1756 if s.f.pass.debug > moveSpills {
1757 s.f.Config.Warnl(e.Line, "moved spill %v in %v for %v to %v in %v",
1758 vsp, b, e, vspnew, d)
1762 // shuffle vspnew to the beginning of its block
1763 copy(d.Values[1:], d.Values[0:len(d.Values)-1])
1764 d.Values[0] = vspnew
1769 // Erase any copies we never used.
1770 // Also, an unused copy might be the only use of another copy,
1771 // so continue erasing until we reach a fixed point.
1774 for c, used := range s.copies {
1775 if !used && c.Uses == 0 {
1776 if s.f.pass.debug > regDebug {
1777 fmt.Printf("delete copied value %s\n", c.LongString())
1790 for _, b := range f.Blocks {
1792 for _, v := range b.Values {
1793 if v.Op == OpInvalid {
1799 b.Values = b.Values[:i]
1802 if f.pass.stats > 0 {
1803 f.LogStat("spills_info",
1804 nSpills, "spills", nSpillsInner, "inner_spills_remaining", nSpillsSunk, "inner_spills_sunk", nSpillsSunkUnused, "inner_spills_unused", nSpillsNotSunkLateUse, "inner_spills_shuffled", nSpillsChanged, "inner_spills_changed")
1808 // isLoopSpillCandidate indicates whether the spill for v satisfies preliminary
1809 // spill-sinking conditions just after the last block of loop has been processed.
1811 // v needs a register.
1812 // v's spill is not (YET) used.
1813 // v's definition is within loop.
1814 // The spill may be used in the future, either by an outright use
1815 // in the code, or by shuffling code inserted after stack allocation.
1816 // Outright uses cause sinking; shuffling (within the loop) inhibits it.
1817 func (s *regAllocState) isLoopSpillCandidate(loop *loop, v *Value) bool {
1818 return s.values[v.ID].needReg && !s.values[v.ID].spillUsed && s.loopnest.b2l[v.Block.ID] == loop
1821 // lateSpillUse notes a late (after stack allocation) use of the spill of value with ID vid.
1822 // This will inhibit spill sinking.
1823 func (s *regAllocState) lateSpillUse(vid ID) {
1824 // TODO investigate why this is necessary.
1825 // It appears that an outside-the-loop use of
1826 // an otherwise sinkable spill makes the spill
1827 // a candidate for shuffling, when it would not
1828 // otherwise have been the case (spillUsed was not
1829 // true when isLoopSpillCandidate was called, yet
1830 // it was shuffled). Such shuffling cuts the amount
1831 // of spill sinking by more than half (in make.bash)
1832 s.values[vid].spillUsedShuffle = true
1835 // shuffle fixes up all the merge edges (those going into blocks of indegree > 1).
1836 func (s *regAllocState) shuffle(stacklive [][]ID) {
1839 e.cache = map[ID][]*Value{}
1840 e.contents = map[Location]contentRecord{}
1841 if s.f.pass.debug > regDebug {
1842 fmt.Printf("shuffle %s\n", s.f.Name)
1843 fmt.Println(s.f.String())
1846 for _, b := range s.f.Blocks {
1847 if len(b.Preds) <= 1 {
1851 for i, edge := range b.Preds {
1854 e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID])
1860 type edgeState struct {
1862 p, b *Block // edge goes from p->b.
1864 // for each pre-regalloc value, a list of equivalent cached values
1865 cache map[ID][]*Value
1866 cachedVals []ID // (superset of) keys of the above map, for deterministic iteration
1868 // map from location to the value it contains
1869 contents map[Location]contentRecord
1871 // desired destination locations
1872 destinations []dstRecord
1875 usedRegs regMask // registers currently holding something
1876 uniqueRegs regMask // registers holding the only copy of a value
1877 finalRegs regMask // registers holding final target
1880 type contentRecord struct {
1881 vid ID // pre-regalloc value
1882 c *Value // cached value
1883 final bool // this is a satisfied destination
1884 line int32 // line number of use of the value
1887 type dstRecord struct {
1888 loc Location // register or stack slot
1889 vid ID // pre-regalloc value it should contain
1890 splice **Value // place to store reference to the generating instruction
1891 line int32 // line number of use of this location
1894 // setup initializes the edge state for shuffling.
1895 func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) {
1896 if e.s.f.pass.debug > regDebug {
1897 fmt.Printf("edge %s->%s\n", e.p, e.b)
1901 for _, vid := range e.cachedVals {
1902 delete(e.cache, vid)
1904 e.cachedVals = e.cachedVals[:0]
1905 for k := range e.contents {
1906 delete(e.contents, k)
1912 // Live registers can be sources.
1913 for _, x := range srcReg {
1914 e.set(&e.s.registers[x.r], x.v.ID, x.c, false, 0) // don't care the line number of the source
1916 // So can all of the spill locations.
1917 for _, spillID := range stacklive {
1918 v := e.s.orig[spillID]
1919 spill := e.s.values[v.ID].spill
1920 e.set(e.s.f.getHome(spillID), v.ID, spill, false, 0) // don't care the line number of the source
1923 // Figure out all the destinations we need.
1924 dsts := e.destinations[:0]
1925 for _, x := range dstReg {
1926 dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.vid, nil, x.line})
1928 // Phis need their args to end up in a specific location.
1929 for _, v := range e.b.Values {
1933 loc := e.s.f.getHome(v.ID)
1937 dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Line})
1939 e.destinations = dsts
1941 if e.s.f.pass.debug > regDebug {
1942 for _, vid := range e.cachedVals {
1944 for _, c := range a {
1945 fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID).Name(), vid, c)
1948 for _, d := range e.destinations {
1949 fmt.Printf("dst %s: v%d\n", d.loc.Name(), d.vid)
1954 // process generates code to move all the values to the right destination locations.
1955 func (e *edgeState) process() {
1956 dsts := e.destinations
1958 // Process the destinations until they are all satisfied.
1961 for _, d := range dsts {
1962 if !e.processDest(d.loc, d.vid, d.splice, d.line) {
1963 // Failed - save for next iteration.
1969 // Made some progress. Go around again.
1972 // Append any extras destinations we generated.
1973 dsts = append(dsts, e.extra...)
1974 e.extra = e.extra[:0]
1978 // We made no progress. That means that any
1979 // remaining unsatisfied moves are in simple cycles.
1980 // For example, A -> B -> C -> D -> A.
1987 // To break the cycle, we pick an unused register, say R,
1988 // and put a copy of B there.
1993 // D <---- C <---- R=copyofB
1994 // When we resume the outer loop, the A->B move can now proceed,
1995 // and eventually the whole cycle completes.
1997 // Copy any cycle location to a temp register. This duplicates
1998 // one of the cycle entries, allowing the just duplicated value
1999 // to be overwritten and the cycle to proceed.
2002 vid := e.contents[loc].vid
2003 c := e.contents[loc].c
2004 r := e.findRegFor(c.Type)
2005 if e.s.f.pass.debug > regDebug {
2006 fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc.Name(), c)
2008 if _, isReg := loc.(*Register); isReg {
2009 c = e.p.NewValue1(d.line, OpCopy, c.Type, c)
2011 e.s.lateSpillUse(vid)
2012 c = e.p.NewValue1(d.line, OpLoadReg, c.Type, c)
2014 e.set(r, vid, c, false, d.line)
2018 // processDest generates code to put value vid into location loc. Returns true
2019 // if progress was made.
2020 func (e *edgeState) processDest(loc Location, vid ID, splice **Value, line int32) bool {
2021 occupant := e.contents[loc]
2022 if occupant.vid == vid {
2023 // Value is already in the correct place.
2024 e.contents[loc] = contentRecord{vid, occupant.c, true, line}
2027 *splice = occupant.c
2029 if occupant.c.Op == OpStoreReg {
2030 e.s.lateSpillUse(vid)
2033 // Note: if splice==nil then c will appear dead. This is
2034 // non-SSA formed code, so be careful after this pass not to run
2035 // deadcode elimination.
2036 if _, ok := e.s.copies[occupant.c]; ok {
2037 // The copy at occupant.c was used to avoid spill.
2038 e.s.copies[occupant.c] = true
2043 // Check if we're allowed to clobber the destination location.
2044 if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable {
2045 // We can't overwrite the last copy
2046 // of a value that needs to survive.
2050 // Copy from a source of v, register preferred.
2054 if e.s.f.pass.debug > regDebug {
2055 fmt.Printf("moving v%d to %s\n", vid, loc.Name())
2056 fmt.Printf("sources of v%d:", vid)
2058 for _, w := range e.cache[vid] {
2059 h := e.s.f.getHome(w.ID)
2060 if e.s.f.pass.debug > regDebug {
2061 fmt.Printf(" %s:%s", h.Name(), w)
2063 _, isreg := h.(*Register)
2064 if src == nil || isreg {
2069 if e.s.f.pass.debug > regDebug {
2071 fmt.Printf(" [use %s]\n", src.Name())
2073 fmt.Printf(" [no source]\n")
2076 _, dstReg := loc.(*Register)
2079 if !e.s.values[vid].rematerializeable {
2080 e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString())
2085 // Rematerialize into stack slot. Need a free
2086 // register to accomplish this.
2087 e.erase(loc) // see pre-clobber comment below
2088 r := e.findRegFor(v.Type)
2090 e.set(r, vid, x, false, line)
2091 // Make sure we spill with the size of the slot, not the
2092 // size of x (which might be wider due to our dropping
2093 // of narrowing conversions).
2094 x = e.p.NewValue1(line, OpStoreReg, loc.(LocalSlot).Type, x)
2097 // Emit move from src to dst.
2098 _, srcReg := src.(*Register)
2101 x = e.p.NewValue1(line, OpCopy, c.Type, c)
2103 x = e.p.NewValue1(line, OpStoreReg, loc.(LocalSlot).Type, c)
2107 e.s.lateSpillUse(vid)
2108 x = e.p.NewValue1(line, OpLoadReg, c.Type, c)
2110 // mem->mem. Use temp register.
2112 // Pre-clobber destination. This avoids the
2113 // following situation:
2114 // - v is currently held in R0 and stacktmp0.
2115 // - We want to copy stacktmp1 to stacktmp0.
2116 // - We choose R0 as the temporary register.
2117 // During the copy, both R0 and stacktmp0 are
2118 // clobbered, losing both copies of v. Oops!
2119 // Erasing the destination early means R0 will not
2120 // be chosen as the temp register, as it will then
2121 // be the last copy of v.
2124 r := e.findRegFor(c.Type)
2125 e.s.lateSpillUse(vid)
2126 t := e.p.NewValue1(line, OpLoadReg, c.Type, c)
2127 e.set(r, vid, t, false, line)
2128 x = e.p.NewValue1(line, OpStoreReg, loc.(LocalSlot).Type, t)
2132 e.set(loc, vid, x, true, line)
2141 // set changes the contents of location loc to hold the given value and its cached representative.
2142 func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, line int32) {
2143 e.s.f.setHome(c, loc)
2145 e.contents[loc] = contentRecord{vid, c, final, line}
2148 e.cachedVals = append(e.cachedVals, vid)
2152 if r, ok := loc.(*Register); ok {
2153 e.usedRegs |= regMask(1) << uint(r.num)
2155 e.finalRegs |= regMask(1) << uint(r.num)
2158 e.uniqueRegs |= regMask(1) << uint(r.num)
2161 if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
2162 e.uniqueRegs &^= regMask(1) << uint(t.num)
2166 if e.s.f.pass.debug > regDebug {
2167 fmt.Printf("%s\n", c.LongString())
2168 fmt.Printf("v%d now available in %s:%s\n", vid, loc.Name(), c)
2172 // erase removes any user of loc.
2173 func (e *edgeState) erase(loc Location) {
2174 cr := e.contents[loc]
2181 // Add a destination to move this value back into place.
2182 // Make sure it gets added to the tail of the destination queue
2183 // so we make progress on other moves first.
2184 e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.line})
2187 // Remove c from the list of cached values.
2189 for i, c := range a {
2190 if e.s.f.getHome(c.ID) == loc {
2191 if e.s.f.pass.debug > regDebug {
2192 fmt.Printf("v%d no longer available in %s:%s\n", vid, loc.Name(), c)
2194 a[i], a = a[len(a)-1], a[:len(a)-1]
2200 // Update register masks.
2201 if r, ok := loc.(*Register); ok {
2202 e.usedRegs &^= regMask(1) << uint(r.num)
2204 e.finalRegs &^= regMask(1) << uint(r.num)
2208 if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
2209 e.uniqueRegs |= regMask(1) << uint(r.num)
2214 // findRegFor finds a register we can use to make a temp copy of type typ.
2215 func (e *edgeState) findRegFor(typ Type) Location {
2216 // Which registers are possibilities.
2219 m = e.s.compatRegs(e.s.f.Config.fe.TypeFloat64())
2221 m = e.s.compatRegs(e.s.f.Config.fe.TypeInt64())
2224 // Pick a register. In priority order:
2225 // 1) an unused register
2226 // 2) a non-unique register not holding a final value
2227 // 3) a non-unique register
2228 x := m &^ e.usedRegs
2230 return &e.s.registers[pickReg(x)]
2232 x = m &^ e.uniqueRegs &^ e.finalRegs
2234 return &e.s.registers[pickReg(x)]
2236 x = m &^ e.uniqueRegs
2238 return &e.s.registers[pickReg(x)]
2241 // No register is available. Allocate a temp location to spill a register to.
2242 // The type of the slot is immaterial - it will not be live across
2243 // any safepoint. Just use a type big enough to hold any register.
2244 typ = e.s.f.Config.fe.TypeInt64()
2245 t := LocalSlot{e.s.f.Config.fe.Auto(typ), typ, 0}
2246 // TODO: reuse these slots.
2248 // Pick a register to spill.
2249 for _, vid := range e.cachedVals {
2251 for _, c := range a {
2252 if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m>>uint(r.num)&1 != 0 {
2253 x := e.p.NewValue1(c.Line, OpStoreReg, c.Type, c)
2254 e.set(t, vid, x, false, c.Line)
2255 if e.s.f.pass.debug > regDebug {
2256 fmt.Printf(" SPILL %s->%s %s\n", r.Name(), t.Name(), x.LongString())
2258 // r will now be overwritten by the caller. At some point
2259 // later, the newly saved value will be moved back to its
2260 // final destination in processDest.
2266 fmt.Printf("m:%d unique:%d final:%d\n", m, e.uniqueRegs, e.finalRegs)
2267 for _, vid := range e.cachedVals {
2269 for _, c := range a {
2270 fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID).Name())
2273 e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b)
2277 // rematerializeable reports whether the register allocator should recompute
2278 // a value instead of spilling/restoring it.
2279 func (v *Value) rematerializeable() bool {
2280 if !opcodeTable[v.Op].rematerializeable {
2283 for _, a := range v.Args {
2284 // SP and SB (generated by OpSP and OpSB) are always available.
2285 if a.Op != OpSP && a.Op != OpSB {
2292 type liveInfo struct {
2293 ID ID // ID of value
2294 dist int32 // # of instructions before next use
2295 line int32 // line number of next use
2298 // dblock contains information about desired & avoid registers at the end of a block.
2299 type dblock struct {
2300 prefers []desiredStateEntry
2304 // computeLive computes a map from block ID to a list of value IDs live at the end
2305 // of that block. Together with the value ID is a count of how many instructions
2306 // to the next use of that value. The resulting map is stored in s.live.
2307 // computeLive also computes the desired register information at the end of each block.
2308 // This desired register information is stored in s.desired.
2309 // TODO: this could be quadratic if lots of variables are live across lots of
2310 // basic blocks. Figure out a way to make this function (or, more precisely, the user
2311 // of this function) require only linear size & time.
2312 func (s *regAllocState) computeLive() {
2314 s.live = make([][]liveInfo, f.NumBlocks())
2315 s.desired = make([]desiredState, f.NumBlocks())
2318 live := newSparseMap(f.NumValues())
2319 t := newSparseMap(f.NumValues())
2321 // Keep track of which value we want in each register.
2322 var desired desiredState
2324 // Instead of iterating over f.Blocks, iterate over their postordering.
2325 // Liveness information flows backward, so starting at the end
2326 // increases the probability that we will stabilize quickly.
2327 // TODO: Do a better job yet. Here's one possibility:
2328 // Calculate the dominator tree and locate all strongly connected components.
2329 // If a value is live in one block of an SCC, it is live in all.
2330 // Walk the dominator tree from end to beginning, just once, treating SCC
2331 // components as single blocks, duplicated calculated liveness information
2332 // out to all of them.
2334 s.loopnest = f.loopnest()
2338 for _, b := range po {
2339 // Start with known live values at the end of the block.
2340 // Add len(b.Values) to adjust from end-of-block distance
2341 // to beginning-of-block distance.
2343 for _, e := range s.live[b.ID] {
2344 live.set(e.ID, e.dist+int32(len(b.Values)), e.line)
2347 // Mark control value as live
2348 if b.Control != nil && s.values[b.Control.ID].needReg {
2349 live.set(b.Control.ID, int32(len(b.Values)), b.Line)
2352 // Propagate backwards to the start of the block
2353 // Assumes Values have been scheduled.
2355 for i := len(b.Values) - 1; i >= 0; i-- {
2359 // save phi ops for later
2360 phis = append(phis, v)
2363 if opcodeTable[v.Op].call {
2364 c := live.contents()
2366 c[i].val += unlikelyDistance
2369 for _, a := range v.Args {
2370 if s.values[a.ID].needReg {
2371 live.set(a.ID, int32(i), v.Line)
2375 // Propagate desired registers backwards.
2376 desired.copy(&s.desired[b.ID])
2377 for i := len(b.Values) - 1; i >= 0; i-- {
2379 prefs := desired.remove(v.ID)
2381 // TODO: if v is a phi, save desired register for phi inputs.
2382 // For now, we just drop it and don't propagate
2383 // desired registers back though phi nodes.
2386 // Cancel desired registers if they get clobbered.
2387 desired.clobber(opcodeTable[v.Op].reg.clobbers)
2388 // Update desired registers if there are any fixed register inputs.
2389 for _, j := range opcodeTable[v.Op].reg.inputs {
2390 if countRegs(j.regs) != 1 {
2393 desired.clobber(j.regs)
2394 desired.add(v.Args[j.idx].ID, pickReg(j.regs))
2396 // Set desired register of input 0 if this is a 2-operand instruction.
2397 if opcodeTable[v.Op].resultInArg0 {
2398 if opcodeTable[v.Op].commutative {
2399 desired.addList(v.Args[1].ID, prefs)
2401 desired.addList(v.Args[0].ID, prefs)
2405 // For each predecessor of b, expand its list of live-at-end values.
2406 // invariant: live contains the values live at the start of b (excluding phi inputs)
2407 for i, e := range b.Preds {
2409 // Compute additional distance for the edge.
2410 // Note: delta must be at least 1 to distinguish the control
2411 // value use from the first user in a successor block.
2412 delta := int32(normalDistance)
2413 if len(p.Succs) == 2 {
2414 if p.Succs[0].b == b && p.Likely == BranchLikely ||
2415 p.Succs[1].b == b && p.Likely == BranchUnlikely {
2416 delta = likelyDistance
2418 if p.Succs[0].b == b && p.Likely == BranchUnlikely ||
2419 p.Succs[1].b == b && p.Likely == BranchLikely {
2420 delta = unlikelyDistance
2424 // Update any desired registers at the end of p.
2425 s.desired[p.ID].merge(&desired)
2427 // Start t off with the previously known live values at the end of p.
2429 for _, e := range s.live[p.ID] {
2430 t.set(e.ID, e.dist, e.line)
2434 // Add new live values from scanning this block.
2435 for _, e := range live.contents() {
2437 if !t.contains(e.key) || d < t.get(e.key) {
2439 t.set(e.key, d, e.aux)
2442 // Also add the correct arg from the saved phi values.
2443 // All phis are at distance delta (we consider them
2444 // simultaneously happening at the start of the block).
2445 for _, v := range phis {
2447 if s.values[id].needReg && (!t.contains(id) || delta < t.get(id)) {
2449 t.set(id, delta, v.Line)
2456 // The live set has changed, update it.
2457 l := s.live[p.ID][:0]
2458 if cap(l) < t.size() {
2459 l = make([]liveInfo, 0, t.size())
2461 for _, e := range t.contents() {
2462 l = append(l, liveInfo{e.key, e.val, e.aux})
2473 if f.pass.debug > regDebug {
2474 fmt.Println("live values at end of each block")
2475 for _, b := range f.Blocks {
2476 fmt.Printf(" %s:", b)
2477 for _, x := range s.live[b.ID] {
2478 fmt.Printf(" v%d", x.ID)
2479 for _, e := range s.desired[b.ID].entries {
2485 for _, r := range e.regs {
2486 if r == noRegister {
2492 fmt.Print(s.registers[r].Name())
2498 fmt.Printf(" avoid=%x", int64(s.desired[b.ID].avoid))
2504 // A desiredState represents desired register assignments.
2505 type desiredState struct {
2506 // Desired assignments will be small, so we just use a list
2507 // of valueID+registers entries.
2508 entries []desiredStateEntry
2509 // Registers that other values want to be in. This value will
2510 // contain at least the union of the regs fields of entries, but
2511 // may contain additional entries for values that were once in
2512 // this data structure but are no longer.
2515 type desiredStateEntry struct {
2516 // (pre-regalloc) value
2518 // Registers it would like to be in, in priority order.
2519 // Unused slots are filled with noRegister.
2523 func (d *desiredState) clear() {
2524 d.entries = d.entries[:0]
2528 // get returns a list of desired registers for value vid.
2529 func (d *desiredState) get(vid ID) [4]register {
2530 for _, e := range d.entries {
2535 return [4]register{noRegister, noRegister, noRegister, noRegister}
2538 // add records that we'd like value vid to be in register r.
2539 func (d *desiredState) add(vid ID, r register) {
2540 d.avoid |= regMask(1) << r
2541 for i := range d.entries {
2547 // Already known and highest priority
2550 for j := 1; j < len(e.regs); j++ {
2552 // Move from lower priority to top priority
2553 copy(e.regs[1:], e.regs[:j])
2558 copy(e.regs[1:], e.regs[:])
2562 d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}})
2565 func (d *desiredState) addList(vid ID, regs [4]register) {
2566 // regs is in priority order, so iterate in reverse order.
2567 for i := len(regs) - 1; i >= 0; i-- {
2569 if r != noRegister {
2575 // clobber erases any desired registers in the set m.
2576 func (d *desiredState) clobber(m regMask) {
2577 for i := 0; i < len(d.entries); {
2580 for _, r := range e.regs {
2581 if r != noRegister && m>>r&1 == 0 {
2587 // No more desired registers for this value.
2588 d.entries[i] = d.entries[len(d.entries)-1]
2589 d.entries = d.entries[:len(d.entries)-1]
2592 for ; j < len(e.regs); j++ {
2593 e.regs[j] = noRegister
2600 // copy copies a desired state from another desiredState x.
2601 func (d *desiredState) copy(x *desiredState) {
2602 d.entries = append(d.entries[:0], x.entries...)
2606 // remove removes the desired registers for vid and returns them.
2607 func (d *desiredState) remove(vid ID) [4]register {
2608 for i := range d.entries {
2609 if d.entries[i].ID == vid {
2610 regs := d.entries[i].regs
2611 d.entries[i] = d.entries[len(d.entries)-1]
2612 d.entries = d.entries[:len(d.entries)-1]
2616 return [4]register{noRegister, noRegister, noRegister, noRegister}
2619 // merge merges another desired state x into d.
2620 func (d *desiredState) merge(x *desiredState) {
2622 // There should only be a few desired registers, so
2623 // linear insert is ok.
2624 for _, e := range x.entries {
2625 d.addList(e.ID, e.regs)