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 7import ( 8 "cmd/compile/internal/types" 9) 10 11// decompose converts phi ops on compound builtin types into phi 12// ops on simple types, then invokes rewrite rules to decompose 13// other ops on those types. 14func decomposeBuiltIn(f *Func) { 15 // Decompose phis 16 for _, b := range f.Blocks { 17 for _, v := range b.Values { 18 if v.Op != OpPhi { 19 continue 20 } 21 decomposeBuiltInPhi(v) 22 } 23 } 24 25 // Decompose other values 26 applyRewrite(f, rewriteBlockdec, rewriteValuedec) 27 if f.Config.RegSize == 4 { 28 applyRewrite(f, rewriteBlockdec64, rewriteValuedec64) 29 } 30 31 // Split up named values into their components. 32 var newNames []LocalSlot 33 for _, name := range f.Names { 34 t := name.Type 35 switch { 36 case t.IsInteger() && t.Size() > f.Config.RegSize: 37 hiName, loName := f.fe.SplitInt64(name) 38 newNames = append(newNames, hiName, loName) 39 for _, v := range f.NamedValues[name] { 40 if v.Op != OpInt64Make { 41 continue 42 } 43 f.NamedValues[hiName] = append(f.NamedValues[hiName], v.Args[0]) 44 f.NamedValues[loName] = append(f.NamedValues[loName], v.Args[1]) 45 } 46 delete(f.NamedValues, name) 47 case t.IsComplex(): 48 rName, iName := f.fe.SplitComplex(name) 49 newNames = append(newNames, rName, iName) 50 for _, v := range f.NamedValues[name] { 51 if v.Op != OpComplexMake { 52 continue 53 } 54 f.NamedValues[rName] = append(f.NamedValues[rName], v.Args[0]) 55 f.NamedValues[iName] = append(f.NamedValues[iName], v.Args[1]) 56 57 } 58 delete(f.NamedValues, name) 59 case t.IsString(): 60 ptrName, lenName := f.fe.SplitString(name) 61 newNames = append(newNames, ptrName, lenName) 62 for _, v := range f.NamedValues[name] { 63 if v.Op != OpStringMake { 64 continue 65 } 66 f.NamedValues[ptrName] = append(f.NamedValues[ptrName], v.Args[0]) 67 f.NamedValues[lenName] = append(f.NamedValues[lenName], v.Args[1]) 68 } 69 delete(f.NamedValues, name) 70 case t.IsSlice(): 71 ptrName, lenName, capName := f.fe.SplitSlice(name) 72 newNames = append(newNames, ptrName, lenName, capName) 73 for _, v := range f.NamedValues[name] { 74 if v.Op != OpSliceMake { 75 continue 76 } 77 f.NamedValues[ptrName] = append(f.NamedValues[ptrName], v.Args[0]) 78 f.NamedValues[lenName] = append(f.NamedValues[lenName], v.Args[1]) 79 f.NamedValues[capName] = append(f.NamedValues[capName], v.Args[2]) 80 } 81 delete(f.NamedValues, name) 82 case t.IsInterface(): 83 typeName, dataName := f.fe.SplitInterface(name) 84 newNames = append(newNames, typeName, dataName) 85 for _, v := range f.NamedValues[name] { 86 if v.Op != OpIMake { 87 continue 88 } 89 f.NamedValues[typeName] = append(f.NamedValues[typeName], v.Args[0]) 90 f.NamedValues[dataName] = append(f.NamedValues[dataName], v.Args[1]) 91 } 92 delete(f.NamedValues, name) 93 case t.IsFloat(): 94 // floats are never decomposed, even ones bigger than RegSize 95 newNames = append(newNames, name) 96 case t.Size() > f.Config.RegSize: 97 f.Fatalf("undecomposed named type %s %v", name, t) 98 default: 99 newNames = append(newNames, name) 100 } 101 } 102 f.Names = newNames 103} 104 105func decomposeBuiltInPhi(v *Value) { 106 switch { 107 case v.Type.IsInteger() && v.Type.Size() > v.Block.Func.Config.RegSize: 108 decomposeInt64Phi(v) 109 case v.Type.IsComplex(): 110 decomposeComplexPhi(v) 111 case v.Type.IsString(): 112 decomposeStringPhi(v) 113 case v.Type.IsSlice(): 114 decomposeSlicePhi(v) 115 case v.Type.IsInterface(): 116 decomposeInterfacePhi(v) 117 case v.Type.IsFloat(): 118 // floats are never decomposed, even ones bigger than RegSize 119 case v.Type.Size() > v.Block.Func.Config.RegSize: 120 v.Fatalf("undecomposed type %s", v.Type) 121 } 122} 123 124func decomposeStringPhi(v *Value) { 125 types := &v.Block.Func.Config.Types 126 ptrType := types.BytePtr 127 lenType := types.Int 128 129 ptr := v.Block.NewValue0(v.Pos, OpPhi, ptrType) 130 len := v.Block.NewValue0(v.Pos, OpPhi, lenType) 131 for _, a := range v.Args { 132 ptr.AddArg(a.Block.NewValue1(v.Pos, OpStringPtr, ptrType, a)) 133 len.AddArg(a.Block.NewValue1(v.Pos, OpStringLen, lenType, a)) 134 } 135 v.reset(OpStringMake) 136 v.AddArg(ptr) 137 v.AddArg(len) 138} 139 140func decomposeSlicePhi(v *Value) { 141 types := &v.Block.Func.Config.Types 142 ptrType := types.BytePtr 143 lenType := types.Int 144 145 ptr := v.Block.NewValue0(v.Pos, OpPhi, ptrType) 146 len := v.Block.NewValue0(v.Pos, OpPhi, lenType) 147 cap := v.Block.NewValue0(v.Pos, OpPhi, lenType) 148 for _, a := range v.Args { 149 ptr.AddArg(a.Block.NewValue1(v.Pos, OpSlicePtr, ptrType, a)) 150 len.AddArg(a.Block.NewValue1(v.Pos, OpSliceLen, lenType, a)) 151 cap.AddArg(a.Block.NewValue1(v.Pos, OpSliceCap, lenType, a)) 152 } 153 v.reset(OpSliceMake) 154 v.AddArg(ptr) 155 v.AddArg(len) 156 v.AddArg(cap) 157} 158 159func decomposeInt64Phi(v *Value) { 160 cfgtypes := &v.Block.Func.Config.Types 161 var partType *types.Type 162 if v.Type.IsSigned() { 163 partType = cfgtypes.Int32 164 } else { 165 partType = cfgtypes.UInt32 166 } 167 168 hi := v.Block.NewValue0(v.Pos, OpPhi, partType) 169 lo := v.Block.NewValue0(v.Pos, OpPhi, cfgtypes.UInt32) 170 for _, a := range v.Args { 171 hi.AddArg(a.Block.NewValue1(v.Pos, OpInt64Hi, partType, a)) 172 lo.AddArg(a.Block.NewValue1(v.Pos, OpInt64Lo, cfgtypes.UInt32, a)) 173 } 174 v.reset(OpInt64Make) 175 v.AddArg(hi) 176 v.AddArg(lo) 177} 178 179func decomposeComplexPhi(v *Value) { 180 cfgtypes := &v.Block.Func.Config.Types 181 var partType *types.Type 182 switch z := v.Type.Size(); z { 183 case 8: 184 partType = cfgtypes.Float32 185 case 16: 186 partType = cfgtypes.Float64 187 default: 188 v.Fatalf("decomposeComplexPhi: bad complex size %d", z) 189 } 190 191 real := v.Block.NewValue0(v.Pos, OpPhi, partType) 192 imag := v.Block.NewValue0(v.Pos, OpPhi, partType) 193 for _, a := range v.Args { 194 real.AddArg(a.Block.NewValue1(v.Pos, OpComplexReal, partType, a)) 195 imag.AddArg(a.Block.NewValue1(v.Pos, OpComplexImag, partType, a)) 196 } 197 v.reset(OpComplexMake) 198 v.AddArg(real) 199 v.AddArg(imag) 200} 201 202func decomposeInterfacePhi(v *Value) { 203 uintptrType := v.Block.Func.Config.Types.Uintptr 204 ptrType := v.Block.Func.Config.Types.BytePtr 205 206 itab := v.Block.NewValue0(v.Pos, OpPhi, uintptrType) 207 data := v.Block.NewValue0(v.Pos, OpPhi, ptrType) 208 for _, a := range v.Args { 209 itab.AddArg(a.Block.NewValue1(v.Pos, OpITab, uintptrType, a)) 210 data.AddArg(a.Block.NewValue1(v.Pos, OpIData, ptrType, a)) 211 } 212 v.reset(OpIMake) 213 v.AddArg(itab) 214 v.AddArg(data) 215} 216 217func decomposeArgs(f *Func) { 218 applyRewrite(f, rewriteBlockdecArgs, rewriteValuedecArgs) 219} 220 221func decomposeUser(f *Func) { 222 for _, b := range f.Blocks { 223 for _, v := range b.Values { 224 if v.Op != OpPhi { 225 continue 226 } 227 decomposeUserPhi(v) 228 } 229 } 230 // Split up named values into their components. 231 i := 0 232 var newNames []LocalSlot 233 for _, name := range f.Names { 234 t := name.Type 235 switch { 236 case t.IsStruct(): 237 newNames = decomposeUserStructInto(f, name, newNames) 238 case t.IsArray(): 239 newNames = decomposeUserArrayInto(f, name, newNames) 240 default: 241 f.Names[i] = name 242 i++ 243 } 244 } 245 f.Names = f.Names[:i] 246 f.Names = append(f.Names, newNames...) 247} 248 249// decomposeUserArrayInto creates names for the element(s) of arrays referenced 250// by name where possible, and appends those new names to slots, which is then 251// returned. 252func decomposeUserArrayInto(f *Func, name LocalSlot, slots []LocalSlot) []LocalSlot { 253 t := name.Type 254 if t.NumElem() == 0 { 255 // TODO(khr): Not sure what to do here. Probably nothing. 256 // Names for empty arrays aren't important. 257 return slots 258 } 259 if t.NumElem() != 1 { 260 // shouldn't get here due to CanSSA 261 f.Fatalf("array not of size 1") 262 } 263 elemName := f.fe.SplitArray(name) 264 for _, v := range f.NamedValues[name] { 265 if v.Op != OpArrayMake1 { 266 continue 267 } 268 f.NamedValues[elemName] = append(f.NamedValues[elemName], v.Args[0]) 269 } 270 // delete the name for the array as a whole 271 delete(f.NamedValues, name) 272 273 if t.Elem().IsArray() { 274 return decomposeUserArrayInto(f, elemName, slots) 275 } else if t.Elem().IsStruct() { 276 return decomposeUserStructInto(f, elemName, slots) 277 } 278 279 return append(slots, elemName) 280} 281 282// decomposeUserStructInto creates names for the fields(s) of structs referenced 283// by name where possible, and appends those new names to slots, which is then 284// returned. 285func decomposeUserStructInto(f *Func, name LocalSlot, slots []LocalSlot) []LocalSlot { 286 fnames := []LocalSlot{} // slots for struct in name 287 t := name.Type 288 n := t.NumFields() 289 290 for i := 0; i < n; i++ { 291 fs := f.fe.SplitStruct(name, i) 292 fnames = append(fnames, fs) 293 // arrays and structs will be decomposed further, so 294 // there's no need to record a name 295 if !fs.Type.IsArray() && !fs.Type.IsStruct() { 296 slots = append(slots, fs) 297 } 298 } 299 300 makeOp := StructMakeOp(n) 301 // create named values for each struct field 302 for _, v := range f.NamedValues[name] { 303 if v.Op != makeOp { 304 continue 305 } 306 for i := 0; i < len(fnames); i++ { 307 f.NamedValues[fnames[i]] = append(f.NamedValues[fnames[i]], v.Args[i]) 308 } 309 } 310 // remove the name of the struct as a whole 311 delete(f.NamedValues, name) 312 313 // now that this f.NamedValues contains values for the struct 314 // fields, recurse into nested structs 315 for i := 0; i < n; i++ { 316 if name.Type.FieldType(i).IsStruct() { 317 slots = decomposeUserStructInto(f, fnames[i], slots) 318 delete(f.NamedValues, fnames[i]) 319 } else if name.Type.FieldType(i).IsArray() { 320 slots = decomposeUserArrayInto(f, fnames[i], slots) 321 delete(f.NamedValues, fnames[i]) 322 } 323 } 324 return slots 325} 326func decomposeUserPhi(v *Value) { 327 switch { 328 case v.Type.IsStruct(): 329 decomposeStructPhi(v) 330 case v.Type.IsArray(): 331 decomposeArrayPhi(v) 332 } 333} 334 335// decomposeStructPhi replaces phi-of-struct with structmake(phi-for-each-field), 336// and then recursively decomposes the phis for each field. 337func decomposeStructPhi(v *Value) { 338 t := v.Type 339 n := t.NumFields() 340 var fields [MaxStruct]*Value 341 for i := 0; i < n; i++ { 342 fields[i] = v.Block.NewValue0(v.Pos, OpPhi, t.FieldType(i)) 343 } 344 for _, a := range v.Args { 345 for i := 0; i < n; i++ { 346 fields[i].AddArg(a.Block.NewValue1I(v.Pos, OpStructSelect, t.FieldType(i), int64(i), a)) 347 } 348 } 349 v.reset(StructMakeOp(n)) 350 v.AddArgs(fields[:n]...) 351 352 // Recursively decompose phis for each field. 353 for _, f := range fields[:n] { 354 decomposeUserPhi(f) 355 } 356} 357 358// decomposeArrayPhi replaces phi-of-array with arraymake(phi-of-array-element), 359// and then recursively decomposes the element phi. 360func decomposeArrayPhi(v *Value) { 361 t := v.Type 362 if t.NumElem() == 0 { 363 v.reset(OpArrayMake0) 364 return 365 } 366 if t.NumElem() != 1 { 367 v.Fatalf("SSAable array must have no more than 1 element") 368 } 369 elem := v.Block.NewValue0(v.Pos, OpPhi, t.Elem()) 370 for _, a := range v.Args { 371 elem.AddArg(a.Block.NewValue1I(v.Pos, OpArraySelect, t.Elem(), 0, a)) 372 } 373 v.reset(OpArrayMake1) 374 v.AddArg(elem) 375 376 // Recursively decompose elem phi. 377 decomposeUserPhi(elem) 378} 379 380// MaxStruct is the maximum number of fields a struct 381// can have and still be SSAable. 382const MaxStruct = 4 383 384// StructMakeOp returns the opcode to construct a struct with the 385// given number of fields. 386func StructMakeOp(nf int) Op { 387 switch nf { 388 case 0: 389 return OpStructMake0 390 case 1: 391 return OpStructMake1 392 case 2: 393 return OpStructMake2 394 case 3: 395 return OpStructMake3 396 case 4: 397 return OpStructMake4 398 } 399 panic("too many fields in an SSAable struct") 400} 401