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 package 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. 12 func tighten(f *Func) { 13 canMove := make([]bool, f.NumValues()) 14 for _, b := range f.Blocks { 15 for _, v := range b.Values { 16 switch v.Op { 17 case OpPhi, OpGetClosurePtr, OpArg, OpSelect0, OpSelect1: 18 // Phis need to stay in their block. 19 // GetClosurePtr & Arg must stay in the entry block. 20 // Tuple selectors must stay with the tuple generator. 21 continue 22 } 23 if len(v.Args) > 0 && v.Args[len(v.Args)-1].Type.IsMemory() { 24 // We can't move values which have a memory arg - it might 25 // make two memory values live across a block boundary. 26 continue 27 } 28 // Count arguments which will need a register. 29 narg := 0 30 for _, a := range v.Args { 31 switch a.Op { 32 case OpConst8, OpConst16, OpConst32, OpConst64, OpAddr: 33 // Probably foldable into v, don't count as an argument needing a register. 34 // TODO: move tighten to a machine-dependent phase and use v.rematerializeable()? 35 default: 36 narg++ 37 } 38 } 39 if narg >= 2 && !v.Type.IsBoolean() { 40 // Don't move values with more than one input, as that may 41 // increase register pressure. 42 // We make an exception for boolean-typed values, as they will 43 // likely be converted to flags, and 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 if c := b.Control; c != nil { 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. 147 func 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