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 import ( 8 "cmd/internal/src" 9 ) 10 11 // fusePlain runs fuse(f, fuseTypePlain). 12 func fusePlain(f *Func) { fuse(f, fuseTypePlain) } 13 14 // fuseAll runs fuse(f, fuseTypeAll). 15 func fuseAll(f *Func) { fuse(f, fuseTypeAll) } 16 17 type fuseType uint8 18 19 const ( 20 fuseTypePlain fuseType = 1 << iota 21 fuseTypeIf 22 fuseTypeAll = fuseTypePlain | fuseTypeIf 23 ) 24 25 // fuse simplifies control flow by joining basic blocks. 26 func fuse(f *Func, typ fuseType) { 27 for changed := true; changed; { 28 changed = false 29 // Fuse from end to beginning, to avoid quadratic behavior in fuseBlockPlain. See issue 13554. 30 for i := len(f.Blocks) - 1; i >= 0; i-- { 31 b := f.Blocks[i] 32 if typ&fuseTypeIf != 0 { 33 changed = fuseBlockIf(b) || changed 34 } 35 if typ&fuseTypePlain != 0 { 36 changed = fuseBlockPlain(b) || changed 37 } 38 } 39 if changed { 40 f.invalidateCFG() 41 } 42 } 43 } 44 45 // fuseBlockIf handles the following cases where s0 and s1 are empty blocks. 46 // 47 // b b b b 48 // / \ | \ / | | | 49 // s0 s1 | s1 s0 | | | 50 // \ / | / \ | | | 51 // ss ss ss ss 52 // 53 // If all Phi ops in ss have identical variables for slots corresponding to 54 // s0, s1 and b then the branch can be dropped. 55 // This optimization often comes up in switch statements with multiple 56 // expressions in a case clause: 57 // switch n { 58 // case 1,2,3: return 4 59 // } 60 // TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway. 61 func fuseBlockIf(b *Block) bool { 62 if b.Kind != BlockIf { 63 return false 64 } 65 66 var ss0, ss1 *Block 67 s0 := b.Succs[0].b 68 i0 := b.Succs[0].i 69 if s0.Kind != BlockPlain || len(s0.Preds) != 1 || !isEmpty(s0) { 70 s0, ss0 = b, s0 71 } else { 72 ss0 = s0.Succs[0].b 73 i0 = s0.Succs[0].i 74 } 75 s1 := b.Succs[1].b 76 i1 := b.Succs[1].i 77 if s1.Kind != BlockPlain || len(s1.Preds) != 1 || !isEmpty(s1) { 78 s1, ss1 = b, s1 79 } else { 80 ss1 = s1.Succs[0].b 81 i1 = s1.Succs[0].i 82 } 83 84 if ss0 != ss1 { 85 return false 86 } 87 ss := ss0 88 89 // s0 and s1 are equal with b if the corresponding block is missing 90 // (2nd, 3rd and 4th case in the figure). 91 92 for _, v := range ss.Values { 93 if v.Op == OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] { 94 return false 95 } 96 } 97 98 // Now we have two of following b->ss, b->s0->ss and b->s1->ss, 99 // with s0 and s1 empty if exist. 100 // We can replace it with b->ss without if all OpPhis in ss 101 // have identical predecessors (verified above). 102 // No critical edge is introduced because b will have one successor. 103 if s0 != b && s1 != b { 104 // Replace edge b->s0->ss with b->ss. 105 // We need to keep a slot for Phis corresponding to b. 106 b.Succs[0] = Edge{ss, i0} 107 ss.Preds[i0] = Edge{b, 0} 108 b.removeEdge(1) 109 s1.removeEdge(0) 110 } else if s0 != b { 111 b.removeEdge(0) 112 s0.removeEdge(0) 113 } else if s1 != b { 114 b.removeEdge(1) 115 s1.removeEdge(0) 116 } else { 117 b.removeEdge(1) 118 } 119 b.Kind = BlockPlain 120 b.Likely = BranchUnknown 121 b.SetControl(nil) 122 123 // Trash the empty blocks s0 and s1. 124 blocks := [...]*Block{s0, s1} 125 for _, s := range &blocks { 126 if s == b { 127 continue 128 } 129 // Move any (dead) values in s0 or s1 to b, 130 // where they will be eliminated by the next deadcode pass. 131 for _, v := range s.Values { 132 v.Block = b 133 } 134 b.Values = append(b.Values, s.Values...) 135 // Clear s. 136 s.Kind = BlockInvalid 137 s.Values = nil 138 s.Succs = nil 139 s.Preds = nil 140 } 141 return true 142 } 143 144 // isEmpty reports whether b contains any live values. 145 // There may be false positives. 146 func isEmpty(b *Block) bool { 147 for _, v := range b.Values { 148 if v.Uses > 0 || v.Type.IsVoid() { 149 return false 150 } 151 } 152 return true 153 } 154 155 func fuseBlockPlain(b *Block) bool { 156 if b.Kind != BlockPlain { 157 return false 158 } 159 160 c := b.Succs[0].b 161 if len(c.Preds) != 1 { 162 return false 163 } 164 165 // If a block happened to end in a statement marker, 166 // try to preserve it. 167 if b.Pos.IsStmt() == src.PosIsStmt { 168 l := b.Pos.Line() 169 for _, v := range c.Values { 170 if v.Pos.IsStmt() == src.PosNotStmt { 171 continue 172 } 173 if l == v.Pos.Line() { 174 v.Pos = v.Pos.WithIsStmt() 175 l = 0 176 break 177 } 178 } 179 if l != 0 && c.Pos.Line() == l { 180 c.Pos = c.Pos.WithIsStmt() 181 } 182 } 183 184 // move all of b's values to c. 185 for _, v := range b.Values { 186 v.Block = c 187 } 188 // Use whichever value slice is larger, in the hopes of avoiding growth. 189 // However, take care to avoid c.Values pointing to b.valstorage. 190 // See golang.org/issue/18602. 191 // It's important to keep the elements in the same order; maintenance of 192 // debugging information depends on the order of *Values in Blocks. 193 // This can also cause changes in the order (which may affect other 194 // optimizations and possibly compiler output) for 32-vs-64 bit compilation 195 // platforms (word size affects allocation bucket size affects slice capacity). 196 if cap(c.Values) >= cap(b.Values) || len(b.Values) <= len(b.valstorage) { 197 bl := len(b.Values) 198 cl := len(c.Values) 199 var t []*Value // construct t = b.Values followed-by c.Values, but with attention to allocation. 200 if cap(c.Values) < bl+cl { 201 // reallocate 202 t = make([]*Value, bl+cl) 203 } else { 204 // in place. 205 t = c.Values[0 : bl+cl] 206 } 207 copy(t[bl:], c.Values) // possibly in-place 208 c.Values = t 209 copy(c.Values, b.Values) 210 } else { 211 c.Values = append(b.Values, c.Values...) 212 } 213 214 // replace b->c edge with preds(b) -> c 215 c.predstorage[0] = Edge{} 216 if len(b.Preds) > len(b.predstorage) { 217 c.Preds = b.Preds 218 } else { 219 c.Preds = append(c.predstorage[:0], b.Preds...) 220 } 221 for i, e := range c.Preds { 222 p := e.b 223 p.Succs[e.i] = Edge{c, i} 224 } 225 f := b.Func 226 if f.Entry == b { 227 f.Entry = c 228 } 229 230 // trash b, just in case 231 b.Kind = BlockInvalid 232 b.Values = nil 233 b.Preds = nil 234 b.Succs = nil 235 return true 236 } 237
View as plain text