Source file src/cmd/compile/internal/ssa/regalloc.go
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. 4 5 // Register allocation. 6 // 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. 12 // 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. 16 // 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. 20 // 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. 26 27 // Spilling 28 // 29 // During the normal course of the allocator, we might throw a still-live 30 // value out of all registers. When that value is subsequently used, we must 31 // load it from a slot on the stack. We must also issue an instruction to 32 // initialize that stack location with a copy of v. 33 // 34 // pre-regalloc: 35 // (1) v = Op ... 36 // (2) x = Op ... 37 // (3) ... = Op v ... 38 // 39 // post-regalloc: 40 // (1) v = Op ... : AX // computes v, store result in AX 41 // s = StoreReg v // spill v to a stack slot 42 // (2) x = Op ... : AX // some other op uses AX 43 // c = LoadReg s : CX // restore v from stack slot 44 // (3) ... = Op c ... // use the restored value 45 // 46 // Allocation occurs normally until we reach (3) and we realize we have 47 // a use of v and it isn't in any register. At that point, we allocate 48 // a spill (a StoreReg) for v. We can't determine the correct place for 49 // the spill at this point, so we allocate the spill as blockless initially. 50 // The restore is then generated to load v back into a register so it can 51 // be used. Subsequent uses of v will use the restored value c instead. 52 // 53 // What remains is the question of where to schedule the spill. 54 // During allocation, we keep track of the dominator of all restores of v. 55 // The spill of v must dominate that block. The spill must also be issued at 56 // a point where v is still in a register. 57 // 58 // To find the right place, start at b, the block which dominates all restores. 59 // - If b is v.Block, then issue the spill right after v. 60 // It is known to be in a register at that point, and dominates any restores. 61 // - Otherwise, if v is in a register at the start of b, 62 // put the spill of v at the start of b. 63 // - Otherwise, set b = immediate dominator of b, and repeat. 64 // 65 // Phi values are special, as always. We define two kinds of phis, those 66 // where the merge happens in a register (a "register" phi) and those where 67 // the merge happens in a stack location (a "stack" phi). 68 // 69 // A register phi must have the phi and all of its inputs allocated to the 70 // same register. Register phis are spilled similarly to regular ops. 71 // 72 // A stack phi must have the phi and all of its inputs allocated to the same 73 // stack location. Stack phis start out life already spilled - each phi 74 // input must be a store (using StoreReg) at the end of the corresponding 75 // predecessor block. 76 // b1: y = ... : AX b2: z = ... : BX 77 // y2 = StoreReg y z2 = StoreReg z 78 // goto b3 goto b3 79 // b3: x = phi(y2, z2) 80 // The stack allocator knows that StoreReg args of stack-allocated phis 81 // must be allocated to the same stack slot as the phi that uses them. 82 // x is now a spilled value and a restore must appear before its first use. 83 84 // TODO 85 86 // Use an affinity graph to mark two values which should use the 87 // same register. This affinity graph will be used to prefer certain 88 // registers for allocation. This affinity helps eliminate moves that 89 // are required for phi implementations and helps generate allocations 90 // for 2-register architectures. 91 92 // Note: regalloc generates a not-quite-SSA output. If we have: 93 // 94 // b1: x = ... : AX 95 // x2 = StoreReg x 96 // ... AX gets reused for something else ... 97 // if ... goto b3 else b4 98 // 99 // b3: x3 = LoadReg x2 : BX b4: x4 = LoadReg x2 : CX 100 // ... use x3 ... ... use x4 ... 101 // 102 // b2: ... use x3 ... 103 // 104 // If b3 is the primary predecessor of b2, then we use x3 in b2 and 105 // add a x4:CX->BX copy at the end of b4. 106 // But the definition of x3 doesn't dominate b2. We should really 107 // insert an extra phi at the start of b2 (x5=phi(x3,x4):BX) to keep 108 // SSA form. For now, we ignore this problem as remaining in strict 109 // SSA form isn't needed after regalloc. We'll just leave the use 110 // of x3 not dominated by the definition of x3, and the CX->BX copy 111 // will have no use (so don't run deadcode after regalloc!). 112 // TODO: maybe we should introduce these extra phis? 113 114 package ssa 115 116 import ( 117 "cmd/compile/internal/ssa/block" 118 "cmd/compile/internal/ssa/ssaop" 119 "cmd/internal/src" 120 ) 121 122 const ( 123 moveSpills = iota 124 LogSpills 125 RegDebug 126 StackDebug 127 ) 128 129 func RegMaskAt(i ssaop.Register) ssaop.RegMask { 130 if i < 64 { 131 return ssaop.RegMask{V1: 1 << i} 132 } 133 return ssaop.RegMask{V2: 1 << (i - 64)} 134 } 135 136 type Use struct { 137 // distance from start of the block to a use of a value 138 // Dist == 0 used by first instruction in block 139 // Dist == len(b.Values)-1 used by last instruction in block 140 // Dist == len(b.Values) used by block's control value 141 // Dist > len(b.Values) used by a subsequent block 142 Dist int32 143 Pos src.XPos // source position of the use 144 Next *Use // linked list of uses of a value in nondecreasing dist order 145 } 146 147 // A ValState records the register allocation state for a (pre-regalloc) value. 148 type ValState struct { 149 Regs ssaop.RegMask // the set of registers holding a Value (usually just one) 150 Uses *Use // list of uses in this block 151 Spill *Value // spilled copy of the Value (if any) 152 RestoreMin int32 // minimum of all restores' blocks' sdom.entry 153 RestoreMax int32 // maximum of all restores' blocks' sdom.exit 154 NeedReg bool // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags() 155 Rematerializeable bool // cached value of v.rematerializeable() 156 } 157 158 // NeedRegister reports whether v needs a register. 159 func (v *Value) NeedRegister() bool { 160 return !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple() 161 } 162 163 // Rematerializeable reports whether the register allocator should recompute 164 // a value instead of spilling/restoring it. 165 func (v *Value) Rematerializeable() bool { 166 if !ssaop.OpcodeTable[v.Op].Rematerializeable { 167 return false 168 } 169 for _, a := range v.Args { 170 // Fixed-register allocations (SP, SB, etc.) are always available. 171 // Any other argument of an opcode makes it not rematerializeable. 172 if !ssaop.OpcodeTable[a.Op].FixedReg { 173 return false 174 } 175 } 176 return true 177 } 178 179 // ComputeUnavoidableCalls computes the containsUnavoidableCall fields in the loop nest. 180 func (loopnest *LoopNest) ComputeUnavoidableCalls() { 181 f := loopnest.F 182 183 hasCall := f.Cache.AllocBoolSlice(f.NumBlocks()) 184 defer f.Cache.FreeBoolSlice(hasCall) 185 for _, b := range f.Blocks { 186 if b.containsCall() { 187 hasCall[b.ID] = true 188 } 189 } 190 found := f.Cache.AllocSparseSet(f.NumBlocks()) 191 defer f.Cache.FreeSparseSet(found) 192 // Run dfs to find path through the loop that avoids all calls. 193 // Such path either escapes the loop or returns back to the header. 194 // It isn't enough to have exit not dominated by any call, for example: 195 // ... some loop 196 // call1 call2 197 // \ / 198 // block 199 // ... 200 // block is not dominated by any single call, but we don't have call-free path to it. 201 loopLoop: 202 for _, l := range loopnest.Loops { 203 found.Clear() 204 tovisit := make([]*Block, 0, 8) 205 tovisit = append(tovisit, l.Header) 206 for len(tovisit) > 0 { 207 cur := tovisit[len(tovisit)-1] 208 tovisit = tovisit[:len(tovisit)-1] 209 if hasCall[cur.ID] { 210 continue 211 } 212 for _, s := range cur.Succs { 213 nb := s.Block() 214 if nb == l.Header { 215 // Found a call-free path around the loop. 216 continue loopLoop 217 } 218 if found.Contains(nb.ID) { 219 // Already found via another path. 220 continue 221 } 222 nl := loopnest.B2L[nb.ID] 223 if nl == nil || (nl.Depth <= l.Depth && nl != l) { 224 // Left the loop. 225 continue 226 } 227 tovisit = append(tovisit, nb) 228 found.Add(nb.ID) 229 } 230 } 231 // No call-free path was found. 232 l.ContainsUnavoidableCall = true 233 } 234 } 235 236 func (b *Block) containsCall() bool { 237 if b.Kind == block.BlockDefer { 238 return true 239 } 240 for _, v := range b.Values { 241 if ssaop.OpcodeTable[v.Op].Call { 242 return true 243 } 244 } 245 return false 246 } 247