| // Copyright 2015 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Register allocation. |
| // |
| // We use a version of a linear scan register allocator. We treat the |
| // whole function as a single long basic block and run through |
| // it using a greedy register allocator. Then all merge edges |
| // (those targeting a block with len(Preds)>1) are processed to |
| // shuffle data into the place that the target of the edge expects. |
| // |
| // The greedy allocator moves values into registers just before they |
| // are used, spills registers only when necessary, and spills the |
| // value whose next use is farthest in the future. |
| // |
| // The register allocator requires that a block is not scheduled until |
| // at least one of its predecessors have been scheduled. The most recent |
| // such predecessor provides the starting register state for a block. |
| // |
| // It also requires that there are no critical edges (critical = |
| // comes from a block with >1 successor and goes to a block with >1 |
| // predecessor). This makes it easy to add fixup code on merge edges - |
| // the source of a merge edge has only one successor, so we can add |
| // fixup code to the end of that block. |
| |
| // Spilling |
| // |
| // During the normal course of the allocator, we might throw a still-live |
| // value out of all registers. When that value is subsequently used, we must |
| // load it from a slot on the stack. We must also issue an instruction to |
| // initialize that stack location with a copy of v. |
| // |
| // pre-regalloc: |
| // (1) v = Op ... |
| // (2) x = Op ... |
| // (3) ... = Op v ... |
| // |
| // post-regalloc: |
| // (1) v = Op ... : AX // computes v, store result in AX |
| // s = StoreReg v // spill v to a stack slot |
| // (2) x = Op ... : AX // some other op uses AX |
| // c = LoadReg s : CX // restore v from stack slot |
| // (3) ... = Op c ... // use the restored value |
| // |
| // Allocation occurs normally until we reach (3) and we realize we have |
| // a use of v and it isn't in any register. At that point, we allocate |
| // a spill (a StoreReg) for v. We can't determine the correct place for |
| // the spill at this point, so we allocate the spill as blockless initially. |
| // The restore is then generated to load v back into a register so it can |
| // be used. Subsequent uses of v will use the restored value c instead. |
| // |
| // What remains is the question of where to schedule the spill. |
| // During allocation, we keep track of the dominator of all restores of v. |
| // The spill of v must dominate that block. The spill must also be issued at |
| // a point where v is still in a register. |
| // |
| // To find the right place, start at b, the block which dominates all restores. |
| // - If b is v.Block, then issue the spill right after v. |
| // It is known to be in a register at that point, and dominates any restores. |
| // - Otherwise, if v is in a register at the start of b, |
| // put the spill of v at the start of b. |
| // - Otherwise, set b = immediate dominator of b, and repeat. |
| // |
| // Phi values are special, as always. We define two kinds of phis, those |
| // where the merge happens in a register (a "register" phi) and those where |
| // the merge happens in a stack location (a "stack" phi). |
| // |
| // A register phi must have the phi and all of its inputs allocated to the |
| // same register. Register phis are spilled similarly to regular ops. |
| // |
| // A stack phi must have the phi and all of its inputs allocated to the same |
| // stack location. Stack phis start out life already spilled - each phi |
| // input must be a store (using StoreReg) at the end of the corresponding |
| // predecessor block. |
| // b1: y = ... : AX b2: z = ... : BX |
| // y2 = StoreReg y z2 = StoreReg z |
| // goto b3 goto b3 |
| // b3: x = phi(y2, z2) |
| // The stack allocator knows that StoreReg args of stack-allocated phis |
| // must be allocated to the same stack slot as the phi that uses them. |
| // x is now a spilled value and a restore must appear before its first use. |
| |
| // TODO |
| |
| // Use an affinity graph to mark two values which should use the |
| // same register. This affinity graph will be used to prefer certain |
| // registers for allocation. This affinity helps eliminate moves that |
| // are required for phi implementations and helps generate allocations |
| // for 2-register architectures. |
| |
| // Note: regalloc generates a not-quite-SSA output. If we have: |
| // |
| // b1: x = ... : AX |
| // x2 = StoreReg x |
| // ... AX gets reused for something else ... |
| // if ... goto b3 else b4 |
| // |
| // b3: x3 = LoadReg x2 : BX b4: x4 = LoadReg x2 : CX |
| // ... use x3 ... ... use x4 ... |
| // |
| // b2: ... use x3 ... |
| // |
| // If b3 is the primary predecessor of b2, then we use x3 in b2 and |
| // add a x4:CX->BX copy at the end of b4. |
| // But the definition of x3 doesn't dominate b2. We should really |
| // insert a dummy phi at the start of b2 (x5=phi(x3,x4):BX) to keep |
| // SSA form. For now, we ignore this problem as remaining in strict |
| // SSA form isn't needed after regalloc. We'll just leave the use |
| // of x3 not dominated by the definition of x3, and the CX->BX copy |
| // will have no use (so don't run deadcode after regalloc!). |
| // TODO: maybe we should introduce these extra phis? |
| |
| package ssa |
| |
| import ( |
| "cmd/compile/internal/types" |
| "cmd/internal/objabi" |
| "cmd/internal/src" |
| "fmt" |
| "unsafe" |
| ) |
| |
| const ( |
| moveSpills = iota |
| logSpills |
| regDebug |
| stackDebug |
| ) |
| |
| // distance is a measure of how far into the future values are used. |
| // distance is measured in units of instructions. |
| const ( |
| likelyDistance = 1 |
| normalDistance = 10 |
| unlikelyDistance = 100 |
| ) |
| |
| // regalloc performs register allocation on f. It sets f.RegAlloc |
| // to the resulting allocation. |
| func regalloc(f *Func) { |
| var s regAllocState |
| s.init(f) |
| s.regalloc(f) |
| } |
| |
| type register uint8 |
| |
| const noRegister register = 255 |
| |
| type regMask uint64 |
| |
| func (m regMask) String() string { |
| s := "" |
| for r := register(0); m != 0; r++ { |
| if m>>r&1 == 0 { |
| continue |
| } |
| m &^= regMask(1) << r |
| if s != "" { |
| s += " " |
| } |
| s += fmt.Sprintf("r%d", r) |
| } |
| return s |
| } |
| |
| // countRegs returns the number of set bits in the register mask. |
| func countRegs(r regMask) int { |
| n := 0 |
| for r != 0 { |
| n += int(r & 1) |
| r >>= 1 |
| } |
| return n |
| } |
| |
| // pickReg picks an arbitrary register from the register mask. |
| func pickReg(r regMask) register { |
| // pick the lowest one |
| if r == 0 { |
| panic("can't pick a register from an empty set") |
| } |
| for i := register(0); ; i++ { |
| if r&1 != 0 { |
| return i |
| } |
| r >>= 1 |
| } |
| } |
| |
| type use struct { |
| dist int32 // distance from start of the block to a use of a value |
| pos src.XPos // source position of the use |
| next *use // linked list of uses of a value in nondecreasing dist order |
| } |
| |
| // A valState records the register allocation state for a (pre-regalloc) value. |
| type valState struct { |
| regs regMask // the set of registers holding a Value (usually just one) |
| uses *use // list of uses in this block |
| spill *Value // spilled copy of the Value (if any) |
| restoreMin int32 // minimum of all restores' blocks' sdom.entry |
| restoreMax int32 // maximum of all restores' blocks' sdom.exit |
| needReg bool // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags() |
| rematerializeable bool // cached value of v.rematerializeable() |
| } |
| |
| type regState struct { |
| v *Value // Original (preregalloc) Value stored in this register. |
| c *Value // A Value equal to v which is currently in a register. Might be v or a copy of it. |
| // If a register is unused, v==c==nil |
| } |
| |
| type regAllocState struct { |
| f *Func |
| |
| sdom SparseTree |
| registers []Register |
| numRegs register |
| SPReg register |
| SBReg register |
| GReg register |
| allocatable regMask |
| |
| // for each block, its primary predecessor. |
| // A predecessor of b is primary if it is the closest |
| // predecessor that appears before b in the layout order. |
| // We record the index in the Preds list where the primary predecessor sits. |
| primary []int32 |
| |
| // live values at the end of each block. live[b.ID] is a list of value IDs |
| // which are live at the end of b, together with a count of how many instructions |
| // forward to the next use. |
| live [][]liveInfo |
| // desired register assignments at the end of each block. |
| // Note that this is a static map computed before allocation occurs. Dynamic |
| // register desires (from partially completed allocations) will trump |
| // this information. |
| desired []desiredState |
| |
| // current state of each (preregalloc) Value |
| values []valState |
| |
| // names associated with each Value |
| valueNames [][]LocalSlot |
| |
| // ID of SP, SB values |
| sp, sb ID |
| |
| // For each Value, map from its value ID back to the |
| // preregalloc Value it was derived from. |
| orig []*Value |
| |
| // current state of each register |
| regs []regState |
| |
| // registers that contain values which can't be kicked out |
| nospill regMask |
| |
| // mask of registers currently in use |
| used regMask |
| |
| // mask of registers used in the current instruction |
| tmpused regMask |
| |
| // current block we're working on |
| curBlock *Block |
| |
| // cache of use records |
| freeUseRecords *use |
| |
| // endRegs[blockid] is the register state at the end of each block. |
| // encoded as a set of endReg records. |
| endRegs [][]endReg |
| |
| // startRegs[blockid] is the register state at the start of merge blocks. |
| // saved state does not include the state of phi ops in the block. |
| startRegs [][]startReg |
| |
| // spillLive[blockid] is the set of live spills at the end of each block |
| spillLive [][]ID |
| |
| // a set of copies we generated to move things around, and |
| // whether it is used in shuffle. Unused copies will be deleted. |
| copies map[*Value]bool |
| |
| loopnest *loopnest |
| } |
| |
| type endReg struct { |
| r register |
| v *Value // pre-regalloc value held in this register (TODO: can we use ID here?) |
| c *Value // cached version of the value |
| } |
| |
| type startReg struct { |
| r register |
| v *Value // pre-regalloc value needed in this register |
| c *Value // cached version of the value |
| pos src.XPos // source position of use of this register |
| } |
| |
| // freeReg frees up register r. Any current user of r is kicked out. |
| func (s *regAllocState) freeReg(r register) { |
| s.freeOrResetReg(r, false) |
| } |
| |
| // freeOrResetReg frees up register r. Any current user of r is kicked out. |
| // resetting indicates that the operation is only for bookkeeping, |
| // e.g. when clearing out state upon entry to a new block. |
| func (s *regAllocState) freeOrResetReg(r register, resetting bool) { |
| v := s.regs[r].v |
| if v == nil { |
| s.f.Fatalf("tried to free an already free register %d\n", r) |
| } |
| |
| // Mark r as unused. |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("freeReg %s (dump %s/%s)\n", &s.registers[r], v, s.regs[r].c) |
| } |
| if !resetting && s.f.Config.ctxt.Flag_locationlists && len(s.valueNames[v.ID]) != 0 { |
| kill := s.curBlock.NewValue0(src.NoXPos, OpRegKill, types.TypeVoid) |
| for int(kill.ID) >= len(s.orig) { |
| s.orig = append(s.orig, nil) |
| } |
| for _, name := range s.valueNames[v.ID] { |
| s.f.NamedValues[name] = append(s.f.NamedValues[name], kill) |
| } |
| s.f.setHome(kill, &s.registers[r]) |
| } |
| s.regs[r] = regState{} |
| s.values[v.ID].regs &^= regMask(1) << r |
| s.used &^= regMask(1) << r |
| } |
| |
| // freeRegs frees up all registers listed in m. |
| func (s *regAllocState) freeRegs(m regMask) { |
| for m&s.used != 0 { |
| s.freeReg(pickReg(m & s.used)) |
| } |
| } |
| |
| // setOrig records that c's original value is the same as |
| // v's original value. |
| func (s *regAllocState) setOrig(c *Value, v *Value) { |
| for int(c.ID) >= len(s.orig) { |
| s.orig = append(s.orig, nil) |
| } |
| if s.orig[c.ID] != nil { |
| s.f.Fatalf("orig value set twice %s %s", c, v) |
| } |
| s.orig[c.ID] = s.orig[v.ID] |
| } |
| |
| // assignReg assigns register r to hold c, a copy of v. |
| // r must be unused. |
| func (s *regAllocState) assignReg(r register, v *Value, c *Value) { |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("assignReg %s %s/%s\n", &s.registers[r], v, c) |
| } |
| if s.regs[r].v != nil { |
| 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) |
| } |
| |
| // Update state. |
| s.regs[r] = regState{v, c} |
| s.values[v.ID].regs |= regMask(1) << r |
| s.used |= regMask(1) << r |
| s.f.setHome(c, &s.registers[r]) |
| } |
| |
| // allocReg chooses a register from the set of registers in mask. |
| // If there is no unused register, a Value will be kicked out of |
| // a register to make room. |
| func (s *regAllocState) allocReg(mask regMask, v *Value) register { |
| mask &= s.allocatable |
| mask &^= s.nospill |
| if mask == 0 { |
| s.f.Fatalf("no register available for %s", v) |
| } |
| |
| // Pick an unused register if one is available. |
| if mask&^s.used != 0 { |
| return pickReg(mask &^ s.used) |
| } |
| |
| // Pick a value to spill. Spill the value with the |
| // farthest-in-the-future use. |
| // TODO: Prefer registers with already spilled Values? |
| // TODO: Modify preference using affinity graph. |
| // TODO: if a single value is in multiple registers, spill one of them |
| // before spilling a value in just a single register. |
| |
| // Find a register to spill. We spill the register containing the value |
| // whose next use is as far in the future as possible. |
| // https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm |
| var r register |
| maxuse := int32(-1) |
| for t := register(0); t < s.numRegs; t++ { |
| if mask>>t&1 == 0 { |
| continue |
| } |
| v := s.regs[t].v |
| if n := s.values[v.ID].uses.dist; n > maxuse { |
| // v's next use is farther in the future than any value |
| // we've seen so far. A new best spill candidate. |
| r = t |
| maxuse = n |
| } |
| } |
| if maxuse == -1 { |
| s.f.Fatalf("couldn't find register to spill") |
| } |
| |
| // Try to move it around before kicking out, if there is a free register. |
| // We generate a Copy and record it. It will be deleted if never used. |
| v2 := s.regs[r].v |
| m := s.compatRegs(v2.Type) &^ s.used &^ s.tmpused &^ (regMask(1) << r) |
| if m != 0 && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 { |
| r2 := pickReg(m) |
| c := s.curBlock.NewValue1(v2.Pos, OpCopy, v2.Type, s.regs[r].c) |
| s.copies[c] = false |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("copy %s to %s : %s\n", v2, c, &s.registers[r2]) |
| } |
| s.setOrig(c, v2) |
| s.assignReg(r2, v2, c) |
| } |
| s.freeReg(r) |
| return r |
| } |
| |
| // makeSpill returns a Value which represents the spilled value of v. |
| // b is the block in which the spill is used. |
| func (s *regAllocState) makeSpill(v *Value, b *Block) *Value { |
| vi := &s.values[v.ID] |
| if vi.spill != nil { |
| // Final block not known - keep track of subtree where restores reside. |
| vi.restoreMin = min32(vi.restoreMin, s.sdom[b.ID].entry) |
| vi.restoreMax = max32(vi.restoreMax, s.sdom[b.ID].exit) |
| return vi.spill |
| } |
| // Make a spill for v. We don't know where we want |
| // to put it yet, so we leave it blockless for now. |
| spill := s.f.newValueNoBlock(OpStoreReg, v.Type, v.Pos) |
| // We also don't know what the spill's arg will be. |
| // Leave it argless for now. |
| s.setOrig(spill, v) |
| vi.spill = spill |
| vi.restoreMin = s.sdom[b.ID].entry |
| vi.restoreMax = s.sdom[b.ID].exit |
| return spill |
| } |
| |
| // allocValToReg allocates v to a register selected from regMask and |
| // returns the register copy of v. Any previous user is kicked out and spilled |
| // (if necessary). Load code is added at the current pc. If nospill is set the |
| // allocated register is marked nospill so the assignment cannot be |
| // undone until the caller allows it by clearing nospill. Returns a |
| // *Value which is either v or a copy of v allocated to the chosen register. |
| func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, pos src.XPos) *Value { |
| vi := &s.values[v.ID] |
| |
| // Check if v is already in a requested register. |
| if mask&vi.regs != 0 { |
| r := pickReg(mask & vi.regs) |
| if s.regs[r].v != v || s.regs[r].c == nil { |
| panic("bad register state") |
| } |
| if nospill { |
| s.nospill |= regMask(1) << r |
| } |
| return s.regs[r].c |
| } |
| |
| // Allocate a register. |
| r := s.allocReg(mask, v) |
| |
| // Allocate v to the new register. |
| var c *Value |
| if vi.regs != 0 { |
| // Copy from a register that v is already in. |
| r2 := pickReg(vi.regs) |
| if s.regs[r2].v != v { |
| panic("bad register state") |
| } |
| c = s.curBlock.NewValue1(pos, OpCopy, v.Type, s.regs[r2].c) |
| } else if v.rematerializeable() { |
| // Rematerialize instead of loading from the spill location. |
| c = v.copyIntoNoXPos(s.curBlock) |
| } else { |
| // Load v from its spill location. |
| spill := s.makeSpill(v, s.curBlock) |
| if s.f.pass.debug > logSpills { |
| s.f.Warnl(vi.spill.Pos, "load spill for %v from %v", v, spill) |
| } |
| c = s.curBlock.NewValue1(pos, OpLoadReg, v.Type, spill) |
| } |
| s.setOrig(c, v) |
| s.assignReg(r, v, c) |
| if nospill { |
| s.nospill |= regMask(1) << r |
| } |
| return c |
| } |
| |
| // isLeaf reports whether f performs any calls. |
| func isLeaf(f *Func) bool { |
| for _, b := range f.Blocks { |
| for _, v := range b.Values { |
| if opcodeTable[v.Op].call { |
| return false |
| } |
| } |
| } |
| return true |
| } |
| |
| func (s *regAllocState) init(f *Func) { |
| s.f = f |
| s.f.RegAlloc = s.f.Cache.locs[:0] |
| s.registers = f.Config.registers |
| if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask(0))*8) { |
| s.f.Fatalf("bad number of registers: %d", nr) |
| } else { |
| s.numRegs = register(nr) |
| } |
| // Locate SP, SB, and g registers. |
| s.SPReg = noRegister |
| s.SBReg = noRegister |
| s.GReg = noRegister |
| for r := register(0); r < s.numRegs; r++ { |
| switch s.registers[r].String() { |
| case "SP": |
| s.SPReg = r |
| case "SB": |
| s.SBReg = r |
| case "g": |
| s.GReg = r |
| } |
| } |
| // Make sure we found all required registers. |
| switch noRegister { |
| case s.SPReg: |
| s.f.Fatalf("no SP register found") |
| case s.SBReg: |
| s.f.Fatalf("no SB register found") |
| case s.GReg: |
| if f.Config.hasGReg { |
| s.f.Fatalf("no g register found") |
| } |
| } |
| |
| // Figure out which registers we're allowed to use. |
| s.allocatable = s.f.Config.gpRegMask | s.f.Config.fpRegMask | s.f.Config.specialRegMask |
| s.allocatable &^= 1 << s.SPReg |
| s.allocatable &^= 1 << s.SBReg |
| if s.f.Config.hasGReg { |
| s.allocatable &^= 1 << s.GReg |
| } |
| if s.f.Config.ctxt.Framepointer_enabled && s.f.Config.FPReg >= 0 { |
| s.allocatable &^= 1 << uint(s.f.Config.FPReg) |
| } |
| if s.f.Config.ctxt.Flag_shared { |
| switch s.f.Config.arch { |
| case "ppc64le": // R2 already reserved. |
| s.allocatable &^= 1 << 12 // R12 |
| } |
| } |
| if s.f.Config.LinkReg != -1 { |
| if isLeaf(f) { |
| // Leaf functions don't save/restore the link register. |
| s.allocatable &^= 1 << uint(s.f.Config.LinkReg) |
| } |
| if s.f.Config.arch == "arm" && objabi.GOARM == 5 { |
| // On ARMv5 we insert softfloat calls at each FP instruction. |
| // This clobbers LR almost everywhere. Disable allocating LR |
| // on ARMv5. |
| s.allocatable &^= 1 << uint(s.f.Config.LinkReg) |
| } |
| } |
| if s.f.Config.ctxt.Flag_dynlink { |
| switch s.f.Config.arch { |
| case "amd64": |
| s.allocatable &^= 1 << 15 // R15 |
| case "arm": |
| s.allocatable &^= 1 << 9 // R9 |
| case "ppc64le": // R2 already reserved. |
| s.allocatable &^= 1 << 12 // R12 |
| case "arm64": |
| // nothing to do? |
| case "386": |
| // nothing to do. |
| // Note that for Flag_shared (position independent code) |
| // we do need to be careful, but that carefulness is hidden |
| // in the rewrite rules so we always have a free register |
| // available for global load/stores. See gen/386.rules (search for Flag_shared). |
| case "s390x": |
| // nothing to do, R10 & R11 already reserved |
| default: |
| s.f.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch) |
| } |
| } |
| if s.f.Config.nacl { |
| switch s.f.Config.arch { |
| case "arm": |
| s.allocatable &^= 1 << 9 // R9 is "thread pointer" on nacl/arm |
| case "amd64p32": |
| s.allocatable &^= 1 << 5 // BP - reserved for nacl |
| s.allocatable &^= 1 << 15 // R15 - reserved for nacl |
| } |
| } |
| if s.f.Config.use387 { |
| s.allocatable &^= 1 << 15 // X7 disallowed (one 387 register is used as scratch space during SSE->387 generation in ../x86/387.go) |
| } |
| |
| s.regs = make([]regState, s.numRegs) |
| s.values = make([]valState, f.NumValues()) |
| s.orig = make([]*Value, f.NumValues()) |
| s.copies = make(map[*Value]bool) |
| if s.f.Config.ctxt.Flag_locationlists { |
| s.valueNames = make([][]LocalSlot, f.NumValues()) |
| for slot, values := range f.NamedValues { |
| if isSynthetic(&slot) { |
| continue |
| } |
| for _, value := range values { |
| s.valueNames[value.ID] = append(s.valueNames[value.ID], slot) |
| } |
| } |
| } |
| for _, b := range f.Blocks { |
| for _, v := range b.Values { |
| if !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple() { |
| s.values[v.ID].needReg = true |
| s.values[v.ID].rematerializeable = v.rematerializeable() |
| s.orig[v.ID] = v |
| } |
| // Note: needReg is false for values returning Tuple types. |
| // Instead, we mark the corresponding Selects as needReg. |
| } |
| } |
| s.computeLive() |
| |
| // Compute block order. This array allows us to distinguish forward edges |
| // from backward edges and compute how far they go. |
| blockOrder := make([]int32, f.NumBlocks()) |
| for i, b := range f.Blocks { |
| blockOrder[b.ID] = int32(i) |
| } |
| |
| // Compute primary predecessors. |
| s.primary = make([]int32, f.NumBlocks()) |
| for _, b := range f.Blocks { |
| best := -1 |
| for i, e := range b.Preds { |
| p := e.b |
| if blockOrder[p.ID] >= blockOrder[b.ID] { |
| continue // backward edge |
| } |
| if best == -1 || blockOrder[p.ID] > blockOrder[b.Preds[best].b.ID] { |
| best = i |
| } |
| } |
| s.primary[b.ID] = int32(best) |
| } |
| |
| s.endRegs = make([][]endReg, f.NumBlocks()) |
| s.startRegs = make([][]startReg, f.NumBlocks()) |
| s.spillLive = make([][]ID, f.NumBlocks()) |
| s.sdom = f.sdom() |
| } |
| |
| // Adds a use record for id at distance dist from the start of the block. |
| // All calls to addUse must happen with nonincreasing dist. |
| func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) { |
| r := s.freeUseRecords |
| if r != nil { |
| s.freeUseRecords = r.next |
| } else { |
| r = &use{} |
| } |
| r.dist = dist |
| r.pos = pos |
| r.next = s.values[id].uses |
| s.values[id].uses = r |
| if r.next != nil && dist > r.next.dist { |
| s.f.Fatalf("uses added in wrong order") |
| } |
| } |
| |
| // advanceUses advances the uses of v's args from the state before v to the state after v. |
| // Any values which have no more uses are deallocated from registers. |
| func (s *regAllocState) advanceUses(v *Value) { |
| for _, a := range v.Args { |
| if !s.values[a.ID].needReg { |
| continue |
| } |
| ai := &s.values[a.ID] |
| r := ai.uses |
| ai.uses = r.next |
| if r.next == nil { |
| // Value is dead, free all registers that hold it. |
| s.freeRegs(ai.regs) |
| } |
| r.next = s.freeUseRecords |
| s.freeUseRecords = r |
| } |
| } |
| |
| // liveAfterCurrentInstruction reports whether v is live after |
| // the current instruction is completed. v must be used by the |
| // current instruction. |
| func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool { |
| u := s.values[v.ID].uses |
| d := u.dist |
| for u != nil && u.dist == d { |
| u = u.next |
| } |
| return u != nil && u.dist > d |
| } |
| |
| // Sets the state of the registers to that encoded in regs. |
| func (s *regAllocState) setState(regs []endReg) { |
| for s.used != 0 { |
| s.freeOrResetReg(pickReg(s.used), true) |
| } |
| for _, x := range regs { |
| s.assignReg(x.r, x.v, x.c) |
| } |
| } |
| |
| // compatRegs returns the set of registers which can store a type t. |
| func (s *regAllocState) compatRegs(t *types.Type) regMask { |
| var m regMask |
| if t.IsTuple() || t.IsFlags() { |
| return 0 |
| } |
| if t.IsFloat() || t == types.TypeInt128 { |
| m = s.f.Config.fpRegMask |
| } else { |
| m = s.f.Config.gpRegMask |
| } |
| return m & s.allocatable |
| } |
| |
| func (s *regAllocState) regalloc(f *Func) { |
| regValLiveSet := f.newSparseSet(f.NumValues()) // set of values that may be live in register |
| defer f.retSparseSet(regValLiveSet) |
| var oldSched []*Value |
| var phis []*Value |
| var phiRegs []register |
| var args []*Value |
| |
| // Data structure used for computing desired registers. |
| var desired desiredState |
| |
| // Desired registers for inputs & outputs for each instruction in the block. |
| type dentry struct { |
| out [4]register // desired output registers |
| in [3][4]register // desired input registers (for inputs 0,1, and 2) |
| } |
| var dinfo []dentry |
| |
| if f.Entry != f.Blocks[0] { |
| f.Fatalf("entry block must be first") |
| } |
| |
| for _, b := range f.Blocks { |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("Begin processing block %v\n", b) |
| } |
| s.curBlock = b |
| |
| // Initialize regValLiveSet and uses fields for this block. |
| // Walk backwards through the block doing liveness analysis. |
| regValLiveSet.clear() |
| for _, e := range s.live[b.ID] { |
| s.addUse(e.ID, int32(len(b.Values))+e.dist, e.pos) // pseudo-uses from beyond end of block |
| regValLiveSet.add(e.ID) |
| } |
| if v := b.Control; v != nil && s.values[v.ID].needReg { |
| s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control value |
| regValLiveSet.add(v.ID) |
| } |
| for i := len(b.Values) - 1; i >= 0; i-- { |
| v := b.Values[i] |
| regValLiveSet.remove(v.ID) |
| if v.Op == OpPhi { |
| // Remove v from the live set, but don't add |
| // any inputs. This is the state the len(b.Preds)>1 |
| // case below desires; it wants to process phis specially. |
| continue |
| } |
| if opcodeTable[v.Op].call { |
| // Function call clobbers all the registers but SP and SB. |
| regValLiveSet.clear() |
| if s.sp != 0 && s.values[s.sp].uses != nil { |
| regValLiveSet.add(s.sp) |
| } |
| if s.sb != 0 && s.values[s.sb].uses != nil { |
| regValLiveSet.add(s.sb) |
| } |
| } |
| for _, a := range v.Args { |
| if !s.values[a.ID].needReg { |
| continue |
| } |
| s.addUse(a.ID, int32(i), v.Pos) |
| regValLiveSet.add(a.ID) |
| } |
| } |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("uses for %s:%s\n", s.f.Name, b) |
| for i := range s.values { |
| vi := &s.values[i] |
| u := vi.uses |
| if u == nil { |
| continue |
| } |
| fmt.Printf(" v%d:", i) |
| for u != nil { |
| fmt.Printf(" %d", u.dist) |
| u = u.next |
| } |
| fmt.Println() |
| } |
| } |
| |
| // Make a copy of the block schedule so we can generate a new one in place. |
| // We make a separate copy for phis and regular values. |
| nphi := 0 |
| for _, v := range b.Values { |
| if v.Op != OpPhi { |
| break |
| } |
| nphi++ |
| } |
| phis = append(phis[:0], b.Values[:nphi]...) |
| oldSched = append(oldSched[:0], b.Values[nphi:]...) |
| b.Values = b.Values[:0] |
| |
| // Initialize start state of block. |
| if b == f.Entry { |
| // Regalloc state is empty to start. |
| if nphi > 0 { |
| f.Fatalf("phis in entry block") |
| } |
| } else if len(b.Preds) == 1 { |
| // Start regalloc state with the end state of the previous block. |
| s.setState(s.endRegs[b.Preds[0].b.ID]) |
| if nphi > 0 { |
| f.Fatalf("phis in single-predecessor block") |
| } |
| // Drop any values which are no longer live. |
| // This may happen because at the end of p, a value may be |
| // live but only used by some other successor of p. |
| for r := register(0); r < s.numRegs; r++ { |
| v := s.regs[r].v |
| if v != nil && !regValLiveSet.contains(v.ID) { |
| s.freeReg(r) |
| } |
| } |
| } else { |
| // This is the complicated case. We have more than one predecessor, |
| // which means we may have Phi ops. |
| |
| // Start with the final register state of the primary predecessor |
| idx := s.primary[b.ID] |
| if idx < 0 { |
| f.Fatalf("block with no primary predecessor %s", b) |
| } |
| p := b.Preds[idx].b |
| s.setState(s.endRegs[p.ID]) |
| |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("starting merge block %s with end state of %s:\n", b, p) |
| for _, x := range s.endRegs[p.ID] { |
| fmt.Printf(" %s: orig:%s cache:%s\n", &s.registers[x.r], x.v, x.c) |
| } |
| } |
| |
| // Decide on registers for phi ops. Use the registers determined |
| // by the primary predecessor if we can. |
| // TODO: pick best of (already processed) predecessors? |
| // Majority vote? Deepest nesting level? |
| phiRegs = phiRegs[:0] |
| var phiUsed regMask |
| for _, v := range phis { |
| if !s.values[v.ID].needReg { |
| phiRegs = append(phiRegs, noRegister) |
| continue |
| } |
| a := v.Args[idx] |
| // Some instructions target not-allocatable registers. |
| // They're not suitable for further (phi-function) allocation. |
| m := s.values[a.ID].regs &^ phiUsed & s.allocatable |
| if m != 0 { |
| r := pickReg(m) |
| phiUsed |= regMask(1) << r |
| phiRegs = append(phiRegs, r) |
| } else { |
| phiRegs = append(phiRegs, noRegister) |
| } |
| } |
| |
| // Second pass - deallocate any phi inputs which are now dead. |
| for i, v := range phis { |
| if !s.values[v.ID].needReg { |
| continue |
| } |
| a := v.Args[idx] |
| if !regValLiveSet.contains(a.ID) { |
| // Input is dead beyond the phi, deallocate |
| // anywhere else it might live. |
| s.freeRegs(s.values[a.ID].regs) |
| } else { |
| // Input is still live. |
| // Try to move it around before kicking out, if there is a free register. |
| // We generate a Copy in the predecessor block and record it. It will be |
| // deleted if never used. |
| r := phiRegs[i] |
| if r == noRegister { |
| continue |
| } |
| // Pick a free register. At this point some registers used in the predecessor |
| // block may have been deallocated. Those are the ones used for Phis. Exclude |
| // them (and they are not going to be helpful anyway). |
| m := s.compatRegs(a.Type) &^ s.used &^ phiUsed |
| if m != 0 && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 { |
| r2 := pickReg(m) |
| c := p.NewValue1(a.Pos, OpCopy, a.Type, s.regs[r].c) |
| s.copies[c] = false |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("copy %s to %s : %s\n", a, c, &s.registers[r2]) |
| } |
| s.setOrig(c, a) |
| s.assignReg(r2, a, c) |
| s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c}) |
| } |
| s.freeReg(r) |
| } |
| } |
| |
| // Copy phi ops into new schedule. |
| b.Values = append(b.Values, phis...) |
| |
| // Third pass - pick registers for phis whose inputs |
| // were not in a register. |
| for i, v := range phis { |
| if !s.values[v.ID].needReg { |
| continue |
| } |
| if phiRegs[i] != noRegister { |
| continue |
| } |
| if s.f.Config.use387 && v.Type.IsFloat() { |
| continue // 387 can't handle floats in registers between blocks |
| } |
| m := s.compatRegs(v.Type) &^ phiUsed &^ s.used |
| if m != 0 { |
| r := pickReg(m) |
| phiRegs[i] = r |
| phiUsed |= regMask(1) << r |
| } |
| } |
| |
| // Set registers for phis. Add phi spill code. |
| for i, v := range phis { |
| if !s.values[v.ID].needReg { |
| continue |
| } |
| r := phiRegs[i] |
| if r == noRegister { |
| // stack-based phi |
| // Spills will be inserted in all the predecessors below. |
| s.values[v.ID].spill = v // v starts life spilled |
| continue |
| } |
| // register-based phi |
| s.assignReg(r, v, v) |
| } |
| |
| // Deallocate any values which are no longer live. Phis are excluded. |
| for r := register(0); r < s.numRegs; r++ { |
| if phiUsed>>r&1 != 0 { |
| continue |
| } |
| v := s.regs[r].v |
| if v != nil && !regValLiveSet.contains(v.ID) { |
| s.freeReg(r) |
| } |
| } |
| |
| // Save the starting state for use by merge edges. |
| var regList []startReg |
| for r := register(0); r < s.numRegs; r++ { |
| v := s.regs[r].v |
| if v == nil { |
| continue |
| } |
| if phiUsed>>r&1 != 0 { |
| // Skip registers that phis used, we'll handle those |
| // specially during merge edge processing. |
| continue |
| } |
| regList = append(regList, startReg{r, v, s.regs[r].c, s.values[v.ID].uses.pos}) |
| } |
| s.startRegs[b.ID] = regList |
| |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("after phis\n") |
| for _, x := range s.startRegs[b.ID] { |
| fmt.Printf(" %s: v%d\n", &s.registers[x.r], x.v.ID) |
| } |
| } |
| } |
| |
| // Allocate space to record the desired registers for each value. |
| dinfo = dinfo[:0] |
| for i := 0; i < len(oldSched); i++ { |
| dinfo = append(dinfo, dentry{}) |
| } |
| |
| // Load static desired register info at the end of the block. |
| desired.copy(&s.desired[b.ID]) |
| |
| // Check actual assigned registers at the start of the next block(s). |
| // Dynamically assigned registers will trump the static |
| // desired registers computed during liveness analysis. |
| // Note that we do this phase after startRegs is set above, so that |
| // we get the right behavior for a block which branches to itself. |
| for _, e := range b.Succs { |
| succ := e.b |
| // TODO: prioritize likely successor? |
| for _, x := range s.startRegs[succ.ID] { |
| desired.add(x.v.ID, x.r) |
| } |
| // Process phi ops in succ. |
| pidx := e.i |
| for _, v := range succ.Values { |
| if v.Op != OpPhi { |
| continue |
| } |
| if !s.values[v.ID].needReg { |
| continue |
| } |
| rp, ok := s.f.getHome(v.ID).(*Register) |
| if !ok { |
| continue |
| } |
| desired.add(v.Args[pidx].ID, register(rp.num)) |
| } |
| } |
| // Walk values backwards computing desired register info. |
| // See computeLive for more comments. |
| for i := len(oldSched) - 1; i >= 0; i-- { |
| v := oldSched[i] |
| prefs := desired.remove(v.ID) |
| desired.clobber(opcodeTable[v.Op].reg.clobbers) |
| for _, j := range opcodeTable[v.Op].reg.inputs { |
| if countRegs(j.regs) != 1 { |
| continue |
| } |
| desired.clobber(j.regs) |
| desired.add(v.Args[j.idx].ID, pickReg(j.regs)) |
| } |
| if opcodeTable[v.Op].resultInArg0 { |
| if opcodeTable[v.Op].commutative { |
| desired.addList(v.Args[1].ID, prefs) |
| } |
| desired.addList(v.Args[0].ID, prefs) |
| } |
| // Save desired registers for this value. |
| dinfo[i].out = prefs |
| for j, a := range v.Args { |
| if j >= len(dinfo[i].in) { |
| break |
| } |
| dinfo[i].in[j] = desired.get(a.ID) |
| } |
| } |
| |
| // Process all the non-phi values. |
| for idx, v := range oldSched { |
| if s.f.pass.debug > regDebug { |
| fmt.Printf(" processing %s\n", v.LongString()) |
| } |
| regspec := opcodeTable[v.Op].reg |
| if v.Op == OpPhi { |
| f.Fatalf("phi %s not at start of block", v) |
| } |
| if v.Op == OpSP { |
| s.assignReg(s.SPReg, v, v) |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| s.sp = v.ID |
| continue |
| } |
| if v.Op == OpSB { |
| s.assignReg(s.SBReg, v, v) |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| s.sb = v.ID |
| continue |
| } |
| if v.Op == OpSelect0 || v.Op == OpSelect1 { |
| if s.values[v.ID].needReg { |
| var i = 0 |
| if v.Op == OpSelect1 { |
| i = 1 |
| } |
| s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v) |
| } |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| goto issueSpill |
| } |
| if v.Op == OpGetG && s.f.Config.hasGReg { |
| // use hardware g register |
| if s.regs[s.GReg].v != nil { |
| s.freeReg(s.GReg) // kick out the old value |
| } |
| s.assignReg(s.GReg, v, v) |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| goto issueSpill |
| } |
| if v.Op == OpArg { |
| // Args are "pre-spilled" values. We don't allocate |
| // any register here. We just set up the spill pointer to |
| // point at itself and any later user will restore it to use it. |
| s.values[v.ID].spill = v |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| continue |
| } |
| if v.Op == OpKeepAlive { |
| // Make sure the argument to v is still live here. |
| s.advanceUses(v) |
| vi := &s.values[v.Args[0].ID] |
| if vi.spill != nil { |
| // Use the spill location. |
| v.SetArg(0, vi.spill) |
| } else { |
| // No need to keep unspilled values live. |
| // These are typically rematerializeable constants like nil, |
| // or values of a variable that were modified since the last call. |
| v.Op = OpCopy |
| v.SetArgs1(v.Args[1]) |
| } |
| b.Values = append(b.Values, v) |
| continue |
| } |
| if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 { |
| // No register allocation required (or none specified yet) |
| s.freeRegs(regspec.clobbers) |
| b.Values = append(b.Values, v) |
| s.advanceUses(v) |
| continue |
| } |
| |
| if s.values[v.ID].rematerializeable { |
| // Value is rematerializeable, don't issue it here. |
| // It will get issued just before each use (see |
| // allocValueToReg). |
| for _, a := range v.Args { |
| a.Uses-- |
| } |
| s.advanceUses(v) |
| continue |
| } |
| |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("value %s\n", v.LongString()) |
| fmt.Printf(" out:") |
| for _, r := range dinfo[idx].out { |
| if r != noRegister { |
| fmt.Printf(" %s", &s.registers[r]) |
| } |
| } |
| fmt.Println() |
| for i := 0; i < len(v.Args) && i < 3; i++ { |
| fmt.Printf(" in%d:", i) |
| for _, r := range dinfo[idx].in[i] { |
| if r != noRegister { |
| fmt.Printf(" %s", &s.registers[r]) |
| } |
| } |
| fmt.Println() |
| } |
| } |
| |
| // Move arguments to registers. Process in an ordering defined |
| // by the register specification (most constrained first). |
| args = append(args[:0], v.Args...) |
| for _, i := range regspec.inputs { |
| mask := i.regs |
| if mask&s.values[args[i.idx].ID].regs == 0 { |
| // Need a new register for the input. |
| mask &= s.allocatable |
| mask &^= s.nospill |
| // Used desired register if available. |
| if i.idx < 3 { |
| for _, r := range dinfo[idx].in[i.idx] { |
| if r != noRegister && (mask&^s.used)>>r&1 != 0 { |
| // Desired register is allowed and unused. |
| mask = regMask(1) << r |
| break |
| } |
| } |
| } |
| // Avoid registers we're saving for other values. |
| if mask&^desired.avoid != 0 { |
| mask &^= desired.avoid |
| } |
| } |
| args[i.idx] = s.allocValToReg(args[i.idx], mask, true, v.Pos) |
| } |
| |
| // If the output clobbers the input register, make sure we have |
| // at least two copies of the input register so we don't |
| // have to reload the value from the spill location. |
| if opcodeTable[v.Op].resultInArg0 { |
| var m regMask |
| if !s.liveAfterCurrentInstruction(v.Args[0]) { |
| // arg0 is dead. We can clobber its register. |
| goto ok |
| } |
| if s.values[v.Args[0].ID].rematerializeable { |
| // We can rematerialize the input, don't worry about clobbering it. |
| goto ok |
| } |
| if countRegs(s.values[v.Args[0].ID].regs) >= 2 { |
| // we have at least 2 copies of arg0. We can afford to clobber one. |
| goto ok |
| } |
| if opcodeTable[v.Op].commutative { |
| if !s.liveAfterCurrentInstruction(v.Args[1]) { |
| args[0], args[1] = args[1], args[0] |
| goto ok |
| } |
| if s.values[v.Args[1].ID].rematerializeable { |
| args[0], args[1] = args[1], args[0] |
| goto ok |
| } |
| if countRegs(s.values[v.Args[1].ID].regs) >= 2 { |
| args[0], args[1] = args[1], args[0] |
| goto ok |
| } |
| } |
| |
| // We can't overwrite arg0 (or arg1, if commutative). So we |
| // need to make a copy of an input so we have a register we can modify. |
| |
| // Possible new registers to copy into. |
| m = s.compatRegs(v.Args[0].Type) &^ s.used |
| if m == 0 { |
| // No free registers. In this case we'll just clobber |
| // an input and future uses of that input must use a restore. |
| // TODO(khr): We should really do this like allocReg does it, |
| // spilling the value with the most distant next use. |
| goto ok |
| } |
| |
| // Try to move an input to the desired output. |
| for _, r := range dinfo[idx].out { |
| if r != noRegister && m>>r&1 != 0 { |
| m = regMask(1) << r |
| args[0] = s.allocValToReg(v.Args[0], m, true, v.Pos) |
| // Note: we update args[0] so the instruction will |
| // use the register copy we just made. |
| goto ok |
| } |
| } |
| // Try to copy input to its desired location & use its old |
| // location as the result register. |
| for _, r := range dinfo[idx].in[0] { |
| if r != noRegister && m>>r&1 != 0 { |
| m = regMask(1) << r |
| c := s.allocValToReg(v.Args[0], m, true, v.Pos) |
| s.copies[c] = false |
| // Note: no update to args[0] so the instruction will |
| // use the original copy. |
| goto ok |
| } |
| } |
| if opcodeTable[v.Op].commutative { |
| for _, r := range dinfo[idx].in[1] { |
| if r != noRegister && m>>r&1 != 0 { |
| m = regMask(1) << r |
| c := s.allocValToReg(v.Args[1], m, true, v.Pos) |
| s.copies[c] = false |
| args[0], args[1] = args[1], args[0] |
| goto ok |
| } |
| } |
| } |
| // Avoid future fixed uses if we can. |
| if m&^desired.avoid != 0 { |
| m &^= desired.avoid |
| } |
| // Save input 0 to a new register so we can clobber it. |
| c := s.allocValToReg(v.Args[0], m, true, v.Pos) |
| s.copies[c] = false |
| } |
| |
| ok: |
| // Now that all args are in regs, we're ready to issue the value itself. |
| // Before we pick a register for the output value, allow input registers |
| // to be deallocated. We do this here so that the output can use the |
| // same register as a dying input. |
| if !opcodeTable[v.Op].resultNotInArgs { |
| s.tmpused = s.nospill |
| s.nospill = 0 |
| s.advanceUses(v) // frees any registers holding args that are no longer live |
| } |
| |
| // Dump any registers which will be clobbered |
| s.freeRegs(regspec.clobbers) |
| s.tmpused |= regspec.clobbers |
| |
| // Pick registers for outputs. |
| { |
| outRegs := [2]register{noRegister, noRegister} |
| var used regMask |
| for _, out := range regspec.outputs { |
| mask := out.regs & s.allocatable &^ used |
| if mask == 0 { |
| continue |
| } |
| if opcodeTable[v.Op].resultInArg0 && out.idx == 0 { |
| if !opcodeTable[v.Op].commutative { |
| // Output must use the same register as input 0. |
| r := register(s.f.getHome(args[0].ID).(*Register).num) |
| mask = regMask(1) << r |
| } else { |
| // Output must use the same register as input 0 or 1. |
| r0 := register(s.f.getHome(args[0].ID).(*Register).num) |
| r1 := register(s.f.getHome(args[1].ID).(*Register).num) |
| // Check r0 and r1 for desired output register. |
| found := false |
| for _, r := range dinfo[idx].out { |
| if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 { |
| mask = regMask(1) << r |
| found = true |
| if r == r1 { |
| args[0], args[1] = args[1], args[0] |
| } |
| break |
| } |
| } |
| if !found { |
| // Neither are desired, pick r0. |
| mask = regMask(1) << r0 |
| } |
| } |
| } |
| for _, r := range dinfo[idx].out { |
| if r != noRegister && (mask&^s.used)>>r&1 != 0 { |
| // Desired register is allowed and unused. |
| mask = regMask(1) << r |
| break |
| } |
| } |
| // Avoid registers we're saving for other values. |
| if mask&^desired.avoid != 0 { |
| mask &^= desired.avoid |
| } |
| r := s.allocReg(mask, v) |
| outRegs[out.idx] = r |
| used |= regMask(1) << r |
| s.tmpused |= regMask(1) << r |
| } |
| // Record register choices |
| if v.Type.IsTuple() { |
| var outLocs LocPair |
| if r := outRegs[0]; r != noRegister { |
| outLocs[0] = &s.registers[r] |
| } |
| if r := outRegs[1]; r != noRegister { |
| outLocs[1] = &s.registers[r] |
| } |
| s.f.setHome(v, outLocs) |
| // Note that subsequent SelectX instructions will do the assignReg calls. |
| } else { |
| if r := outRegs[0]; r != noRegister { |
| s.assignReg(r, v, v) |
| } |
| } |
| } |
| |
| // deallocate dead args, if we have not done so |
| if opcodeTable[v.Op].resultNotInArgs { |
| s.nospill = 0 |
| s.advanceUses(v) // frees any registers holding args that are no longer live |
| } |
| s.tmpused = 0 |
| |
| // Issue the Value itself. |
| for i, a := range args { |
| v.SetArg(i, a) // use register version of arguments |
| } |
| b.Values = append(b.Values, v) |
| |
| issueSpill: |
| } |
| |
| // Load control value into reg. |
| if v := b.Control; v != nil && s.values[v.ID].needReg { |
| if s.f.pass.debug > regDebug { |
| fmt.Printf(" processing control %s\n", v.LongString()) |
| } |
| // We assume that a control input can be passed in any |
| // type-compatible register. If this turns out not to be true, |
| // we'll need to introduce a regspec for a block's control value. |
| b.Control = s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos) |
| if b.Control != v { |
| v.Uses-- |
| b.Control.Uses++ |
| } |
| // Remove this use from the uses list. |
| vi := &s.values[v.ID] |
| u := vi.uses |
| vi.uses = u.next |
| if u.next == nil { |
| s.freeRegs(vi.regs) // value is dead |
| } |
| u.next = s.freeUseRecords |
| s.freeUseRecords = u |
| } |
| |
| // Spill any values that can't live across basic block boundaries. |
| if s.f.Config.use387 { |
| s.freeRegs(s.f.Config.fpRegMask) |
| } |
| |
| // If we are approaching a merge point and we are the primary |
| // predecessor of it, find live values that we use soon after |
| // the merge point and promote them to registers now. |
| if len(b.Succs) == 1 { |
| // For this to be worthwhile, the loop must have no calls in it. |
| top := b.Succs[0].b |
| loop := s.loopnest.b2l[top.ID] |
| if loop == nil || loop.header != top || loop.containsCall { |
| goto badloop |
| } |
| |
| // TODO: sort by distance, pick the closest ones? |
| for _, live := range s.live[b.ID] { |
| if live.dist >= unlikelyDistance { |
| // Don't preload anything live after the loop. |
| continue |
| } |
| vid := live.ID |
| vi := &s.values[vid] |
| if vi.regs != 0 { |
| continue |
| } |
| if vi.rematerializeable { |
| continue |
| } |
| v := s.orig[vid] |
| if s.f.Config.use387 && v.Type.IsFloat() { |
| continue // 387 can't handle floats in registers between blocks |
| } |
| m := s.compatRegs(v.Type) &^ s.used |
| if m&^desired.avoid != 0 { |
| m &^= desired.avoid |
| } |
| if m != 0 { |
| s.allocValToReg(v, m, false, b.Pos) |
| } |
| } |
| } |
| badloop: |
| ; |
| |
| // Save end-of-block register state. |
| // First count how many, this cuts allocations in half. |
| k := 0 |
| for r := register(0); r < s.numRegs; r++ { |
| v := s.regs[r].v |
| if v == nil { |
| continue |
| } |
| k++ |
| } |
| regList := make([]endReg, 0, k) |
| for r := register(0); r < s.numRegs; r++ { |
| v := s.regs[r].v |
| if v == nil { |
| continue |
| } |
| regList = append(regList, endReg{r, v, s.regs[r].c}) |
| } |
| s.endRegs[b.ID] = regList |
| |
| if checkEnabled { |
| regValLiveSet.clear() |
| for _, x := range s.live[b.ID] { |
| regValLiveSet.add(x.ID) |
| } |
| for r := register(0); r < s.numRegs; r++ { |
| v := s.regs[r].v |
| if v == nil { |
| continue |
| } |
| if !regValLiveSet.contains(v.ID) { |
| s.f.Fatalf("val %s is in reg but not live at end of %s", v, b) |
| } |
| } |
| } |
| |
| // If a value is live at the end of the block and |
| // isn't in a register, generate a use for the spill location. |
| // We need to remember this information so that |
| // the liveness analysis in stackalloc is correct. |
| for _, e := range s.live[b.ID] { |
| vi := &s.values[e.ID] |
| if vi.regs != 0 { |
| // in a register, we'll use that source for the merge. |
| continue |
| } |
| if vi.rematerializeable { |
| // we'll rematerialize during the merge. |
| continue |
| } |
| //fmt.Printf("live-at-end spill for %s at %s\n", s.orig[e.ID], b) |
| spill := s.makeSpill(s.orig[e.ID], b) |
| s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID) |
| } |
| |
| // Clear any final uses. |
| // All that is left should be the pseudo-uses added for values which |
| // are live at the end of b. |
| for _, e := range s.live[b.ID] { |
| u := s.values[e.ID].uses |
| if u == nil { |
| f.Fatalf("live at end, no uses v%d", e.ID) |
| } |
| if u.next != nil { |
| f.Fatalf("live at end, too many uses v%d", e.ID) |
| } |
| s.values[e.ID].uses = nil |
| u.next = s.freeUseRecords |
| s.freeUseRecords = u |
| } |
| } |
| |
| // Decide where the spills we generated will go. |
| s.placeSpills() |
| |
| // Anything that didn't get a register gets a stack location here. |
| // (StoreReg, stack-based phis, inputs, ...) |
| stacklive := stackalloc(s.f, s.spillLive) |
| |
| // Fix up all merge edges. |
| s.shuffle(stacklive) |
| |
| // Erase any copies we never used. |
| // Also, an unused copy might be the only use of another copy, |
| // so continue erasing until we reach a fixed point. |
| for { |
| progress := false |
| for c, used := range s.copies { |
| if !used && c.Uses == 0 { |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("delete copied value %s\n", c.LongString()) |
| } |
| c.Args[0].Uses-- |
| f.freeValue(c) |
| delete(s.copies, c) |
| progress = true |
| } |
| } |
| if !progress { |
| break |
| } |
| } |
| |
| for _, b := range f.Blocks { |
| i := 0 |
| for _, v := range b.Values { |
| if v.Op == OpInvalid { |
| continue |
| } |
| b.Values[i] = v |
| i++ |
| } |
| b.Values = b.Values[:i] |
| } |
| } |
| |
| func (s *regAllocState) placeSpills() { |
| f := s.f |
| |
| // Precompute some useful info. |
| phiRegs := make([]regMask, f.NumBlocks()) |
| for _, b := range f.Blocks { |
| var m regMask |
| for _, v := range b.Values { |
| if v.Op == OpRegKill { |
| continue |
| } |
| if v.Op != OpPhi { |
| break |
| } |
| if r, ok := f.getHome(v.ID).(*Register); ok { |
| m |= regMask(1) << uint(r.num) |
| } |
| } |
| phiRegs[b.ID] = m |
| } |
| |
| // Start maps block IDs to the list of spills |
| // that go at the start of the block (but after any phis). |
| start := map[ID][]*Value{} |
| // After maps value IDs to the list of spills |
| // that go immediately after that value ID. |
| after := map[ID][]*Value{} |
| |
| for i := range s.values { |
| vi := s.values[i] |
| spill := vi.spill |
| if spill == nil { |
| continue |
| } |
| if spill.Block != nil { |
| // Some spills are already fully set up, |
| // like OpArgs and stack-based phis. |
| continue |
| } |
| v := s.orig[i] |
| |
| // Walk down the dominator tree looking for a good place to |
| // put the spill of v. At the start "best" is the best place |
| // we have found so far. |
| // TODO: find a way to make this O(1) without arbitrary cutoffs. |
| best := v.Block |
| bestArg := v |
| var bestDepth int16 |
| if l := s.loopnest.b2l[best.ID]; l != nil { |
| bestDepth = l.depth |
| } |
| b := best |
| const maxSpillSearch = 100 |
| for i := 0; i < maxSpillSearch; i++ { |
| // Find the child of b in the dominator tree which |
| // dominates all restores. |
| p := b |
| b = nil |
| for c := s.sdom.Child(p); c != nil && i < maxSpillSearch; c, i = s.sdom.Sibling(c), i+1 { |
| if s.sdom[c.ID].entry <= vi.restoreMin && s.sdom[c.ID].exit >= vi.restoreMax { |
| // c also dominates all restores. Walk down into c. |
| b = c |
| break |
| } |
| } |
| if b == nil { |
| // Ran out of blocks which dominate all restores. |
| break |
| } |
| |
| var depth int16 |
| if l := s.loopnest.b2l[b.ID]; l != nil { |
| depth = l.depth |
| } |
| if depth > bestDepth { |
| // Don't push the spill into a deeper loop. |
| continue |
| } |
| |
| // If v is in a register at the start of b, we can |
| // place the spill here (after the phis). |
| if len(b.Preds) == 1 { |
| for _, e := range s.endRegs[b.Preds[0].b.ID] { |
| if e.v == v { |
| // Found a better spot for the spill. |
| best = b |
| bestArg = e.c |
| bestDepth = depth |
| break |
| } |
| } |
| } else { |
| for _, e := range s.startRegs[b.ID] { |
| if e.v == v { |
| // Found a better spot for the spill. |
| best = b |
| bestArg = e.c |
| bestDepth = depth |
| break |
| } |
| } |
| } |
| } |
| |
| // Put the spill in the best block we found. |
| spill.Block = best |
| spill.AddArg(bestArg) |
| if best == v.Block && v.Op != OpPhi { |
| // Place immediately after v. |
| after[v.ID] = append(after[v.ID], spill) |
| } else { |
| // Place at the start of best block. |
| start[best.ID] = append(start[best.ID], spill) |
| } |
| } |
| |
| // Insert spill instructions into the block schedules. |
| var oldSched []*Value |
| for _, b := range f.Blocks { |
| nphi := 0 |
| for _, v := range b.Values { |
| if v.Op != OpRegKill && v.Op != OpPhi { |
| break |
| } |
| nphi++ |
| } |
| oldSched = append(oldSched[:0], b.Values[nphi:]...) |
| b.Values = b.Values[:nphi] |
| for _, v := range start[b.ID] { |
| b.Values = append(b.Values, v) |
| } |
| for _, v := range oldSched { |
| b.Values = append(b.Values, v) |
| for _, w := range after[v.ID] { |
| b.Values = append(b.Values, w) |
| } |
| } |
| } |
| } |
| |
| // shuffle fixes up all the merge edges (those going into blocks of indegree > 1). |
| func (s *regAllocState) shuffle(stacklive [][]ID) { |
| var e edgeState |
| e.s = s |
| e.cache = map[ID][]*Value{} |
| e.contents = map[Location]contentRecord{} |
| if s.f.pass.debug > regDebug { |
| fmt.Printf("shuffle %s\n", s.f.Name) |
| fmt.Println(s.f.String()) |
| } |
| |
| for _, b := range s.f.Blocks { |
| if len(b.Preds) <= 1 { |
| continue |
| } |
| e.b = b |
| for i, edge := range b.Preds { |
| p := edge.b |
| e.p = p |
| e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID]) |
| e.process() |
| } |
| } |
| } |
| |
| type edgeState struct { |
| s *regAllocState |
| p, b *Block // edge goes from p->b. |
| |
| // for each pre-regalloc value, a list of equivalent cached values |
| cache map[ID][]*Value |
| cachedVals []ID // (superset of) keys of the above map, for deterministic iteration |
| |
| // map from location to the value it contains |
| contents map[Location]contentRecord |
| |
| // desired destination locations |
| destinations []dstRecord |
| extra []dstRecord |
| |
| usedRegs regMask // registers currently holding something |
| uniqueRegs regMask // registers holding the only copy of a value |
| finalRegs regMask // registers holding final target |
| } |
| |
| type contentRecord struct { |
| vid ID // pre-regalloc value |
| c *Value // cached value |
| final bool // this is a satisfied destination |
| pos src.XPos // source position of use of the value |
| } |
| |
| type dstRecord struct { |
| loc Location // register or stack slot |
| vid ID // pre-regalloc value it should contain |
| splice **Value // place to store reference to the generating instruction |
| pos src.XPos // source position of use of this location |
| } |
| |
| // setup initializes the edge state for shuffling. |
| func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) { |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf("edge %s->%s\n", e.p, e.b) |
| } |
| |
| // Clear state. |
| for _, vid := range e.cachedVals { |
| delete(e.cache, vid) |
| } |
| e.cachedVals = e.cachedVals[:0] |
| for k := range e.contents { |
| delete(e.contents, k) |
| } |
| e.usedRegs = 0 |
| e.uniqueRegs = 0 |
| e.finalRegs = 0 |
| |
| // Live registers can be sources. |
| for _, x := range srcReg { |
| e.set(&e.s.registers[x.r], x.v.ID, x.c, false, src.NoXPos) // don't care the position of the source |
| } |
| // So can all of the spill locations. |
| for _, spillID := range stacklive { |
| v := e.s.orig[spillID] |
| spill := e.s.values[v.ID].spill |
| if !e.s.sdom.isAncestorEq(spill.Block, e.p) { |
| // Spills were placed that only dominate the uses found |
| // during the first regalloc pass. The edge fixup code |
| // can't use a spill location if the spill doesn't dominate |
| // the edge. |
| // We are guaranteed that if the spill doesn't dominate this edge, |
| // then the value is available in a register (because we called |
| // makeSpill for every value not in a register at the start |
| // of an edge). |
| continue |
| } |
| e.set(e.s.f.getHome(spillID), v.ID, spill, false, src.NoXPos) // don't care the position of the source |
| } |
| |
| // Figure out all the destinations we need. |
| dsts := e.destinations[:0] |
| for _, x := range dstReg { |
| dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.v.ID, nil, x.pos}) |
| } |
| // Phis need their args to end up in a specific location. |
| for _, v := range e.b.Values { |
| if v.Op == OpRegKill { |
| continue |
| } |
| if v.Op != OpPhi { |
| break |
| } |
| loc := e.s.f.getHome(v.ID) |
| if loc == nil { |
| continue |
| } |
| dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Pos}) |
| } |
| e.destinations = dsts |
| |
| if e.s.f.pass.debug > regDebug { |
| for _, vid := range e.cachedVals { |
| a := e.cache[vid] |
| for _, c := range a { |
| fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID), vid, c) |
| } |
| } |
| for _, d := range e.destinations { |
| fmt.Printf("dst %s: v%d\n", d.loc, d.vid) |
| } |
| } |
| } |
| |
| // process generates code to move all the values to the right destination locations. |
| func (e *edgeState) process() { |
| dsts := e.destinations |
| |
| // Process the destinations until they are all satisfied. |
| for len(dsts) > 0 { |
| i := 0 |
| for _, d := range dsts { |
| if !e.processDest(d.loc, d.vid, d.splice, d.pos) { |
| // Failed - save for next iteration. |
| dsts[i] = d |
| i++ |
| } |
| } |
| if i < len(dsts) { |
| // Made some progress. Go around again. |
| dsts = dsts[:i] |
| |
| // Append any extras destinations we generated. |
| dsts = append(dsts, e.extra...) |
| e.extra = e.extra[:0] |
| continue |
| } |
| |
| // We made no progress. That means that any |
| // remaining unsatisfied moves are in simple cycles. |
| // For example, A -> B -> C -> D -> A. |
| // A ----> B |
| // ^ | |
| // | | |
| // | v |
| // D <---- C |
| |
| // To break the cycle, we pick an unused register, say R, |
| // and put a copy of B there. |
| // A ----> B |
| // ^ | |
| // | | |
| // | v |
| // D <---- C <---- R=copyofB |
| // When we resume the outer loop, the A->B move can now proceed, |
| // and eventually the whole cycle completes. |
| |
| // Copy any cycle location to a temp register. This duplicates |
| // one of the cycle entries, allowing the just duplicated value |
| // to be overwritten and the cycle to proceed. |
| d := dsts[0] |
| loc := d.loc |
| vid := e.contents[loc].vid |
| c := e.contents[loc].c |
| r := e.findRegFor(c.Type) |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc, c) |
| } |
| e.erase(r) |
| if _, isReg := loc.(*Register); isReg { |
| c = e.p.NewValue1(d.pos, OpCopy, c.Type, c) |
| } else { |
| c = e.p.NewValue1(d.pos, OpLoadReg, c.Type, c) |
| } |
| e.set(r, vid, c, false, d.pos) |
| } |
| } |
| |
| // processDest generates code to put value vid into location loc. Returns true |
| // if progress was made. |
| func (e *edgeState) processDest(loc Location, vid ID, splice **Value, pos src.XPos) bool { |
| occupant := e.contents[loc] |
| if occupant.vid == vid { |
| // Value is already in the correct place. |
| e.contents[loc] = contentRecord{vid, occupant.c, true, pos} |
| if splice != nil { |
| (*splice).Uses-- |
| *splice = occupant.c |
| occupant.c.Uses++ |
| } |
| // Note: if splice==nil then c will appear dead. This is |
| // non-SSA formed code, so be careful after this pass not to run |
| // deadcode elimination. |
| if _, ok := e.s.copies[occupant.c]; ok { |
| // The copy at occupant.c was used to avoid spill. |
| e.s.copies[occupant.c] = true |
| } |
| return true |
| } |
| |
| // Check if we're allowed to clobber the destination location. |
| if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable { |
| // We can't overwrite the last copy |
| // of a value that needs to survive. |
| return false |
| } |
| |
| // Copy from a source of v, register preferred. |
| v := e.s.orig[vid] |
| var c *Value |
| var src Location |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf("moving v%d to %s\n", vid, loc) |
| fmt.Printf("sources of v%d:", vid) |
| } |
| for _, w := range e.cache[vid] { |
| h := e.s.f.getHome(w.ID) |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf(" %s:%s", h, w) |
| } |
| _, isreg := h.(*Register) |
| if src == nil || isreg { |
| c = w |
| src = h |
| } |
| } |
| if e.s.f.pass.debug > regDebug { |
| if src != nil { |
| fmt.Printf(" [use %s]\n", src) |
| } else { |
| fmt.Printf(" [no source]\n") |
| } |
| } |
| _, dstReg := loc.(*Register) |
| |
| // Pre-clobber destination. This avoids the |
| // following situation: |
| // - v is currently held in R0 and stacktmp0. |
| // - We want to copy stacktmp1 to stacktmp0. |
| // - We choose R0 as the temporary register. |
| // During the copy, both R0 and stacktmp0 are |
| // clobbered, losing both copies of v. Oops! |
| // Erasing the destination early means R0 will not |
| // be chosen as the temp register, as it will then |
| // be the last copy of v. |
| e.erase(loc) |
| var x *Value |
| if c == nil { |
| if !e.s.values[vid].rematerializeable { |
| e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString()) |
| } |
| if dstReg { |
| x = v.copyIntoNoXPos(e.p) |
| } else { |
| // Rematerialize into stack slot. Need a free |
| // register to accomplish this. |
| r := e.findRegFor(v.Type) |
| e.erase(r) |
| x = v.copyIntoNoXPos(e.p) |
| e.set(r, vid, x, false, pos) |
| // Make sure we spill with the size of the slot, not the |
| // size of x (which might be wider due to our dropping |
| // of narrowing conversions). |
| x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, x) |
| } |
| } else { |
| // Emit move from src to dst. |
| _, srcReg := src.(*Register) |
| if srcReg { |
| if dstReg { |
| x = e.p.NewValue1(pos, OpCopy, c.Type, c) |
| } else { |
| x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, c) |
| } |
| } else { |
| if dstReg { |
| x = e.p.NewValue1(pos, OpLoadReg, c.Type, c) |
| } else { |
| // mem->mem. Use temp register. |
| r := e.findRegFor(c.Type) |
| e.erase(r) |
| t := e.p.NewValue1(pos, OpLoadReg, c.Type, c) |
| e.set(r, vid, t, false, pos) |
| x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, t) |
| } |
| } |
| } |
| e.set(loc, vid, x, true, pos) |
| if splice != nil { |
| (*splice).Uses-- |
| *splice = x |
| x.Uses++ |
| } |
| return true |
| } |
| |
| // set changes the contents of location loc to hold the given value and its cached representative. |
| func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, pos src.XPos) { |
| e.s.f.setHome(c, loc) |
| e.contents[loc] = contentRecord{vid, c, final, pos} |
| a := e.cache[vid] |
| if len(a) == 0 { |
| e.cachedVals = append(e.cachedVals, vid) |
| } |
| a = append(a, c) |
| e.cache[vid] = a |
| if r, ok := loc.(*Register); ok { |
| e.usedRegs |= regMask(1) << uint(r.num) |
| if final { |
| e.finalRegs |= regMask(1) << uint(r.num) |
| } |
| if len(a) == 1 { |
| e.uniqueRegs |= regMask(1) << uint(r.num) |
| } |
| if len(a) == 2 { |
| if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok { |
| e.uniqueRegs &^= regMask(1) << uint(t.num) |
| } |
| } |
| } |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf("%s\n", c.LongString()) |
| fmt.Printf("v%d now available in %s:%s\n", vid, loc, c) |
| } |
| } |
| |
| // erase removes any user of loc. |
| func (e *edgeState) erase(loc Location) { |
| cr := e.contents[loc] |
| if cr.c == nil { |
| return |
| } |
| vid := cr.vid |
| |
| if cr.final { |
| // Add a destination to move this value back into place. |
| // Make sure it gets added to the tail of the destination queue |
| // so we make progress on other moves first. |
| e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.pos}) |
| } |
| |
| // Remove c from the list of cached values. |
| a := e.cache[vid] |
| for i, c := range a { |
| if e.s.f.getHome(c.ID) == loc { |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf("v%d no longer available in %s:%s\n", vid, loc, c) |
| } |
| a[i], a = a[len(a)-1], a[:len(a)-1] |
| if e.s.f.Config.ctxt.Flag_locationlists { |
| if _, isReg := loc.(*Register); isReg && int(c.ID) < len(e.s.valueNames) && len(e.s.valueNames[c.ID]) != 0 { |
| kill := e.p.NewValue0(src.NoXPos, OpRegKill, types.TypeVoid) |
| e.s.f.setHome(kill, loc) |
| for _, name := range e.s.valueNames[c.ID] { |
| e.s.f.NamedValues[name] = append(e.s.f.NamedValues[name], kill) |
| } |
| } |
| } |
| |
| break |
| } |
| } |
| e.cache[vid] = a |
| |
| // Update register masks. |
| if r, ok := loc.(*Register); ok { |
| e.usedRegs &^= regMask(1) << uint(r.num) |
| if cr.final { |
| e.finalRegs &^= regMask(1) << uint(r.num) |
| } |
| } |
| if len(a) == 1 { |
| if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok { |
| e.uniqueRegs |= regMask(1) << uint(r.num) |
| } |
| } |
| } |
| |
| // findRegFor finds a register we can use to make a temp copy of type typ. |
| func (e *edgeState) findRegFor(typ *types.Type) Location { |
| // Which registers are possibilities. |
| var m regMask |
| types := &e.s.f.Config.Types |
| if typ.IsFloat() { |
| m = e.s.compatRegs(types.Float64) |
| } else { |
| m = e.s.compatRegs(types.Int64) |
| } |
| |
| // Pick a register. In priority order: |
| // 1) an unused register |
| // 2) a non-unique register not holding a final value |
| // 3) a non-unique register |
| // 4) TODO: a register holding a rematerializeable value |
| x := m &^ e.usedRegs |
| if x != 0 { |
| return &e.s.registers[pickReg(x)] |
| } |
| x = m &^ e.uniqueRegs &^ e.finalRegs |
| if x != 0 { |
| return &e.s.registers[pickReg(x)] |
| } |
| x = m &^ e.uniqueRegs |
| if x != 0 { |
| return &e.s.registers[pickReg(x)] |
| } |
| |
| // No register is available. |
| // Pick a register to spill. |
| for _, vid := range e.cachedVals { |
| a := e.cache[vid] |
| for _, c := range a { |
| if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m>>uint(r.num)&1 != 0 { |
| if !c.rematerializeable() { |
| x := e.p.NewValue1(c.Pos, OpStoreReg, c.Type, c) |
| // Allocate a temp location to spill a register to. |
| // The type of the slot is immaterial - it will not be live across |
| // any safepoint. Just use a type big enough to hold any register. |
| t := LocalSlot{N: e.s.f.fe.Auto(c.Pos, types.Int64), Type: types.Int64} |
| // TODO: reuse these slots. They'll need to be erased first. |
| e.set(t, vid, x, false, c.Pos) |
| if e.s.f.pass.debug > regDebug { |
| fmt.Printf(" SPILL %s->%s %s\n", r, t, x.LongString()) |
| } |
| } |
| // r will now be overwritten by the caller. At some point |
| // later, the newly saved value will be moved back to its |
| // final destination in processDest. |
| return r |
| } |
| } |
| } |
| |
| fmt.Printf("m:%d unique:%d final:%d\n", m, e.uniqueRegs, e.finalRegs) |
| for _, vid := range e.cachedVals { |
| a := e.cache[vid] |
| for _, c := range a { |
| fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID)) |
| } |
| } |
| e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b) |
| return nil |
| } |
| |
| // rematerializeable reports whether the register allocator should recompute |
| // a value instead of spilling/restoring it. |
| func (v *Value) rematerializeable() bool { |
| if !opcodeTable[v.Op].rematerializeable { |
| return false |
| } |
| for _, a := range v.Args { |
| // SP and SB (generated by OpSP and OpSB) are always available. |
| if a.Op != OpSP && a.Op != OpSB { |
| return false |
| } |
| } |
| return true |
| } |
| |
| type liveInfo struct { |
| ID ID // ID of value |
| dist int32 // # of instructions before next use |
| pos src.XPos // source position of next use |
| } |
| |
| // dblock contains information about desired & avoid registers at the end of a block. |
| type dblock struct { |
| prefers []desiredStateEntry |
| avoid regMask |
| } |
| |
| // computeLive computes a map from block ID to a list of value IDs live at the end |
| // of that block. Together with the value ID is a count of how many instructions |
| // to the next use of that value. The resulting map is stored in s.live. |
| // computeLive also computes the desired register information at the end of each block. |
| // This desired register information is stored in s.desired. |
| // TODO: this could be quadratic if lots of variables are live across lots of |
| // basic blocks. Figure out a way to make this function (or, more precisely, the user |
| // of this function) require only linear size & time. |
| func (s *regAllocState) computeLive() { |
| f := s.f |
| s.live = make([][]liveInfo, f.NumBlocks()) |
| s.desired = make([]desiredState, f.NumBlocks()) |
| var phis []*Value |
| |
| live := newSparseMap(f.NumValues()) |
| t := newSparseMap(f.NumValues()) |
| |
| // Keep track of which value we want in each register. |
| var desired desiredState |
| |
| // Instead of iterating over f.Blocks, iterate over their postordering. |
| // Liveness information flows backward, so starting at the end |
| // increases the probability that we will stabilize quickly. |
| // TODO: Do a better job yet. Here's one possibility: |
| // Calculate the dominator tree and locate all strongly connected components. |
| // If a value is live in one block of an SCC, it is live in all. |
| // Walk the dominator tree from end to beginning, just once, treating SCC |
| // components as single blocks, duplicated calculated liveness information |
| // out to all of them. |
| po := f.postorder() |
| s.loopnest = f.loopnest() |
| s.loopnest.calculateDepths() |
| for { |
| changed := false |
| |
| for _, b := range po { |
| // Start with known live values at the end of the block. |
| // Add len(b.Values) to adjust from end-of-block distance |
| // to beginning-of-block distance. |
| live.clear() |
| for _, e := range s.live[b.ID] { |
| live.set(e.ID, e.dist+int32(len(b.Values)), e.pos) |
| } |
| |
| // Mark control value as live |
| if b.Control != nil && s.values[b.Control.ID].needReg { |
| live.set(b.Control.ID, int32(len(b.Values)), b.Pos) |
| } |
| |
| // Propagate backwards to the start of the block |
| // Assumes Values have been scheduled. |
| phis = phis[:0] |
| for i := len(b.Values) - 1; i >= 0; i-- { |
| v := b.Values[i] |
| live.remove(v.ID) |
| if v.Op == OpPhi { |
| // save phi ops for later |
| phis = append(phis, v) |
| continue |
| } |
| if opcodeTable[v.Op].call { |
| c := live.contents() |
| for i := range c { |
| c[i].val += unlikelyDistance |
| } |
| } |
| for _, a := range v.Args { |
| if s.values[a.ID].needReg { |
| live.set(a.ID, int32(i), v.Pos) |
| } |
| } |
| } |
| // Propagate desired registers backwards. |
| desired.copy(&s.desired[b.ID]) |
| for i := len(b.Values) - 1; i >= 0; i-- { |
| v := b.Values[i] |
| prefs := desired.remove(v.ID) |
| if v.Op == OpPhi { |
| // TODO: if v is a phi, save desired register for phi inputs. |
| // For now, we just drop it and don't propagate |
| // desired registers back though phi nodes. |
| continue |
| } |
| // Cancel desired registers if they get clobbered. |
| desired.clobber(opcodeTable[v.Op].reg.clobbers) |
| // Update desired registers if there are any fixed register inputs. |
| for _, j := range opcodeTable[v.Op].reg.inputs { |
| if countRegs(j.regs) != 1 { |
| continue |
| } |
| desired.clobber(j.regs) |
| desired.add(v.Args[j.idx].ID, pickReg(j.regs)) |
| } |
| // Set desired register of input 0 if this is a 2-operand instruction. |
| if opcodeTable[v.Op].resultInArg0 { |
| if opcodeTable[v.Op].commutative { |
| desired.addList(v.Args[1].ID, prefs) |
| } |
| desired.addList(v.Args[0].ID, prefs) |
| } |
| } |
| |
| // For each predecessor of b, expand its list of live-at-end values. |
| // invariant: live contains the values live at the start of b (excluding phi inputs) |
| for i, e := range b.Preds { |
| p := e.b |
| // Compute additional distance for the edge. |
| // Note: delta must be at least 1 to distinguish the control |
| // value use from the first user in a successor block. |
| delta := int32(normalDistance) |
| if len(p.Succs) == 2 { |
| if p.Succs[0].b == b && p.Likely == BranchLikely || |
| p.Succs[1].b == b && p.Likely == BranchUnlikely { |
| delta = likelyDistance |
| } |
| if p.Succs[0].b == b && p.Likely == BranchUnlikely || |
| p.Succs[1].b == b && p.Likely == BranchLikely { |
| delta = unlikelyDistance |
| } |
| } |
| |
| // Update any desired registers at the end of p. |
| s.desired[p.ID].merge(&desired) |
| |
| // Start t off with the previously known live values at the end of p. |
| t.clear() |
| for _, e := range s.live[p.ID] { |
| t.set(e.ID, e.dist, e.pos) |
| } |
| update := false |
| |
| // Add new live values from scanning this block. |
| for _, e := range live.contents() { |
| d := e.val + delta |
| if !t.contains(e.key) || d < t.get(e.key) { |
| update = true |
| t.set(e.key, d, e.aux) |
| } |
| } |
| // Also add the correct arg from the saved phi values. |
| // All phis are at distance delta (we consider them |
| // simultaneously happening at the start of the block). |
| for _, v := range phis { |
| id := v.Args[i].ID |
| if s.values[id].needReg && (!t.contains(id) || delta < t.get(id)) { |
| update = true |
| t.set(id, delta, v.Pos) |
| } |
| } |
| |
| if !update { |
| continue |
| } |
| // The live set has changed, update it. |
| l := s.live[p.ID][:0] |
| if cap(l) < t.size() { |
| l = make([]liveInfo, 0, t.size()) |
| } |
| for _, e := range t.contents() { |
| l = append(l, liveInfo{e.key, e.val, e.aux}) |
| } |
| s.live[p.ID] = l |
| changed = true |
| } |
| } |
| |
| if !changed { |
| break |
| } |
| } |
| if f.pass.debug > regDebug { |
| fmt.Println("live values at end of each block") |
| for _, b := range f.Blocks { |
| fmt.Printf(" %s:", b) |
| for _, x := range s.live[b.ID] { |
| fmt.Printf(" v%d", x.ID) |
| for _, e := range s.desired[b.ID].entries { |
| if e.ID != x.ID { |
| continue |
| } |
| fmt.Printf("[") |
| first := true |
| for _, r := range e.regs { |
| if r == noRegister { |
| continue |
| } |
| if !first { |
| fmt.Printf(",") |
| } |
| fmt.Print(&s.registers[r]) |
| first = false |
| } |
| fmt.Printf("]") |
| } |
| } |
| fmt.Printf(" avoid=%x", int64(s.desired[b.ID].avoid)) |
| fmt.Println() |
| } |
| } |
| } |
| |
| // A desiredState represents desired register assignments. |
| type desiredState struct { |
| // Desired assignments will be small, so we just use a list |
| // of valueID+registers entries. |
| entries []desiredStateEntry |
| // Registers that other values want to be in. This value will |
| // contain at least the union of the regs fields of entries, but |
| // may contain additional entries for values that were once in |
| // this data structure but are no longer. |
| avoid regMask |
| } |
| type desiredStateEntry struct { |
| // (pre-regalloc) value |
| ID ID |
| // Registers it would like to be in, in priority order. |
| // Unused slots are filled with noRegister. |
| regs [4]register |
| } |
| |
| func (d *desiredState) clear() { |
| d.entries = d.entries[:0] |
| d.avoid = 0 |
| } |
| |
| // get returns a list of desired registers for value vid. |
| func (d *desiredState) get(vid ID) [4]register { |
| for _, e := range d.entries { |
| if e.ID == vid { |
| return e.regs |
| } |
| } |
| return [4]register{noRegister, noRegister, noRegister, noRegister} |
| } |
| |
| // add records that we'd like value vid to be in register r. |
| func (d *desiredState) add(vid ID, r register) { |
| d.avoid |= regMask(1) << r |
| for i := range d.entries { |
| e := &d.entries[i] |
| if e.ID != vid { |
| continue |
| } |
| if e.regs[0] == r { |
| // Already known and highest priority |
| return |
| } |
| for j := 1; j < len(e.regs); j++ { |
| if e.regs[j] == r { |
| // Move from lower priority to top priority |
| copy(e.regs[1:], e.regs[:j]) |
| e.regs[0] = r |
| return |
| } |
| } |
| copy(e.regs[1:], e.regs[:]) |
| e.regs[0] = r |
| return |
| } |
| d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}}) |
| } |
| |
| func (d *desiredState) addList(vid ID, regs [4]register) { |
| // regs is in priority order, so iterate in reverse order. |
| for i := len(regs) - 1; i >= 0; i-- { |
| r := regs[i] |
| if r != noRegister { |
| d.add(vid, r) |
| } |
| } |
| } |
| |
| // clobber erases any desired registers in the set m. |
| func (d *desiredState) clobber(m regMask) { |
| for i := 0; i < len(d.entries); { |
| e := &d.entries[i] |
| j := 0 |
| for _, r := range e.regs { |
| if r != noRegister && m>>r&1 == 0 { |
| e.regs[j] = r |
| j++ |
| } |
| } |
| if j == 0 { |
| // No more desired registers for this value. |
| d.entries[i] = d.entries[len(d.entries)-1] |
| d.entries = d.entries[:len(d.entries)-1] |
| continue |
| } |
| for ; j < len(e.regs); j++ { |
| e.regs[j] = noRegister |
| } |
| i++ |
| } |
| d.avoid &^= m |
| } |
| |
| // copy copies a desired state from another desiredState x. |
| func (d *desiredState) copy(x *desiredState) { |
| d.entries = append(d.entries[:0], x.entries...) |
| d.avoid = x.avoid |
| } |
| |
| // remove removes the desired registers for vid and returns them. |
| func (d *desiredState) remove(vid ID) [4]register { |
| for i := range d.entries { |
| if d.entries[i].ID == vid { |
| regs := d.entries[i].regs |
| d.entries[i] = d.entries[len(d.entries)-1] |
| d.entries = d.entries[:len(d.entries)-1] |
| return regs |
| } |
| } |
| return [4]register{noRegister, noRegister, noRegister, noRegister} |
| } |
| |
| // merge merges another desired state x into d. |
| func (d *desiredState) merge(x *desiredState) { |
| d.avoid |= x.avoid |
| // There should only be a few desired registers, so |
| // linear insert is ok. |
| for _, e := range x.entries { |
| d.addList(e.ID, e.regs) |
| } |
| } |
| |
| func min32(x, y int32) int32 { |
| if x < y { |
| return x |
| } |
| return y |
| } |
| func max32(x, y int32) int32 { |
| if x > y { |
| return x |
| } |
| return y |
| } |