Source file src/pkg/cmd/compile/internal/ssa/decompose.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	package ssa
     6	
     7	import (
     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.
    14	func 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	
   105	func 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	
   124	func 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	
   140	func 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	
   159	func 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	
   179	func 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	
   202	func 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	
   217	func decomposeArgs(f *Func) {
   218		applyRewrite(f, rewriteBlockdecArgs, rewriteValuedecArgs)
   219	}
   220	
   221	func 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.
   252	func 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.
   285	func 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	}
   326	func 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.
   337	func 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.
   360	func 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.
   382	const MaxStruct = 4
   383	
   384	// StructMakeOp returns the opcode to construct a struct with the
   385	// given number of fields.
   386	func 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	

View as plain text