src/cmd/compile/internal/ssa/expand_calls.go

   1 // Copyright 2020 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/abi"
   9         "cmd/compile/internal/base"
  10         "cmd/compile/internal/ir"
  11         "cmd/compile/internal/types"
  12         "cmd/internal/src"
  13         "fmt"
  14 )
  15
  16 func postExpandCallsDecompose(f *Func) {
  17         decomposeUser(f)    // redo user decompose to cleanup after expand calls
  18         decomposeBuiltIn(f) // handles both regular decomposition and cleanup.
  19 }
  20
  21 func expandCalls(f *Func) {
  22         // Convert each aggregate arg to a call into "dismantle aggregate, store/pass parts"
  23         // Convert each aggregate result from a call into "assemble aggregate from parts"
  24         // Convert each multivalue exit into "dismantle aggregate, store/return parts"
  25         // Convert incoming aggregate arg into assembly of parts.
  26         // Feed modified AST to decompose.
  27
  28         sp, _ := f.spSb()
  29
  30         x := &expandState{
  31                 f:               f,
  32                 debug:           f.pass.debug,
  33                 regSize:         f.Config.RegSize,
  34                 sp:              sp,
  35                 typs:            &f.Config.Types,
  36                 wideSelects:     make(map[*Value]*Value),
  37                 commonArgs:      make(map[selKey]*Value),
  38                 commonSelectors: make(map[selKey]*Value),
  39                 memForCall:      make(map[ID]*Value),
  40         }
  41
  42         // For 32-bit, need to deal with decomposition of 64-bit integers, which depends on endianness.
  43         if f.Config.BigEndian {
  44                 x.firstOp = OpInt64Hi
  45                 x.secondOp = OpInt64Lo
  46                 x.firstType = x.typs.Int32
  47                 x.secondType = x.typs.UInt32
  48         } else {
  49                 x.firstOp = OpInt64Lo
  50                 x.secondOp = OpInt64Hi
  51                 x.firstType = x.typs.UInt32
  52                 x.secondType = x.typs.Int32
  53         }
  54
  55         // Defer select processing until after all calls and selects are seen.
  56         var selects []*Value
  57         var calls []*Value
  58         var args []*Value
  59         var exitBlocks []*Block
  60
  61         var m0 *Value
  62
  63         // Accumulate lists of calls, args, selects, and exit blocks to process,
  64         // note "wide" selects consumed by stores,
  65         // rewrite mem for each call,
  66         // rewrite each OpSelectNAddr.
  67         for _, b := range f.Blocks {
  68                 for _, v := range b.Values {
  69                         switch v.Op {
  70                         case OpInitMem:
  71                                 m0 = v
  72
  73                         case OpClosureLECall, OpInterLECall, OpStaticLECall, OpTailLECall:
  74                                 calls = append(calls, v)
  75
  76                         case OpArg:
  77                                 args = append(args, v)
  78
  79                         case OpStore:
  80                                 if a := v.Args[1]; a.Op == OpSelectN && !CanSSA(a.Type) {
  81                                         if a.Uses > 1 {
  82                                                 panic(fmt.Errorf("Saw double use of wide SelectN %s operand of Store %s",
  83                                                         a.LongString(), v.LongString()))
  84                                         }
  85                                         x.wideSelects[a] = v
  86                                 }
  87
  88                         case OpSelectN:
  89                                 if v.Type == types.TypeMem {
  90                                         // rewrite the mem selector in place
  91                                         call := v.Args[0]
  92                                         aux := call.Aux.(*AuxCall)
  93                                         mem := x.memForCall[call.ID]
  94                                         if mem == nil {
  95                                                 v.AuxInt = int64(aux.abiInfo.OutRegistersUsed())
  96                                                 x.memForCall[call.ID] = v
  97                                         } else {
  98                                                 panic(fmt.Errorf("Saw two memories for call %v, %v and %v", call, mem, v))
  99                                         }
 100                                 } else {
 101                                         selects = append(selects, v)
 102                                 }
 103
 104                         case OpSelectNAddr:
 105                                 call := v.Args[0]
 106                                 which := v.AuxInt
 107                                 aux := call.Aux.(*AuxCall)
 108                                 pt := v.Type
 109                                 off := x.offsetFrom(x.f.Entry, x.sp, aux.OffsetOfResult(which), pt)
 110                                 v.copyOf(off)
 111                         }
 112                 }
 113
 114                 // rewrite function results from an exit block
 115                 // values returned by function need to be split out into registers.
 116                 if isBlockMultiValueExit(b) {
 117                         exitBlocks = append(exitBlocks, b)
 118                 }
 119         }
 120
 121         // Convert each aggregate arg into Make of its parts (and so on, to primitive types)
 122         for _, v := range args {
 123                 var rc registerCursor
 124                 a := x.prAssignForArg(v)
 125                 aux := x.f.OwnAux
 126                 regs := a.Registers
 127                 var offset int64
 128                 if len(regs) == 0 {
 129                         offset = a.FrameOffset(aux.abiInfo)
 130                 }
 131                 auxBase := x.offsetFrom(x.f.Entry, x.sp, offset, types.NewPtr(v.Type))
 132                 rc.init(regs, aux.abiInfo, nil, auxBase, 0)
 133                 x.rewriteSelectOrArg(f.Entry.Pos, f.Entry, v, v, m0, v.Type, rc)
 134         }
 135
 136         // Rewrite selects of results (which may be aggregates) into make-aggregates of register/memory-targeted selects
 137         for _, v := range selects {
 138                 if v.Op == OpInvalid {
 139                         continue
 140                 }
 141
 142                 call := v.Args[0]
 143                 aux := call.Aux.(*AuxCall)
 144                 mem := x.memForCall[call.ID]
 145                 if mem == nil {
 146                         mem = call.Block.NewValue1I(call.Pos, OpSelectN, types.TypeMem, int64(aux.abiInfo.OutRegistersUsed()), call)
 147                         x.memForCall[call.ID] = mem
 148                 }
 149
 150                 i := v.AuxInt
 151                 regs := aux.RegsOfResult(i)
 152
 153                 // If this select cannot fit into SSA and is stored, either disaggregate to register stores, or mem-mem move.
 154                 if store := x.wideSelects[v]; store != nil {
 155                         // Use the mem that comes from the store operation.
 156                         storeAddr := store.Args[0]
 157                         mem := store.Args[2]
 158                         if len(regs) > 0 {
 159                                 // Cannot do a rewrite that builds up a result from pieces; instead, copy pieces to the store operation.
 160                                 var rc registerCursor
 161                                 rc.init(regs, aux.abiInfo, nil, storeAddr, 0)
 162                                 mem = x.rewriteWideSelectToStores(call.Pos, call.Block, v, mem, v.Type, rc)
 163                                 store.copyOf(mem)
 164                         } else {
 165                                 // Move directly from AuxBase to store target; rewrite the store instruction.
 166                                 offset := aux.OffsetOfResult(i)
 167                                 auxBase := x.offsetFrom(x.f.Entry, x.sp, offset, types.NewPtr(v.Type))
 168                                 // was Store dst, v, mem
 169                                 // now Move dst, auxBase, mem
 170                                 move := store.Block.NewValue3A(store.Pos, OpMove, types.TypeMem, v.Type, storeAddr, auxBase, mem)
 171                                 move.AuxInt = v.Type.Size()
 172                                 store.copyOf(move)
 173                         }
 174                         continue
 175                 }
 176
 177                 var auxBase *Value
 178                 if len(regs) == 0 {
 179                         offset := aux.OffsetOfResult(i)
 180                         auxBase = x.offsetFrom(x.f.Entry, x.sp, offset, types.NewPtr(v.Type))
 181                 }
 182                 var rc registerCursor
 183                 rc.init(regs, aux.abiInfo, nil, auxBase, 0)
 184                 x.rewriteSelectOrArg(call.Pos, call.Block, v, v, mem, v.Type, rc)
 185         }
 186
 187         rewriteCall := func(v *Value, newOp Op, argStart int) {
 188                 // Break aggregate args passed to call into smaller pieces.
 189                 x.rewriteCallArgs(v, argStart)
 190                 v.Op = newOp
 191                 rts := abi.RegisterTypes(v.Aux.(*AuxCall).abiInfo.OutParams())
 192                 v.Type = types.NewResults(append(rts, types.TypeMem))
 193         }
 194
 195         // Rewrite calls
 196         for _, v := range calls {
 197                 switch v.Op {
 198                 case OpStaticLECall:
 199                         rewriteCall(v, OpStaticCall, 0)
 200                 case OpTailLECall:
 201                         rewriteCall(v, OpTailCall, 0)
 202                 case OpClosureLECall:
 203                         rewriteCall(v, OpClosureCall, 2)
 204                 case OpInterLECall:
 205                         rewriteCall(v, OpInterCall, 1)
 206                 }
 207         }
 208
 209         // Rewrite results from exit blocks
 210         for _, b := range exitBlocks {
 211                 v := b.Controls[0]
 212                 x.rewriteFuncResults(v, b, f.OwnAux)
 213                 b.SetControl(v)
 214         }
 215
 216 }
 217
 218 func (x *expandState) rewriteFuncResults(v *Value, b *Block, aux *AuxCall) {
 219         // This is very similar to rewriteCallArgs
 220         // differences:
 221         // firstArg + preArgs
 222         // sp vs auxBase
 223
 224         m0 := v.MemoryArg()
 225         mem := m0
 226
 227         allResults := []*Value{}
 228         var oldArgs []*Value
 229         argsWithoutMem := v.Args[:len(v.Args)-1]
 230
 231         for j, a := range argsWithoutMem {
 232                 oldArgs = append(oldArgs, a)
 233                 i := int64(j)
 234                 auxType := aux.TypeOfResult(i)
 235                 auxBase := b.NewValue2A(v.Pos, OpLocalAddr, types.NewPtr(auxType), aux.NameOfResult(i), x.sp, mem)
 236                 auxOffset := int64(0)
 237                 aRegs := aux.RegsOfResult(int64(j))
 238                 if a.Op == OpDereference {
 239                         a.Op = OpLoad
 240                 }
 241                 var rc registerCursor
 242                 var result *[]*Value
 243                 if len(aRegs) > 0 {
 244                         result = &allResults
 245                 } else {
 246                         if a.Op == OpLoad && a.Args[0].Op == OpLocalAddr {
 247                                 addr := a.Args[0]
 248                                 if addr.MemoryArg() == a.MemoryArg() && addr.Aux == aux.NameOfResult(i) {
 249                                         continue // Self move to output parameter
 250                                 }
 251                         }
 252                 }
 253                 rc.init(aRegs, aux.abiInfo, result, auxBase, auxOffset)
 254                 mem = x.decomposeAsNecessary(v.Pos, b, a, mem, rc)
 255         }
 256         v.resetArgs()
 257         v.AddArgs(allResults...)
 258         v.AddArg(mem)
 259         for _, a := range oldArgs {
 260                 if a.Uses == 0 {
 261                         if x.debug > 1 {
 262                                 x.Printf("...marking %v unused\n", a.LongString())
 263                         }
 264                         x.invalidateRecursively(a)
 265                 }
 266         }
 267         v.Type = types.NewResults(append(abi.RegisterTypes(aux.abiInfo.OutParams()), types.TypeMem))
 268         return
 269 }
 270
 271 func (x *expandState) rewriteCallArgs(v *Value, firstArg int) {
 272         if x.debug > 1 {
 273                 x.indent(3)
 274                 defer x.indent(-3)
 275                 x.Printf("rewriteCallArgs(%s; %d)\n", v.LongString(), firstArg)
 276         }
 277         // Thread the stores on the memory arg
 278         aux := v.Aux.(*AuxCall)
 279         m0 := v.MemoryArg()
 280         mem := m0
 281         allResults := []*Value{}
 282         oldArgs := []*Value{}
 283         argsWithoutMem := v.Args[firstArg : len(v.Args)-1] // Also strip closure/interface Op-specific args
 284
 285         sp := x.sp
 286         if v.Op == OpTailLECall {
 287                 // For tail call, we unwind the frame before the call so we'll use the caller's
 288                 // SP.
 289                 sp = x.f.Entry.NewValue1(src.NoXPos, OpGetCallerSP, x.typs.Uintptr, mem)
 290         }
 291
 292         for i, a := range argsWithoutMem { // skip leading non-parameter SSA Args and trailing mem SSA Arg.
 293                 oldArgs = append(oldArgs, a)
 294                 auxI := int64(i)
 295                 aRegs := aux.RegsOfArg(auxI)
 296                 aType := aux.TypeOfArg(auxI)
 297
 298                 if a.Op == OpDereference {
 299                         a.Op = OpLoad
 300                 }
 301                 var rc registerCursor
 302                 var result *[]*Value
 303                 var aOffset int64
 304                 if len(aRegs) > 0 {
 305                         result = &allResults
 306                 } else {
 307                         aOffset = aux.OffsetOfArg(auxI)
 308                 }
 309                 if v.Op == OpTailLECall && a.Op == OpArg && a.AuxInt == 0 {
 310                         // It's common for a tail call passing the same arguments (e.g. method wrapper),
 311                         // so this would be a self copy. Detect this and optimize it out.
 312                         n := a.Aux.(*ir.Name)
 313                         if n.Class == ir.PPARAM && n.FrameOffset()+x.f.Config.ctxt.Arch.FixedFrameSize == aOffset {
 314                                 continue
 315                         }
 316                 }
 317                 if x.debug > 1 {
 318                         x.Printf("...storeArg %s, %v, %d\n", a.LongString(), aType, aOffset)
 319                 }
 320
 321                 rc.init(aRegs, aux.abiInfo, result, sp, aOffset)
 322                 mem = x.decomposeAsNecessary(v.Pos, v.Block, a, mem, rc)
 323         }
 324         var preArgStore [2]*Value
 325         preArgs := append(preArgStore[:0], v.Args[0:firstArg]...)
 326         v.resetArgs()
 327         v.AddArgs(preArgs...)
 328         v.AddArgs(allResults...)
 329         v.AddArg(mem)
 330         for _, a := range oldArgs {
 331                 if a.Uses == 0 {
 332                         x.invalidateRecursively(a)
 333                 }
 334         }
 335
 336         return
 337 }
 338
 339 func (x *expandState) decomposePair(pos src.XPos, b *Block, a, mem *Value, t0, t1 *types.Type, o0, o1 Op, rc *registerCursor) *Value {
 340         e := b.NewValue1(pos, o0, t0, a)
 341         pos = pos.WithNotStmt()
 342         mem = x.decomposeAsNecessary(pos, b, e, mem, rc.next(t0))
 343         e = b.NewValue1(pos, o1, t1, a)
 344         mem = x.decomposeAsNecessary(pos, b, e, mem, rc.next(t1))
 345         return mem
 346 }
 347
 348 func (x *expandState) decomposeOne(pos src.XPos, b *Block, a, mem *Value, t0 *types.Type, o0 Op, rc *registerCursor) *Value {
 349         e := b.NewValue1(pos, o0, t0, a)
 350         pos = pos.WithNotStmt()
 351         mem = x.decomposeAsNecessary(pos, b, e, mem, rc.next(t0))
 352         return mem
 353 }
 354
 355 // decomposeAsNecessary converts a value (perhaps an aggregate) passed to a call or returned by a function,
 356 // into the appropriate sequence of stores and register assignments to transmit that value in a given ABI, and
 357 // returns the current memory after this convert/rewrite (it may be the input memory, perhaps stores were needed.)
 358 // 'pos' is the source position all this is tied to
 359 // 'b' is the enclosing block
 360 // 'a' is the value to decompose
 361 // 'm0' is the input memory arg used for the first store (or returned if there are no stores)
 362 // 'rc' is a registerCursor which identifies the register/memory destination for the value
 363 func (x *expandState) decomposeAsNecessary(pos src.XPos, b *Block, a, m0 *Value, rc registerCursor) *Value {
 364         if x.debug > 1 {
 365                 x.indent(3)
 366                 defer x.indent(-3)
 367         }
 368         at := a.Type
 369         if at.Size() == 0 {
 370                 return m0
 371         }
 372         if a.Op == OpDereference {
 373                 a.Op = OpLoad // For purposes of parameter passing expansion, a Dereference is a Load.
 374         }
 375
 376         if !rc.hasRegs() && !CanSSA(at) {
 377                 dst := x.offsetFrom(b, rc.storeDest, rc.storeOffset, types.NewPtr(at))
 378                 if x.debug > 1 {
 379                         x.Printf("...recur store %s at %s\n", a.LongString(), dst.LongString())
 380                 }
 381                 if a.Op == OpLoad {
 382                         m0 = b.NewValue3A(pos, OpMove, types.TypeMem, at, dst, a.Args[0], m0)
 383                         m0.AuxInt = at.Size()
 384                         return m0
 385                 } else {
 386                         panic(fmt.Errorf("Store of not a load"))
 387                 }
 388         }
 389
 390         mem := m0
 391         switch at.Kind() {
 392         case types.TARRAY:
 393                 et := at.Elem()
 394                 for i := int64(0); i < at.NumElem(); i++ {
 395                         e := b.NewValue1I(pos, OpArraySelect, et, i, a)
 396                         pos = pos.WithNotStmt()
 397                         mem = x.decomposeAsNecessary(pos, b, e, mem, rc.next(et))
 398                 }
 399                 return mem
 400
 401         case types.TSTRUCT:
 402                 for i := 0; i < at.NumFields(); i++ {
 403                         et := at.Field(i).Type // might need to read offsets from the fields
 404                         e := b.NewValue1I(pos, OpStructSelect, et, int64(i), a)
 405                         pos = pos.WithNotStmt()
 406                         if x.debug > 1 {
 407                                 x.Printf("...recur decompose %s, %v\n", e.LongString(), et)
 408                         }
 409                         mem = x.decomposeAsNecessary(pos, b, e, mem, rc.next(et))
 410                 }
 411                 return mem
 412
 413         case types.TSLICE:
 414                 mem = x.decomposeOne(pos, b, a, mem, x.typs.BytePtr, OpSlicePtr, &rc)
 415                 pos = pos.WithNotStmt()
 416                 mem = x.decomposeOne(pos, b, a, mem, x.typs.Int, OpSliceLen, &rc)
 417                 return x.decomposeOne(pos, b, a, mem, x.typs.Int, OpSliceCap, &rc)
 418
 419         case types.TSTRING:
 420                 return x.decomposePair(pos, b, a, mem, x.typs.BytePtr, x.typs.Int, OpStringPtr, OpStringLen, &rc)
 421
 422         case types.TINTER:
 423                 mem = x.decomposeOne(pos, b, a, mem, x.typs.Uintptr, OpITab, &rc)
 424                 pos = pos.WithNotStmt()
 425                 // Immediate interfaces cause so many headaches.
 426                 if a.Op == OpIMake {
 427                         data := a.Args[1]
 428                         for data.Op == OpStructMake1 || data.Op == OpArrayMake1 {
 429                                 data = data.Args[0]
 430                         }
 431                         return x.decomposeAsNecessary(pos, b, data, mem, rc.next(data.Type))
 432                 }
 433                 return x.decomposeOne(pos, b, a, mem, x.typs.BytePtr, OpIData, &rc)
 434
 435         case types.TCOMPLEX64:
 436                 return x.decomposePair(pos, b, a, mem, x.typs.Float32, x.typs.Float32, OpComplexReal, OpComplexImag, &rc)
 437
 438         case types.TCOMPLEX128:
 439                 return x.decomposePair(pos, b, a, mem, x.typs.Float64, x.typs.Float64, OpComplexReal, OpComplexImag, &rc)
 440
 441         case types.TINT64:
 442                 if at.Size() > x.regSize {
 443                         return x.decomposePair(pos, b, a, mem, x.firstType, x.secondType, x.firstOp, x.secondOp, &rc)
 444                 }
 445         case types.TUINT64:
 446                 if at.Size() > x.regSize {
 447                         return x.decomposePair(pos, b, a, mem, x.typs.UInt32, x.typs.UInt32, x.firstOp, x.secondOp, &rc)
 448                 }
 449         }
 450
 451         // An atomic type, either record the register or store it and update the memory.
 452
 453         if rc.hasRegs() {
 454                 if x.debug > 1 {
 455                         x.Printf("...recur addArg %s\n", a.LongString())
 456                 }
 457                 rc.addArg(a)
 458         } else {
 459                 dst := x.offsetFrom(b, rc.storeDest, rc.storeOffset, types.NewPtr(at))
 460                 if x.debug > 1 {
 461                         x.Printf("...recur store %s at %s\n", a.LongString(), dst.LongString())
 462                 }
 463                 mem = b.NewValue3A(pos, OpStore, types.TypeMem, at, dst, a, mem)
 464         }
 465
 466         return mem
 467 }
 468
 469 // Convert scalar OpArg into the proper OpWhateverArg instruction
 470 // Convert scalar OpSelectN into perhaps-differently-indexed OpSelectN
 471 // Convert aggregate OpArg into Make of its parts (which are eventually scalars)
 472 // Convert aggregate OpSelectN into Make of its parts (which are eventually scalars)
 473 // Returns the converted value.
 474 //
 475 //   - "pos" the position for any generated instructions
 476 //   - "b" the block for any generated instructions
 477 //   - "container" the outermost OpArg/OpSelectN
 478 //   - "a" the instruction to overwrite, if any (only the outermost caller)
 479 //   - "m0" the memory arg for any loads that are necessary
 480 //   - "at" the type of the Arg/part
 481 //   - "rc" the register/memory cursor locating the various parts of the Arg.
 482 func (x *expandState) rewriteSelectOrArg(pos src.XPos, b *Block, container, a, m0 *Value, at *types.Type, rc registerCursor) *Value {
 483
 484         if at == types.TypeMem {
 485                 a.copyOf(m0)
 486                 return a
 487         }
 488
 489         makeOf := func(a *Value, op Op, args []*Value) *Value {
 490                 if a == nil {
 491                         a = b.NewValue0(pos, op, at)
 492                         a.AddArgs(args...)
 493                 } else {
 494                         a.resetArgs()
 495                         a.Aux, a.AuxInt = nil, 0
 496                         a.Pos, a.Op, a.Type = pos, op, at
 497                         a.AddArgs(args...)
 498                 }
 499                 return a
 500         }
 501
 502         if at.Size() == 0 {
 503                 // For consistency, create these values even though they'll ultimately be unused
 504                 if at.IsArray() {
 505                         return makeOf(a, OpArrayMake0, nil)
 506                 }
 507                 if at.IsStruct() {
 508                         return makeOf(a, OpStructMake0, nil)
 509                 }
 510                 return a
 511         }
 512
 513         sk := selKey{from: container, size: 0, offsetOrIndex: rc.storeOffset, typ: at}
 514         dupe := x.commonSelectors[sk]
 515         if dupe != nil {
 516                 if a == nil {
 517                         return dupe
 518                 }
 519                 a.copyOf(dupe)
 520                 return a
 521         }
 522
 523         var argStore [10]*Value
 524         args := argStore[:0]
 525
 526         addArg := func(a0 *Value) {
 527                 if a0 == nil {
 528                         as := "<nil>"
 529                         if a != nil {
 530                                 as = a.LongString()
 531                         }
 532                         panic(fmt.Errorf("a0 should not be nil, a=%v, container=%v, at=%v", as, container.LongString(), at))
 533                 }
 534                 args = append(args, a0)
 535         }
 536
 537         switch at.Kind() {
 538         case types.TARRAY:
 539                 et := at.Elem()
 540                 for i := int64(0); i < at.NumElem(); i++ {
 541                         e := x.rewriteSelectOrArg(pos, b, container, nil, m0, et, rc.next(et))
 542                         addArg(e)
 543                 }
 544                 a = makeOf(a, OpArrayMake1, args)
 545                 x.commonSelectors[sk] = a
 546                 return a
 547
 548         case types.TSTRUCT:
 549                 // Assume ssagen/ssa.go (in buildssa) spills large aggregates so they won't appear here.
 550                 for i := 0; i < at.NumFields(); i++ {
 551                         et := at.Field(i).Type
 552                         e := x.rewriteSelectOrArg(pos, b, container, nil, m0, et, rc.next(et))
 553                         if e == nil {
 554                                 panic(fmt.Errorf("nil e, et=%v, et.Size()=%d, i=%d", et, et.Size(), i))
 555                         }
 556                         addArg(e)
 557                         pos = pos.WithNotStmt()
 558                 }
 559                 if at.NumFields() > 4 {
 560                         panic(fmt.Errorf("Too many fields (%d, %d bytes), container=%s", at.NumFields(), at.Size(), container.LongString()))
 561                 }
 562                 a = makeOf(a, StructMakeOp(at.NumFields()), args)
 563                 x.commonSelectors[sk] = a
 564                 return a
 565
 566         case types.TSLICE:
 567                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr)))
 568                 pos = pos.WithNotStmt()
 569                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Int, rc.next(x.typs.Int)))
 570                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Int, rc.next(x.typs.Int)))
 571                 a = makeOf(a, OpSliceMake, args)
 572                 x.commonSelectors[sk] = a
 573                 return a
 574
 575         case types.TSTRING:
 576                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr)))
 577                 pos = pos.WithNotStmt()
 578                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Int, rc.next(x.typs.Int)))
 579                 a = makeOf(a, OpStringMake, args)
 580                 x.commonSelectors[sk] = a
 581                 return a
 582
 583         case types.TINTER:
 584                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Uintptr, rc.next(x.typs.Uintptr)))
 585                 pos = pos.WithNotStmt()
 586                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr)))
 587                 a = makeOf(a, OpIMake, args)
 588                 x.commonSelectors[sk] = a
 589                 return a
 590
 591         case types.TCOMPLEX64:
 592                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Float32, rc.next(x.typs.Float32)))
 593                 pos = pos.WithNotStmt()
 594                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Float32, rc.next(x.typs.Float32)))
 595                 a = makeOf(a, OpComplexMake, args)
 596                 x.commonSelectors[sk] = a
 597                 return a
 598
 599         case types.TCOMPLEX128:
 600                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Float64, rc.next(x.typs.Float64)))
 601                 pos = pos.WithNotStmt()
 602                 addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.Float64, rc.next(x.typs.Float64)))
 603                 a = makeOf(a, OpComplexMake, args)
 604                 x.commonSelectors[sk] = a
 605                 return a
 606
 607         case types.TINT64:
 608                 if at.Size() > x.regSize {
 609                         addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.firstType, rc.next(x.firstType)))
 610                         pos = pos.WithNotStmt()
 611                         addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.secondType, rc.next(x.secondType)))
 612                         if !x.f.Config.BigEndian {
 613                                 // Int64Make args are big, little
 614                                 args[0], args[1] = args[1], args[0]
 615                         }
 616                         a = makeOf(a, OpInt64Make, args)
 617                         x.commonSelectors[sk] = a
 618                         return a
 619                 }
 620         case types.TUINT64:
 621                 if at.Size() > x.regSize {
 622                         addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.UInt32, rc.next(x.typs.UInt32)))
 623                         pos = pos.WithNotStmt()
 624                         addArg(x.rewriteSelectOrArg(pos, b, container, nil, m0, x.typs.UInt32, rc.next(x.typs.UInt32)))
 625                         if !x.f.Config.BigEndian {
 626                                 // Int64Make args are big, little
 627                                 args[0], args[1] = args[1], args[0]
 628                         }
 629                         a = makeOf(a, OpInt64Make, args)
 630                         x.commonSelectors[sk] = a
 631                         return a
 632                 }
 633         }
 634
 635         // An atomic type, either record the register or store it and update the memory.
 636
 637         // Depending on the container Op, the leaves are either OpSelectN or OpArg{Int,Float}Reg
 638
 639         if container.Op == OpArg {
 640                 if rc.hasRegs() {
 641                         op, i := rc.ArgOpAndRegisterFor()
 642                         name := container.Aux.(*ir.Name)
 643                         a = makeOf(a, op, nil)
 644                         a.AuxInt = i
 645                         a.Aux = &AuxNameOffset{name, rc.storeOffset}
 646                 } else {
 647                         key := selKey{container, rc.storeOffset, at.Size(), at}
 648                         w := x.commonArgs[key]
 649                         if w != nil && w.Uses != 0 {
 650                                 if a == nil {
 651                                         a = w
 652                                 } else {
 653                                         a.copyOf(w)
 654                                 }
 655                         } else {
 656                                 if a == nil {
 657                                         aux := container.Aux
 658                                         auxInt := container.AuxInt + rc.storeOffset
 659                                         a = container.Block.NewValue0IA(container.Pos, OpArg, at, auxInt, aux)
 660                                 } else {
 661                                         // do nothing, the original should be okay.
 662                                 }
 663                                 x.commonArgs[key] = a
 664                         }
 665                 }
 666         } else if container.Op == OpSelectN {
 667                 call := container.Args[0]
 668                 aux := call.Aux.(*AuxCall)
 669                 which := container.AuxInt
 670
 671                 if at == types.TypeMem {
 672                         if a != m0 || a != x.memForCall[call.ID] {
 673                                 panic(fmt.Errorf("Memories %s, %s, and %s should all be equal after %s", a.LongString(), m0.LongString(), x.memForCall[call.ID], call.LongString()))
 674                         }
 675                 } else if rc.hasRegs() {
 676                         firstReg := uint32(0)
 677                         for i := 0; i < int(which); i++ {
 678                                 firstReg += uint32(len(aux.abiInfo.OutParam(i).Registers))
 679                         }
 680                         reg := int64(rc.nextSlice + Abi1RO(firstReg))
 681                         a = makeOf(a, OpSelectN, []*Value{call})
 682                         a.AuxInt = reg
 683                 } else {
 684                         off := x.offsetFrom(x.f.Entry, x.sp, rc.storeOffset+aux.OffsetOfResult(which), types.NewPtr(at))
 685                         a = makeOf(a, OpLoad, []*Value{off, m0})
 686                 }
 687
 688         } else {
 689                 panic(fmt.Errorf("Expected container OpArg or OpSelectN, saw %v instead", container.LongString()))
 690         }
 691
 692         x.commonSelectors[sk] = a
 693         return a
 694 }
 695
 696 // rewriteWideSelectToStores handles the case of a SelectN'd result from a function call that is too large for SSA,
 697 // but is transferred in registers.  In this case the register cursor tracks both operands; the register sources and
 698 // the memory destinations.
 699 // This returns the memory flowing out of the last store
 700 func (x *expandState) rewriteWideSelectToStores(pos src.XPos, b *Block, container, m0 *Value, at *types.Type, rc registerCursor) *Value {
 701
 702         if at.Size() == 0 {
 703                 return m0
 704         }
 705
 706         switch at.Kind() {
 707         case types.TARRAY:
 708                 et := at.Elem()
 709                 for i := int64(0); i < at.NumElem(); i++ {
 710                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, et, rc.next(et))
 711                 }
 712                 return m0
 713
 714         case types.TSTRUCT:
 715                 // Assume ssagen/ssa.go (in buildssa) spills large aggregates so they won't appear here.
 716                 for i := 0; i < at.NumFields(); i++ {
 717                         et := at.Field(i).Type
 718                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, et, rc.next(et))
 719                         pos = pos.WithNotStmt()
 720                 }
 721                 return m0
 722
 723         case types.TSLICE:
 724                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr))
 725                 pos = pos.WithNotStmt()
 726                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Int, rc.next(x.typs.Int))
 727                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Int, rc.next(x.typs.Int))
 728                 return m0
 729
 730         case types.TSTRING:
 731                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr))
 732                 pos = pos.WithNotStmt()
 733                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Int, rc.next(x.typs.Int))
 734                 return m0
 735
 736         case types.TINTER:
 737                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Uintptr, rc.next(x.typs.Uintptr))
 738                 pos = pos.WithNotStmt()
 739                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.BytePtr, rc.next(x.typs.BytePtr))
 740                 return m0
 741
 742         case types.TCOMPLEX64:
 743                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Float32, rc.next(x.typs.Float32))
 744                 pos = pos.WithNotStmt()
 745                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Float32, rc.next(x.typs.Float32))
 746                 return m0
 747
 748         case types.TCOMPLEX128:
 749                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Float64, rc.next(x.typs.Float64))
 750                 pos = pos.WithNotStmt()
 751                 m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.Float64, rc.next(x.typs.Float64))
 752                 return m0
 753
 754         case types.TINT64:
 755                 if at.Size() > x.regSize {
 756                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.firstType, rc.next(x.firstType))
 757                         pos = pos.WithNotStmt()
 758                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.secondType, rc.next(x.secondType))
 759                         return m0
 760                 }
 761         case types.TUINT64:
 762                 if at.Size() > x.regSize {
 763                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.UInt32, rc.next(x.typs.UInt32))
 764                         pos = pos.WithNotStmt()
 765                         m0 = x.rewriteWideSelectToStores(pos, b, container, m0, x.typs.UInt32, rc.next(x.typs.UInt32))
 766                         return m0
 767                 }
 768         }
 769
 770         // TODO could change treatment of too-large OpArg, would deal with it here.
 771         if container.Op == OpSelectN {
 772                 call := container.Args[0]
 773                 aux := call.Aux.(*AuxCall)
 774                 which := container.AuxInt
 775
 776                 if rc.hasRegs() {
 777                         firstReg := uint32(0)
 778                         for i := 0; i < int(which); i++ {
 779                                 firstReg += uint32(len(aux.abiInfo.OutParam(i).Registers))
 780                         }
 781                         reg := int64(rc.nextSlice + Abi1RO(firstReg))
 782                         a := b.NewValue1I(pos, OpSelectN, at, reg, call)
 783                         dst := x.offsetFrom(b, rc.storeDest, rc.storeOffset, types.NewPtr(at))
 784                         m0 = b.NewValue3A(pos, OpStore, types.TypeMem, at, dst, a, m0)
 785                 } else {
 786                         panic(fmt.Errorf("Expected rc to have registers"))
 787                 }
 788         } else {
 789                 panic(fmt.Errorf("Expected container OpSelectN, saw %v instead", container.LongString()))
 790         }
 791         return m0
 792 }
 793
 794 func isBlockMultiValueExit(b *Block) bool {
 795         return (b.Kind == BlockRet || b.Kind == BlockRetJmp) && b.Controls[0] != nil && b.Controls[0].Op == OpMakeResult
 796 }
 797
 798 type Abi1RO uint8 // An offset within a parameter's slice of register indices, for abi1.
 799
 800 // A registerCursor tracks which register is used for an Arg or regValues, or a piece of such.
 801 type registerCursor struct {
 802         storeDest   *Value // if there are no register targets, then this is the base of the store.
 803         storeOffset int64
 804         regs        []abi.RegIndex // the registers available for this Arg/result (which is all in registers or not at all)
 805         nextSlice   Abi1RO         // the next register/register-slice offset
 806         config      *abi.ABIConfig
 807         regValues   *[]*Value // values assigned to registers accumulate here
 808 }
 809
 810 func (c *registerCursor) String() string {
 811         dest := "<none>"
 812         if c.storeDest != nil {
 813                 dest = fmt.Sprintf("%s+%d", c.storeDest.String(), c.storeOffset)
 814         }
 815         regs := "<none>"
 816         if c.regValues != nil {
 817                 regs = ""
 818                 for i, x := range *c.regValues {
 819                         if i > 0 {
 820                                 regs = regs + "; "
 821                         }
 822                         regs = regs + x.LongString()
 823                 }
 824         }
 825
 826         // not printing the config because that has not been useful
 827         return fmt.Sprintf("RCSR{storeDest=%v, regsLen=%d, nextSlice=%d, regValues=[%s]}", dest, len(c.regs), c.nextSlice, regs)
 828 }
 829
 830 // next effectively post-increments the register cursor; the receiver is advanced,
 831 // the (aligned) old value is returned.
 832 func (c *registerCursor) next(t *types.Type) registerCursor {
 833         c.storeOffset = types.RoundUp(c.storeOffset, t.Alignment())
 834         rc := *c
 835         c.storeOffset = types.RoundUp(c.storeOffset+t.Size(), t.Alignment())
 836         if int(c.nextSlice) < len(c.regs) {
 837                 w := c.config.NumParamRegs(t)
 838                 c.nextSlice += Abi1RO(w)
 839         }
 840         return rc
 841 }
 842
 843 // plus returns a register cursor offset from the original, without modifying the original.
 844 func (c *registerCursor) plus(regWidth Abi1RO) registerCursor {
 845         rc := *c
 846         rc.nextSlice += regWidth
 847         return rc
 848 }
 849
 850 // at returns the register cursor for component i of t, where the first
 851 // component is numbered 0.
 852 func (c *registerCursor) at(t *types.Type, i int) registerCursor {
 853         rc := *c
 854         if i == 0 || len(c.regs) == 0 {
 855                 return rc
 856         }
 857         if t.IsArray() {
 858                 w := c.config.NumParamRegs(t.Elem())
 859                 rc.nextSlice += Abi1RO(i * w)
 860                 return rc
 861         }
 862         if t.IsStruct() {
 863                 for j := 0; j < i; j++ {
 864                         rc.next(t.FieldType(j))
 865                 }
 866                 return rc
 867         }
 868         panic("Haven't implemented this case yet, do I need to?")
 869 }
 870
 871 func (c *registerCursor) init(regs []abi.RegIndex, info *abi.ABIParamResultInfo, result *[]*Value, storeDest *Value, storeOffset int64) {
 872         c.regs = regs
 873         c.nextSlice = 0
 874         c.storeOffset = storeOffset
 875         c.storeDest = storeDest
 876         c.config = info.Config()
 877         c.regValues = result
 878 }
 879
 880 func (c *registerCursor) addArg(v *Value) {
 881         *c.regValues = append(*c.regValues, v)
 882 }
 883
 884 func (c *registerCursor) hasRegs() bool {
 885         return len(c.regs) > 0
 886 }
 887
 888 func (c *registerCursor) ArgOpAndRegisterFor() (Op, int64) {
 889         r := c.regs[c.nextSlice]
 890         return ArgOpAndRegisterFor(r, c.config)
 891 }
 892
 893 // ArgOpAndRegisterFor converts an abi register index into an ssa Op and corresponding
 894 // arg register index.
 895 func ArgOpAndRegisterFor(r abi.RegIndex, abiConfig *abi.ABIConfig) (Op, int64) {
 896         i := abiConfig.FloatIndexFor(r)
 897         if i >= 0 { // float PR
 898                 return OpArgFloatReg, i
 899         }
 900         return OpArgIntReg, int64(r)
 901 }
 902
 903 type selKey struct {
 904         from          *Value // what is selected from
 905         offsetOrIndex int64  // whatever is appropriate for the selector
 906         size          int64
 907         typ           *types.Type
 908 }
 909
 910 type expandState struct {
 911         f       *Func
 912         debug   int // odd values log lost statement markers, so likely settings are 1 (stmts), 2 (expansion), and 3 (both)
 913         regSize int64
 914         sp      *Value
 915         typs    *Types
 916
 917         firstOp    Op          // for 64-bit integers on 32-bit machines, first word in memory
 918         secondOp   Op          // for 64-bit integers on 32-bit machines, second word in memory
 919         firstType  *types.Type // first half type, for Int64
 920         secondType *types.Type // second half type, for Int64
 921
 922         wideSelects     map[*Value]*Value // Selects that are not SSA-able, mapped to consuming stores.
 923         commonSelectors map[selKey]*Value // used to de-dupe selectors
 924         commonArgs      map[selKey]*Value // used to de-dupe OpArg/OpArgIntReg/OpArgFloatReg
 925         memForCall      map[ID]*Value     // For a call, need to know the unique selector that gets the mem.
 926         indentLevel     int               // Indentation for debugging recursion
 927 }
 928
 929 // intPairTypes returns the pair of 32-bit int types needed to encode a 64-bit integer type on a target
 930 // that has no 64-bit integer registers.
 931 func (x *expandState) intPairTypes(et types.Kind) (tHi, tLo *types.Type) {
 932         tHi = x.typs.UInt32
 933         if et == types.TINT64 {
 934                 tHi = x.typs.Int32
 935         }
 936         tLo = x.typs.UInt32
 937         return
 938 }
 939
 940 // offsetFrom creates an offset from a pointer, simplifying chained offsets and offsets from SP
 941 func (x *expandState) offsetFrom(b *Block, from *Value, offset int64, pt *types.Type) *Value {
 942         ft := from.Type
 943         if offset == 0 {
 944                 if ft == pt {
 945                         return from
 946                 }
 947                 // This captures common, (apparently) safe cases.  The unsafe cases involve ft == uintptr
 948                 if (ft.IsPtr() || ft.IsUnsafePtr()) && pt.IsPtr() {
 949                         return from
 950                 }
 951         }
 952         // Simplify, canonicalize
 953         for from.Op == OpOffPtr {
 954                 offset += from.AuxInt
 955                 from = from.Args[0]
 956         }
 957         if from == x.sp {
 958                 return x.f.ConstOffPtrSP(pt, offset, x.sp)
 959         }
 960         return b.NewValue1I(from.Pos.WithNotStmt(), OpOffPtr, pt, offset, from)
 961 }
 962
 963 func (x *expandState) regWidth(t *types.Type) Abi1RO {
 964         return Abi1RO(x.f.ABI1.NumParamRegs(t))
 965 }
 966
 967 // regOffset returns the register offset of the i'th element of type t
 968 func (x *expandState) regOffset(t *types.Type, i int) Abi1RO {
 969         // TODO maybe cache this in a map if profiling recommends.
 970         if i == 0 {
 971                 return 0
 972         }
 973         if t.IsArray() {
 974                 return Abi1RO(i) * x.regWidth(t.Elem())
 975         }
 976         if t.IsStruct() {
 977                 k := Abi1RO(0)
 978                 for j := 0; j < i; j++ {
 979                         k += x.regWidth(t.FieldType(j))
 980                 }
 981                 return k
 982         }
 983         panic("Haven't implemented this case yet, do I need to?")
 984 }
 985
 986 // prAssignForArg returns the ABIParamAssignment for v, assumed to be an OpArg.
 987 func (x *expandState) prAssignForArg(v *Value) *abi.ABIParamAssignment {
 988         if v.Op != OpArg {
 989                 panic(fmt.Errorf("Wanted OpArg, instead saw %s", v.LongString()))
 990         }
 991         return ParamAssignmentForArgName(x.f, v.Aux.(*ir.Name))
 992 }
 993
 994 // ParamAssignmentForArgName returns the ABIParamAssignment for f's arg with matching name.
 995 func ParamAssignmentForArgName(f *Func, name *ir.Name) *abi.ABIParamAssignment {
 996         abiInfo := f.OwnAux.abiInfo
 997         ip := abiInfo.InParams()
 998         for i, a := range ip {
 999                 if a.Name == name {
1000                         return &ip[i]
1001                 }
1002         }
1003         panic(fmt.Errorf("Did not match param %v in prInfo %+v", name, abiInfo.InParams()))
1004 }
1005
1006 // indent increments (or decrements) the indentation.
1007 func (x *expandState) indent(n int) {
1008         x.indentLevel += n
1009 }
1010
1011 // Printf does an indented fmt.Printf on the format and args.
1012 func (x *expandState) Printf(format string, a ...interface{}) (n int, err error) {
1013         if x.indentLevel > 0 {
1014                 fmt.Printf("%[1]*s", x.indentLevel, "")
1015         }
1016         return fmt.Printf(format, a...)
1017 }
1018
1019 func (x *expandState) invalidateRecursively(a *Value) {
1020         var s string
1021         if x.debug > 0 {
1022                 plus := " "
1023                 if a.Pos.IsStmt() == src.PosIsStmt {
1024                         plus = " +"
1025                 }
1026                 s = a.String() + plus + a.Pos.LineNumber() + " " + a.LongString()
1027                 if x.debug > 1 {
1028                         x.Printf("...marking %v unused\n", s)
1029                 }
1030         }
1031         lost := a.invalidateRecursively()
1032         if x.debug&1 != 0 && lost { // For odd values of x.debug, do this.
1033                 x.Printf("Lost statement marker in %s on former %s\n", base.Ctxt.Pkgpath+"."+x.f.Name, s)
1034         }
1035 }