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 5package ssa 6 7// tighten moves Values closer to the Blocks in which they are used. 8// This can reduce the amount of register spilling required, 9// if it doesn't also create more live values. 10// A Value can be moved to any block that 11// dominates all blocks in which it is used. 12func tighten(f *Func) { 13 canMove := make([]bool, f.NumValues()) 14 for _, b := range f.Blocks { 15 for _, v := range b.Values { 16 if v.Op.isLoweredGetClosurePtr() { 17 // Must stay in the entry block. 18 continue 19 } 20 switch v.Op { 21 case OpPhi, OpArg, OpArgIntReg, OpArgFloatReg, OpSelect0, OpSelect1, OpSelectN: 22 // Phis need to stay in their block. 23 // Arg must stay in the entry block. 24 // Tuple selectors must stay with the tuple generator. 25 // SelectN is typically, ultimately, a register. 26 continue 27 } 28 if v.MemoryArg() != nil { 29 // We can't move values which have a memory arg - it might 30 // make two memory values live across a block boundary. 31 continue 32 } 33 // Count arguments which will need a register. 34 narg := 0 35 for _, a := range v.Args { 36 if !a.rematerializeable() { 37 narg++ 38 } 39 } 40 if narg >= 2 && !v.Type.IsFlags() { 41 // Don't move values with more than one input, as that may 42 // increase register pressure. 43 // We make an exception for flags, as we want flag generators 44 // moved next to uses (because we only have 1 flag register). 45 continue 46 } 47 canMove[v.ID] = true 48 } 49 } 50 51 // Build data structure for fast least-common-ancestor queries. 52 lca := makeLCArange(f) 53 54 // For each moveable value, record the block that dominates all uses found so far. 55 target := make([]*Block, f.NumValues()) 56 57 // Grab loop information. 58 // We use this to make sure we don't tighten a value into a (deeper) loop. 59 idom := f.Idom() 60 loops := f.loopnest() 61 loops.calculateDepths() 62 63 changed := true 64 for changed { 65 changed = false 66 67 // Reset target 68 for i := range target { 69 target[i] = nil 70 } 71 72 // Compute target locations (for moveable values only). 73 // target location = the least common ancestor of all uses in the dominator tree. 74 for _, b := range f.Blocks { 75 for _, v := range b.Values { 76 for i, a := range v.Args { 77 if !canMove[a.ID] { 78 continue 79 } 80 use := b 81 if v.Op == OpPhi { 82 use = b.Preds[i].b 83 } 84 if target[a.ID] == nil { 85 target[a.ID] = use 86 } else { 87 target[a.ID] = lca.find(target[a.ID], use) 88 } 89 } 90 } 91 for _, c := range b.ControlValues() { 92 if !canMove[c.ID] { 93 continue 94 } 95 if target[c.ID] == nil { 96 target[c.ID] = b 97 } else { 98 target[c.ID] = lca.find(target[c.ID], b) 99 } 100 } 101 } 102 103 // If the target location is inside a loop, 104 // move the target location up to just before the loop head. 105 for _, b := range f.Blocks { 106 origloop := loops.b2l[b.ID] 107 for _, v := range b.Values { 108 t := target[v.ID] 109 if t == nil { 110 continue 111 } 112 targetloop := loops.b2l[t.ID] 113 for targetloop != nil && (origloop == nil || targetloop.depth > origloop.depth) { 114 t = idom[targetloop.header.ID] 115 target[v.ID] = t 116 targetloop = loops.b2l[t.ID] 117 } 118 } 119 } 120 121 // Move values to target locations. 122 for _, b := range f.Blocks { 123 for i := 0; i < len(b.Values); i++ { 124 v := b.Values[i] 125 t := target[v.ID] 126 if t == nil || t == b { 127 // v is not moveable, or is already in correct place. 128 continue 129 } 130 // Move v to the block which dominates its uses. 131 t.Values = append(t.Values, v) 132 v.Block = t 133 last := len(b.Values) - 1 134 b.Values[i] = b.Values[last] 135 b.Values[last] = nil 136 b.Values = b.Values[:last] 137 changed = true 138 i-- 139 } 140 } 141 } 142} 143 144// phiTighten moves constants closer to phi users. 145// This pass avoids having lots of constants live for lots of the program. 146// See issue 16407. 147func phiTighten(f *Func) { 148 for _, b := range f.Blocks { 149 for _, v := range b.Values { 150 if v.Op != OpPhi { 151 continue 152 } 153 for i, a := range v.Args { 154 if !a.rematerializeable() { 155 continue // not a constant we can move around 156 } 157 if a.Block == b.Preds[i].b { 158 continue // already in the right place 159 } 160 // Make a copy of a, put in predecessor block. 161 v.SetArg(i, a.copyInto(b.Preds[i].b)) 162 } 163 } 164 } 165} 166