src/cmd/compile/internal/gc/ssa.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 gc
   6
   7 import (
   8         "bytes"
   9         "crypto/sha1"
  10         "fmt"
  11         "html"
  12         "math"
  13         "os"
  14         "strings"
  15
  16         "cmd/compile/internal/ssa"
  17         "cmd/internal/obj"
  18         "cmd/internal/obj/x86"
  19 )
  20
  21 // buildssa builds an SSA function
  22 // and reports whether it should be used.
  23 // Once the SSA implementation is complete,
  24 // it will never return nil, and the bool can be removed.
  25 func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) {
  26         name := fn.Func.Nname.Sym.Name
  27         usessa = strings.HasSuffix(name, "_ssa") || strings.Contains(name, "_ssa.") || name == os.Getenv("GOSSAFUNC")
  28
  29         if usessa {
  30                 fmt.Println("generating SSA for", name)
  31                 dumplist("buildssa-enter", fn.Func.Enter)
  32                 dumplist("buildssa-body", fn.Nbody)
  33                 dumplist("buildssa-exit", fn.Func.Exit)
  34         }
  35
  36         var s state
  37         s.pushLine(fn.Lineno)
  38         defer s.popLine()
  39
  40         // TODO(khr): build config just once at the start of the compiler binary
  41
  42         var e ssaExport
  43         e.log = usessa
  44         s.config = ssa.NewConfig(Thearch.Thestring, &e)
  45         s.f = s.config.NewFunc()
  46         s.f.Name = name
  47         s.exitCode = fn.Func.Exit
  48
  49         if name == os.Getenv("GOSSAFUNC") {
  50                 // TODO: tempfile? it is handy to have the location
  51                 // of this file be stable, so you can just reload in the browser.
  52                 s.config.HTML = ssa.NewHTMLWriter("ssa.html", &s, name)
  53                 // TODO: generate and print a mapping from nodes to values and blocks
  54         }
  55         defer func() {
  56                 if !usessa {
  57                         s.config.HTML.Close()
  58                 }
  59         }()
  60
  61         // If SSA support for the function is incomplete,
  62         // assume that any panics are due to violated
  63         // invariants. Swallow them silently.
  64         defer func() {
  65                 if err := recover(); err != nil {
  66                         if !e.unimplemented {
  67                                 panic(err)
  68                         }
  69                 }
  70         }()
  71
  72         // We construct SSA using an algorithm similar to
  73         // Brau, Buchwald, Hack, Leißa, Mallon, and Zwinkau
  74         // http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
  75         // TODO: check this comment
  76
  77         // Allocate starting block
  78         s.f.Entry = s.f.NewBlock(ssa.BlockPlain)
  79
  80         // Allocate starting values
  81         s.labels = map[string]*ssaLabel{}
  82         s.labeledNodes = map[*Node]*ssaLabel{}
  83         s.startmem = s.entryNewValue0(ssa.OpArg, ssa.TypeMem)
  84         s.sp = s.entryNewValue0(ssa.OpSP, Types[TUINTPTR]) // TODO: use generic pointer type (unsafe.Pointer?) instead
  85         s.sb = s.entryNewValue0(ssa.OpSB, Types[TUINTPTR])
  86
  87         s.startBlock(s.f.Entry)
  88         s.vars[&memVar] = s.startmem
  89
  90         s.varsyms = map[*Node]interface{}{}
  91
  92         // Generate addresses of local declarations
  93         s.decladdrs = map[*Node]*ssa.Value{}
  94         for d := fn.Func.Dcl; d != nil; d = d.Next {
  95                 n := d.N
  96                 switch n.Class {
  97                 case PPARAM:
  98                         aux := s.lookupSymbol(n, &ssa.ArgSymbol{Typ: n.Type, Node: n})
  99                         s.decladdrs[n] = s.entryNewValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sp)
 100                 case PAUTO | PHEAP:
 101                         // TODO this looks wrong for PAUTO|PHEAP, no vardef, but also no definition
 102                         aux := s.lookupSymbol(n, &ssa.AutoSymbol{Typ: n.Type, Node: n})
 103                         s.decladdrs[n] = s.entryNewValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sp)
 104                 case PPARAM | PHEAP, PPARAMOUT | PHEAP:
 105                 // This ends up wrong, have to do it at the PARAM node instead.
 106                 case PAUTO, PPARAMOUT:
 107                         // processed at each use, to prevent Addr coming
 108                         // before the decl.
 109                 case PFUNC:
 110                         // local function - already handled by frontend
 111                 default:
 112                         str := ""
 113                         if n.Class&PHEAP != 0 {
 114                                 str = ",heap"
 115                         }
 116                         s.Unimplementedf("local variable with class %s%s unimplemented", classnames[n.Class&^PHEAP], str)
 117                 }
 118         }
 119         // nodfp is a special argument which is the function's FP.
 120         aux := &ssa.ArgSymbol{Typ: Types[TUINTPTR], Node: nodfp}
 121         s.decladdrs[nodfp] = s.entryNewValue1A(ssa.OpAddr, Types[TUINTPTR], aux, s.sp)
 122
 123         // Convert the AST-based IR to the SSA-based IR
 124         s.stmtList(fn.Func.Enter)
 125         s.stmtList(fn.Nbody)
 126
 127         // fallthrough to exit
 128         if s.curBlock != nil {
 129                 s.stmtList(s.exitCode)
 130                 m := s.mem()
 131                 b := s.endBlock()
 132                 b.Kind = ssa.BlockRet
 133                 b.Control = m
 134         }
 135
 136         // Check that we used all labels
 137         for name, lab := range s.labels {
 138                 if !lab.used() && !lab.reported {
 139                         yyerrorl(int(lab.defNode.Lineno), "label %v defined and not used", name)
 140                         lab.reported = true
 141                 }
 142                 if lab.used() && !lab.defined() && !lab.reported {
 143                         yyerrorl(int(lab.useNode.Lineno), "label %v not defined", name)
 144                         lab.reported = true
 145                 }
 146         }
 147
 148         // Check any forward gotos. Non-forward gotos have already been checked.
 149         for _, n := range s.fwdGotos {
 150                 lab := s.labels[n.Left.Sym.Name]
 151                 // If the label is undefined, we have already have printed an error.
 152                 if lab.defined() {
 153                         s.checkgoto(n, lab.defNode)
 154                 }
 155         }
 156
 157         if nerrors > 0 {
 158                 return nil, false
 159         }
 160
 161         // Link up variable uses to variable definitions
 162         s.linkForwardReferences()
 163
 164         // Don't carry reference this around longer than necessary
 165         s.exitCode = nil
 166
 167         // Main call to ssa package to compile function
 168         ssa.Compile(s.f)
 169
 170         // Calculate stats about what percentage of functions SSA handles.
 171         if false {
 172                 fmt.Printf("SSA implemented: %t\n", !e.unimplemented)
 173         }
 174
 175         if e.unimplemented {
 176                 return nil, false
 177         }
 178
 179         // TODO: enable codegen more broadly once the codegen stabilizes
 180         // and runtime support is in (gc maps, write barriers, etc.)
 181         if usessa {
 182                 return s.f, true
 183         }
 184         if localpkg.Name != os.Getenv("GOSSAPKG") {
 185                 return s.f, false
 186         }
 187         if os.Getenv("GOSSAHASH") == "" {
 188                 // Use everything in the package
 189                 return s.f, true
 190         }
 191         // Check the hash of the name against a partial input hash.
 192         // We use this feature to do a binary search within a package to
 193         // find a function that is incorrectly compiled.
 194         hstr := ""
 195         for _, b := range sha1.Sum([]byte(name)) {
 196                 hstr += fmt.Sprintf("%08b", b)
 197         }
 198         if strings.HasSuffix(hstr, os.Getenv("GOSSAHASH")) {
 199                 fmt.Printf("GOSSAHASH triggered %s\n", name)
 200                 return s.f, true
 201         }
 202         return s.f, false
 203 }
 204
 205 type state struct {
 206         // configuration (arch) information
 207         config *ssa.Config
 208
 209         // function we're building
 210         f *ssa.Func
 211
 212         // labels and labeled control flow nodes (OFOR, OSWITCH, OSELECT) in f
 213         labels       map[string]*ssaLabel
 214         labeledNodes map[*Node]*ssaLabel
 215
 216         // gotos that jump forward; required for deferred checkgoto calls
 217         fwdGotos []*Node
 218         // Code that must precede any return
 219         // (e.g., copying value of heap-escaped paramout back to true paramout)
 220         exitCode *NodeList
 221
 222         // unlabeled break and continue statement tracking
 223         breakTo    *ssa.Block // current target for plain break statement
 224         continueTo *ssa.Block // current target for plain continue statement
 225
 226         // current location where we're interpreting the AST
 227         curBlock *ssa.Block
 228
 229         // variable assignments in the current block (map from variable symbol to ssa value)
 230         // *Node is the unique identifier (an ONAME Node) for the variable.
 231         vars map[*Node]*ssa.Value
 232
 233         // all defined variables at the end of each block.  Indexed by block ID.
 234         defvars []map[*Node]*ssa.Value
 235
 236         // addresses of PPARAM and PPARAMOUT variables.
 237         decladdrs map[*Node]*ssa.Value
 238
 239         // symbols for PEXTERN, PAUTO and PPARAMOUT variables so they can be reused.
 240         varsyms map[*Node]interface{}
 241
 242         // starting values.  Memory, frame pointer, and stack pointer
 243         startmem *ssa.Value
 244         sp       *ssa.Value
 245         sb       *ssa.Value
 246
 247         // line number stack.  The current line number is top of stack
 248         line []int32
 249 }
 250
 251 type ssaLabel struct {
 252         target         *ssa.Block // block identified by this label
 253         breakTarget    *ssa.Block // block to break to in control flow node identified by this label
 254         continueTarget *ssa.Block // block to continue to in control flow node identified by this label
 255         defNode        *Node      // label definition Node (OLABEL)
 256         // Label use Node (OGOTO, OBREAK, OCONTINUE).
 257         // Used only for error detection and reporting.
 258         // There might be multiple uses, but we only need to track one.
 259         useNode  *Node
 260         reported bool // reported indicates whether an error has already been reported for this label
 261 }
 262
 263 // defined reports whether the label has a definition (OLABEL node).
 264 func (l *ssaLabel) defined() bool { return l.defNode != nil }
 265
 266 // used reports whether the label has a use (OGOTO, OBREAK, or OCONTINUE node).
 267 func (l *ssaLabel) used() bool { return l.useNode != nil }
 268
 269 // label returns the label associated with sym, creating it if necessary.
 270 func (s *state) label(sym *Sym) *ssaLabel {
 271         lab := s.labels[sym.Name]
 272         if lab == nil {
 273                 lab = new(ssaLabel)
 274                 s.labels[sym.Name] = lab
 275         }
 276         return lab
 277 }
 278
 279 func (s *state) Logf(msg string, args ...interface{})           { s.config.Logf(msg, args...) }
 280 func (s *state) Fatalf(msg string, args ...interface{})         { s.config.Fatalf(msg, args...) }
 281 func (s *state) Unimplementedf(msg string, args ...interface{}) { s.config.Unimplementedf(msg, args...) }
 282
 283 var (
 284         // dummy node for the memory variable
 285         memVar = Node{Op: ONAME, Sym: &Sym{Name: "mem"}}
 286
 287         // dummy nodes for temporary variables
 288         ptrVar   = Node{Op: ONAME, Sym: &Sym{Name: "ptr"}}
 289         capVar   = Node{Op: ONAME, Sym: &Sym{Name: "cap"}}
 290         typVar   = Node{Op: ONAME, Sym: &Sym{Name: "typ"}}
 291         idataVar = Node{Op: ONAME, Sym: &Sym{Name: "idata"}}
 292         okVar    = Node{Op: ONAME, Sym: &Sym{Name: "ok"}}
 293 )
 294
 295 // startBlock sets the current block we're generating code in to b.
 296 func (s *state) startBlock(b *ssa.Block) {
 297         if s.curBlock != nil {
 298                 s.Fatalf("starting block %v when block %v has not ended", b, s.curBlock)
 299         }
 300         s.curBlock = b
 301         s.vars = map[*Node]*ssa.Value{}
 302 }
 303
 304 // endBlock marks the end of generating code for the current block.
 305 // Returns the (former) current block.  Returns nil if there is no current
 306 // block, i.e. if no code flows to the current execution point.
 307 func (s *state) endBlock() *ssa.Block {
 308         b := s.curBlock
 309         if b == nil {
 310                 return nil
 311         }
 312         for len(s.defvars) <= int(b.ID) {
 313                 s.defvars = append(s.defvars, nil)
 314         }
 315         s.defvars[b.ID] = s.vars
 316         s.curBlock = nil
 317         s.vars = nil
 318         b.Line = s.peekLine()
 319         return b
 320 }
 321
 322 // pushLine pushes a line number on the line number stack.
 323 func (s *state) pushLine(line int32) {
 324         s.line = append(s.line, line)
 325 }
 326
 327 // popLine pops the top of the line number stack.
 328 func (s *state) popLine() {
 329         s.line = s.line[:len(s.line)-1]
 330 }
 331
 332 // peekLine peek the top of the line number stack.
 333 func (s *state) peekLine() int32 {
 334         return s.line[len(s.line)-1]
 335 }
 336
 337 func (s *state) Error(msg string, args ...interface{}) {
 338         yyerrorl(int(s.peekLine()), msg, args...)
 339 }
 340
 341 // newValue0 adds a new value with no arguments to the current block.
 342 func (s *state) newValue0(op ssa.Op, t ssa.Type) *ssa.Value {
 343         return s.curBlock.NewValue0(s.peekLine(), op, t)
 344 }
 345
 346 // newValue0A adds a new value with no arguments and an aux value to the current block.
 347 func (s *state) newValue0A(op ssa.Op, t ssa.Type, aux interface{}) *ssa.Value {
 348         return s.curBlock.NewValue0A(s.peekLine(), op, t, aux)
 349 }
 350
 351 // newValue0I adds a new value with no arguments and an auxint value to the current block.
 352 func (s *state) newValue0I(op ssa.Op, t ssa.Type, auxint int64) *ssa.Value {
 353         return s.curBlock.NewValue0I(s.peekLine(), op, t, auxint)
 354 }
 355
 356 // newValue1 adds a new value with one argument to the current block.
 357 func (s *state) newValue1(op ssa.Op, t ssa.Type, arg *ssa.Value) *ssa.Value {
 358         return s.curBlock.NewValue1(s.peekLine(), op, t, arg)
 359 }
 360
 361 // newValue1A adds a new value with one argument and an aux value to the current block.
 362 func (s *state) newValue1A(op ssa.Op, t ssa.Type, aux interface{}, arg *ssa.Value) *ssa.Value {
 363         return s.curBlock.NewValue1A(s.peekLine(), op, t, aux, arg)
 364 }
 365
 366 // newValue1I adds a new value with one argument and an auxint value to the current block.
 367 func (s *state) newValue1I(op ssa.Op, t ssa.Type, aux int64, arg *ssa.Value) *ssa.Value {
 368         return s.curBlock.NewValue1I(s.peekLine(), op, t, aux, arg)
 369 }
 370
 371 // newValue2 adds a new value with two arguments to the current block.
 372 func (s *state) newValue2(op ssa.Op, t ssa.Type, arg0, arg1 *ssa.Value) *ssa.Value {
 373         return s.curBlock.NewValue2(s.peekLine(), op, t, arg0, arg1)
 374 }
 375
 376 // newValue2I adds a new value with two arguments and an auxint value to the current block.
 377 func (s *state) newValue2I(op ssa.Op, t ssa.Type, aux int64, arg0, arg1 *ssa.Value) *ssa.Value {
 378         return s.curBlock.NewValue2I(s.peekLine(), op, t, aux, arg0, arg1)
 379 }
 380
 381 // newValue3 adds a new value with three arguments to the current block.
 382 func (s *state) newValue3(op ssa.Op, t ssa.Type, arg0, arg1, arg2 *ssa.Value) *ssa.Value {
 383         return s.curBlock.NewValue3(s.peekLine(), op, t, arg0, arg1, arg2)
 384 }
 385
 386 // newValue3I adds a new value with three arguments and an auxint value to the current block.
 387 func (s *state) newValue3I(op ssa.Op, t ssa.Type, aux int64, arg0, arg1, arg2 *ssa.Value) *ssa.Value {
 388         return s.curBlock.NewValue3I(s.peekLine(), op, t, aux, arg0, arg1, arg2)
 389 }
 390
 391 // entryNewValue0 adds a new value with no arguments to the entry block.
 392 func (s *state) entryNewValue0(op ssa.Op, t ssa.Type) *ssa.Value {
 393         return s.f.Entry.NewValue0(s.peekLine(), op, t)
 394 }
 395
 396 // entryNewValue0A adds a new value with no arguments and an aux value to the entry block.
 397 func (s *state) entryNewValue0A(op ssa.Op, t ssa.Type, aux interface{}) *ssa.Value {
 398         return s.f.Entry.NewValue0A(s.peekLine(), op, t, aux)
 399 }
 400
 401 // entryNewValue0I adds a new value with no arguments and an auxint value to the entry block.
 402 func (s *state) entryNewValue0I(op ssa.Op, t ssa.Type, auxint int64) *ssa.Value {
 403         return s.f.Entry.NewValue0I(s.peekLine(), op, t, auxint)
 404 }
 405
 406 // entryNewValue1 adds a new value with one argument to the entry block.
 407 func (s *state) entryNewValue1(op ssa.Op, t ssa.Type, arg *ssa.Value) *ssa.Value {
 408         return s.f.Entry.NewValue1(s.peekLine(), op, t, arg)
 409 }
 410
 411 // entryNewValue1 adds a new value with one argument and an auxint value to the entry block.
 412 func (s *state) entryNewValue1I(op ssa.Op, t ssa.Type, auxint int64, arg *ssa.Value) *ssa.Value {
 413         return s.f.Entry.NewValue1I(s.peekLine(), op, t, auxint, arg)
 414 }
 415
 416 // entryNewValue1A adds a new value with one argument and an aux value to the entry block.
 417 func (s *state) entryNewValue1A(op ssa.Op, t ssa.Type, aux interface{}, arg *ssa.Value) *ssa.Value {
 418         return s.f.Entry.NewValue1A(s.peekLine(), op, t, aux, arg)
 419 }
 420
 421 // entryNewValue2 adds a new value with two arguments to the entry block.
 422 func (s *state) entryNewValue2(op ssa.Op, t ssa.Type, arg0, arg1 *ssa.Value) *ssa.Value {
 423         return s.f.Entry.NewValue2(s.peekLine(), op, t, arg0, arg1)
 424 }
 425
 426 // const* routines add a new const value to the entry block.
 427 func (s *state) constBool(c bool) *ssa.Value {
 428         return s.f.ConstBool(s.peekLine(), Types[TBOOL], c)
 429 }
 430 func (s *state) constInt8(t ssa.Type, c int8) *ssa.Value {
 431         return s.f.ConstInt8(s.peekLine(), t, c)
 432 }
 433 func (s *state) constInt16(t ssa.Type, c int16) *ssa.Value {
 434         return s.f.ConstInt16(s.peekLine(), t, c)
 435 }
 436 func (s *state) constInt32(t ssa.Type, c int32) *ssa.Value {
 437         return s.f.ConstInt32(s.peekLine(), t, c)
 438 }
 439 func (s *state) constInt64(t ssa.Type, c int64) *ssa.Value {
 440         return s.f.ConstInt64(s.peekLine(), t, c)
 441 }
 442 func (s *state) constFloat32(t ssa.Type, c float64) *ssa.Value {
 443         return s.f.ConstFloat32(s.peekLine(), t, c)
 444 }
 445 func (s *state) constFloat64(t ssa.Type, c float64) *ssa.Value {
 446         return s.f.ConstFloat64(s.peekLine(), t, c)
 447 }
 448 func (s *state) constIntPtr(t ssa.Type, c int64) *ssa.Value {
 449         if s.config.PtrSize == 4 && int64(int32(c)) != c {
 450                 s.Fatalf("pointer constant too big %d", c)
 451         }
 452         return s.f.ConstIntPtr(s.peekLine(), t, c)
 453 }
 454 func (s *state) constInt(t ssa.Type, c int64) *ssa.Value {
 455         if s.config.IntSize == 8 {
 456                 return s.constInt64(t, c)
 457         }
 458         if int64(int32(c)) != c {
 459                 s.Fatalf("integer constant too big %d", c)
 460         }
 461         return s.constInt32(t, int32(c))
 462 }
 463
 464 // ssaStmtList converts the statement n to SSA and adds it to s.
 465 func (s *state) stmtList(l *NodeList) {
 466         for ; l != nil; l = l.Next {
 467                 s.stmt(l.N)
 468         }
 469 }
 470
 471 // ssaStmt converts the statement n to SSA and adds it to s.
 472 func (s *state) stmt(n *Node) {
 473         s.pushLine(n.Lineno)
 474         defer s.popLine()
 475
 476         // If s.curBlock is nil, then we're about to generate dead code.
 477         // We can't just short-circuit here, though,
 478         // because we check labels and gotos as part of SSA generation.
 479         // Provide a block for the dead code so that we don't have
 480         // to add special cases everywhere else.
 481         if s.curBlock == nil {
 482                 dead := s.f.NewBlock(ssa.BlockPlain)
 483                 s.startBlock(dead)
 484         }
 485
 486         s.stmtList(n.Ninit)
 487         switch n.Op {
 488
 489         case OBLOCK:
 490                 s.stmtList(n.List)
 491
 492         // No-ops
 493         case OEMPTY, ODCLCONST, ODCLTYPE, OFALL:
 494
 495         // Expression statements
 496         case OCALLFUNC, OCALLMETH, OCALLINTER:
 497                 s.call(n, callNormal)
 498         case ODEFER:
 499                 s.call(n.Left, callDefer)
 500         case OPROC:
 501                 s.call(n.Left, callGo)
 502
 503         case OAS2DOTTYPE:
 504                 res, resok := s.dottype(n.Rlist.N, true)
 505                 s.assign(n.List.N, res, false)
 506                 s.assign(n.List.Next.N, resok, false)
 507                 return
 508
 509         case ODCL:
 510                 if n.Left.Class&PHEAP == 0 {
 511                         return
 512                 }
 513                 if compiling_runtime != 0 {
 514                         Fatalf("%v escapes to heap, not allowed in runtime.", n)
 515                 }
 516
 517                 // TODO: the old pass hides the details of PHEAP
 518                 // variables behind ONAME nodes. Figure out if it's better
 519                 // to rewrite the tree and make the heapaddr construct explicit
 520                 // or to keep this detail hidden behind the scenes.
 521                 palloc := prealloc[n.Left]
 522                 if palloc == nil {
 523                         palloc = callnew(n.Left.Type)
 524                         prealloc[n.Left] = palloc
 525                 }
 526                 r := s.expr(palloc)
 527                 s.assign(n.Left.Name.Heapaddr, r, false)
 528
 529         case OLABEL:
 530                 sym := n.Left.Sym
 531
 532                 if isblanksym(sym) {
 533                         // Empty identifier is valid but useless.
 534                         // See issues 11589, 11593.
 535                         return
 536                 }
 537
 538                 lab := s.label(sym)
 539
 540                 // Associate label with its control flow node, if any
 541                 if ctl := n.Name.Defn; ctl != nil {
 542                         switch ctl.Op {
 543                         case OFOR, OSWITCH, OSELECT:
 544                                 s.labeledNodes[ctl] = lab
 545                         }
 546                 }
 547
 548                 if !lab.defined() {
 549                         lab.defNode = n
 550                 } else {
 551                         s.Error("label %v already defined at %v", sym, Ctxt.Line(int(lab.defNode.Lineno)))
 552                         lab.reported = true
 553                 }
 554                 // The label might already have a target block via a goto.
 555                 if lab.target == nil {
 556                         lab.target = s.f.NewBlock(ssa.BlockPlain)
 557                 }
 558
 559                 // go to that label (we pretend "label:" is preceded by "goto label")
 560                 b := s.endBlock()
 561                 b.AddEdgeTo(lab.target)
 562                 s.startBlock(lab.target)
 563
 564         case OGOTO:
 565                 sym := n.Left.Sym
 566
 567                 lab := s.label(sym)
 568                 if lab.target == nil {
 569                         lab.target = s.f.NewBlock(ssa.BlockPlain)
 570                 }
 571                 if !lab.used() {
 572                         lab.useNode = n
 573                 }
 574
 575                 if lab.defined() {
 576                         s.checkgoto(n, lab.defNode)
 577                 } else {
 578                         s.fwdGotos = append(s.fwdGotos, n)
 579                 }
 580
 581                 b := s.endBlock()
 582                 b.AddEdgeTo(lab.target)
 583
 584         case OAS, OASWB:
 585                 // Check whether we can generate static data rather than code.
 586                 // If so, ignore n and defer data generation until codegen.
 587                 // Failure to do this causes writes to readonly symbols.
 588                 if gen_as_init(n, true) {
 589                         var data []*Node
 590                         if s.f.StaticData != nil {
 591                                 data = s.f.StaticData.([]*Node)
 592                         }
 593                         s.f.StaticData = append(data, n)
 594                         return
 595                 }
 596                 var r *ssa.Value
 597                 if n.Right != nil {
 598                         if n.Right.Op == OSTRUCTLIT || n.Right.Op == OARRAYLIT {
 599                                 // All literals with nonzero fields have already been
 600                                 // rewritten during walk.  Any that remain are just T{}
 601                                 // or equivalents.  Leave r = nil to get zeroing behavior.
 602                                 if !iszero(n.Right) {
 603                                         Fatalf("literal with nonzero value in SSA: %v", n.Right)
 604                                 }
 605                         } else {
 606                                 r = s.expr(n.Right)
 607                         }
 608                 }
 609                 if n.Right != nil && n.Right.Op == OAPPEND {
 610                         // Yuck!  The frontend gets rid of the write barrier, but we need it!
 611                         // At least, we need it in the case where growslice is called.
 612                         // TODO: Do the write barrier on just the growslice branch.
 613                         // TODO: just add a ptr graying to the end of growslice?
 614                         // TODO: check whether we need to do this for ODOTTYPE and ORECV also.
 615                         // They get similar wb-removal treatment in walk.go:OAS.
 616                         s.assign(n.Left, r, true)
 617                         return
 618                 }
 619                 s.assign(n.Left, r, n.Op == OASWB)
 620
 621         case OIF:
 622                 cond := s.expr(n.Left)
 623                 b := s.endBlock()
 624                 b.Kind = ssa.BlockIf
 625                 b.Control = cond
 626                 b.Likely = ssa.BranchPrediction(n.Likely) // gc and ssa both use -1/0/+1 for likeliness
 627
 628                 bThen := s.f.NewBlock(ssa.BlockPlain)
 629                 bEnd := s.f.NewBlock(ssa.BlockPlain)
 630                 var bElse *ssa.Block
 631
 632                 if n.Rlist == nil {
 633                         b.AddEdgeTo(bThen)
 634                         b.AddEdgeTo(bEnd)
 635                 } else {
 636                         bElse = s.f.NewBlock(ssa.BlockPlain)
 637                         b.AddEdgeTo(bThen)
 638                         b.AddEdgeTo(bElse)
 639                 }
 640
 641                 s.startBlock(bThen)
 642                 s.stmtList(n.Nbody)
 643                 if b := s.endBlock(); b != nil {
 644                         b.AddEdgeTo(bEnd)
 645                 }
 646
 647                 if n.Rlist != nil {
 648                         s.startBlock(bElse)
 649                         s.stmtList(n.Rlist)
 650                         if b := s.endBlock(); b != nil {
 651                                 b.AddEdgeTo(bEnd)
 652                         }
 653                 }
 654                 s.startBlock(bEnd)
 655
 656         case ORETURN:
 657                 s.stmtList(n.List)
 658                 s.stmtList(s.exitCode)
 659                 m := s.mem()
 660                 b := s.endBlock()
 661                 b.Kind = ssa.BlockRet
 662                 b.Control = m
 663         case ORETJMP:
 664                 s.stmtList(n.List)
 665                 s.stmtList(s.exitCode)
 666                 m := s.mem()
 667                 b := s.endBlock()
 668                 b.Kind = ssa.BlockRetJmp
 669                 b.Aux = n.Left.Sym
 670                 b.Control = m
 671
 672         case OCONTINUE, OBREAK:
 673                 var op string
 674                 var to *ssa.Block
 675                 switch n.Op {
 676                 case OCONTINUE:
 677                         op = "continue"
 678                         to = s.continueTo
 679                 case OBREAK:
 680                         op = "break"
 681                         to = s.breakTo
 682                 }
 683                 if n.Left == nil {
 684                         // plain break/continue
 685                         if to == nil {
 686                                 s.Error("%s is not in a loop", op)
 687                                 return
 688                         }
 689                         // nothing to do; "to" is already the correct target
 690                 } else {
 691                         // labeled break/continue; look up the target
 692                         sym := n.Left.Sym
 693                         lab := s.label(sym)
 694                         if !lab.used() {
 695                                 lab.useNode = n.Left
 696                         }
 697                         if !lab.defined() {
 698                                 s.Error("%s label not defined: %v", op, sym)
 699                                 lab.reported = true
 700                                 return
 701                         }
 702                         switch n.Op {
 703                         case OCONTINUE:
 704                                 to = lab.continueTarget
 705                         case OBREAK:
 706                                 to = lab.breakTarget
 707                         }
 708                         if to == nil {
 709                                 // Valid label but not usable with a break/continue here, e.g.:
 710                                 // for {
 711                                 //      continue abc
 712                                 // }
 713                                 // abc:
 714                                 // for {}
 715                                 s.Error("invalid %s label %v", op, sym)
 716                                 lab.reported = true
 717                                 return
 718                         }
 719                 }
 720
 721                 b := s.endBlock()
 722                 b.AddEdgeTo(to)
 723
 724         case OFOR:
 725                 // OFOR: for Ninit; Left; Right { Nbody }
 726                 bCond := s.f.NewBlock(ssa.BlockPlain)
 727                 bBody := s.f.NewBlock(ssa.BlockPlain)
 728                 bIncr := s.f.NewBlock(ssa.BlockPlain)
 729                 bEnd := s.f.NewBlock(ssa.BlockPlain)
 730
 731                 // first, jump to condition test
 732                 b := s.endBlock()
 733                 b.AddEdgeTo(bCond)
 734
 735                 // generate code to test condition
 736                 s.startBlock(bCond)
 737                 var cond *ssa.Value
 738                 if n.Left != nil {
 739                         cond = s.expr(n.Left)
 740                 } else {
 741                         cond = s.constBool(true)
 742                 }
 743                 b = s.endBlock()
 744                 b.Kind = ssa.BlockIf
 745                 b.Control = cond
 746                 b.Likely = ssa.BranchLikely
 747                 b.AddEdgeTo(bBody)
 748                 b.AddEdgeTo(bEnd)
 749
 750                 // set up for continue/break in body
 751                 prevContinue := s.continueTo
 752                 prevBreak := s.breakTo
 753                 s.continueTo = bIncr
 754                 s.breakTo = bEnd
 755                 lab := s.labeledNodes[n]
 756                 if lab != nil {
 757                         // labeled for loop
 758                         lab.continueTarget = bIncr
 759                         lab.breakTarget = bEnd
 760                 }
 761
 762                 // generate body
 763                 s.startBlock(bBody)
 764                 s.stmtList(n.Nbody)
 765
 766                 // tear down continue/break
 767                 s.continueTo = prevContinue
 768                 s.breakTo = prevBreak
 769                 if lab != nil {
 770                         lab.continueTarget = nil
 771                         lab.breakTarget = nil
 772                 }
 773
 774                 // done with body, goto incr
 775                 if b := s.endBlock(); b != nil {
 776                         b.AddEdgeTo(bIncr)
 777                 }
 778
 779                 // generate incr
 780                 s.startBlock(bIncr)
 781                 if n.Right != nil {
 782                         s.stmt(n.Right)
 783                 }
 784                 if b := s.endBlock(); b != nil {
 785                         b.AddEdgeTo(bCond)
 786                 }
 787                 s.startBlock(bEnd)
 788
 789         case OSWITCH, OSELECT:
 790                 // These have been mostly rewritten by the front end into their Nbody fields.
 791                 // Our main task is to correctly hook up any break statements.
 792                 bEnd := s.f.NewBlock(ssa.BlockPlain)
 793
 794                 prevBreak := s.breakTo
 795                 s.breakTo = bEnd
 796                 lab := s.labeledNodes[n]
 797                 if lab != nil {
 798                         // labeled
 799                         lab.breakTarget = bEnd
 800                 }
 801
 802                 // generate body code
 803                 s.stmtList(n.Nbody)
 804
 805                 s.breakTo = prevBreak
 806                 if lab != nil {
 807                         lab.breakTarget = nil
 808                 }
 809
 810                 if b := s.endBlock(); b != nil {
 811                         b.AddEdgeTo(bEnd)
 812                 }
 813                 s.startBlock(bEnd)
 814
 815         case OVARKILL:
 816                 // Insert a varkill op to record that a variable is no longer live.
 817                 // We only care about liveness info at call sites, so putting the
 818                 // varkill in the store chain is enough to keep it correctly ordered
 819                 // with respect to call ops.
 820                 if !canSSA(n.Left) {
 821                         s.vars[&memVar] = s.newValue1A(ssa.OpVarKill, ssa.TypeMem, n.Left, s.mem())
 822                 }
 823
 824         case OCHECKNIL:
 825                 p := s.expr(n.Left)
 826                 s.nilCheck(p)
 827
 828         default:
 829                 s.Unimplementedf("unhandled stmt %s", opnames[n.Op])
 830         }
 831 }
 832
 833 type opAndType struct {
 834         op    uint8
 835         etype uint8
 836 }
 837
 838 var opToSSA = map[opAndType]ssa.Op{
 839         opAndType{OADD, TINT8}:    ssa.OpAdd8,
 840         opAndType{OADD, TUINT8}:   ssa.OpAdd8,
 841         opAndType{OADD, TINT16}:   ssa.OpAdd16,
 842         opAndType{OADD, TUINT16}:  ssa.OpAdd16,
 843         opAndType{OADD, TINT32}:   ssa.OpAdd32,
 844         opAndType{OADD, TUINT32}:  ssa.OpAdd32,
 845         opAndType{OADD, TPTR32}:   ssa.OpAdd32,
 846         opAndType{OADD, TINT64}:   ssa.OpAdd64,
 847         opAndType{OADD, TUINT64}:  ssa.OpAdd64,
 848         opAndType{OADD, TPTR64}:   ssa.OpAdd64,
 849         opAndType{OADD, TFLOAT32}: ssa.OpAdd32F,
 850         opAndType{OADD, TFLOAT64}: ssa.OpAdd64F,
 851
 852         opAndType{OSUB, TINT8}:    ssa.OpSub8,
 853         opAndType{OSUB, TUINT8}:   ssa.OpSub8,
 854         opAndType{OSUB, TINT16}:   ssa.OpSub16,
 855         opAndType{OSUB, TUINT16}:  ssa.OpSub16,
 856         opAndType{OSUB, TINT32}:   ssa.OpSub32,
 857         opAndType{OSUB, TUINT32}:  ssa.OpSub32,
 858         opAndType{OSUB, TINT64}:   ssa.OpSub64,
 859         opAndType{OSUB, TUINT64}:  ssa.OpSub64,
 860         opAndType{OSUB, TFLOAT32}: ssa.OpSub32F,
 861         opAndType{OSUB, TFLOAT64}: ssa.OpSub64F,
 862
 863         opAndType{ONOT, TBOOL}: ssa.OpNot,
 864
 865         opAndType{OMINUS, TINT8}:    ssa.OpNeg8,
 866         opAndType{OMINUS, TUINT8}:   ssa.OpNeg8,
 867         opAndType{OMINUS, TINT16}:   ssa.OpNeg16,
 868         opAndType{OMINUS, TUINT16}:  ssa.OpNeg16,
 869         opAndType{OMINUS, TINT32}:   ssa.OpNeg32,
 870         opAndType{OMINUS, TUINT32}:  ssa.OpNeg32,
 871         opAndType{OMINUS, TINT64}:   ssa.OpNeg64,
 872         opAndType{OMINUS, TUINT64}:  ssa.OpNeg64,
 873         opAndType{OMINUS, TFLOAT32}: ssa.OpNeg32F,
 874         opAndType{OMINUS, TFLOAT64}: ssa.OpNeg64F,
 875
 876         opAndType{OCOM, TINT8}:   ssa.OpCom8,
 877         opAndType{OCOM, TUINT8}:  ssa.OpCom8,
 878         opAndType{OCOM, TINT16}:  ssa.OpCom16,
 879         opAndType{OCOM, TUINT16}: ssa.OpCom16,
 880         opAndType{OCOM, TINT32}:  ssa.OpCom32,
 881         opAndType{OCOM, TUINT32}: ssa.OpCom32,
 882         opAndType{OCOM, TINT64}:  ssa.OpCom64,
 883         opAndType{OCOM, TUINT64}: ssa.OpCom64,
 884
 885         opAndType{OIMAG, TCOMPLEX64}:  ssa.OpComplexImag,
 886         opAndType{OIMAG, TCOMPLEX128}: ssa.OpComplexImag,
 887         opAndType{OREAL, TCOMPLEX64}:  ssa.OpComplexReal,
 888         opAndType{OREAL, TCOMPLEX128}: ssa.OpComplexReal,
 889
 890         opAndType{OMUL, TINT8}:    ssa.OpMul8,
 891         opAndType{OMUL, TUINT8}:   ssa.OpMul8,
 892         opAndType{OMUL, TINT16}:   ssa.OpMul16,
 893         opAndType{OMUL, TUINT16}:  ssa.OpMul16,
 894         opAndType{OMUL, TINT32}:   ssa.OpMul32,
 895         opAndType{OMUL, TUINT32}:  ssa.OpMul32,
 896         opAndType{OMUL, TINT64}:   ssa.OpMul64,
 897         opAndType{OMUL, TUINT64}:  ssa.OpMul64,
 898         opAndType{OMUL, TFLOAT32}: ssa.OpMul32F,
 899         opAndType{OMUL, TFLOAT64}: ssa.OpMul64F,
 900
 901         opAndType{ODIV, TFLOAT32}: ssa.OpDiv32F,
 902         opAndType{ODIV, TFLOAT64}: ssa.OpDiv64F,
 903
 904         opAndType{OHMUL, TINT8}:   ssa.OpHmul8,
 905         opAndType{OHMUL, TUINT8}:  ssa.OpHmul8u,
 906         opAndType{OHMUL, TINT16}:  ssa.OpHmul16,
 907         opAndType{OHMUL, TUINT16}: ssa.OpHmul16u,
 908         opAndType{OHMUL, TINT32}:  ssa.OpHmul32,
 909         opAndType{OHMUL, TUINT32}: ssa.OpHmul32u,
 910
 911         opAndType{ODIV, TINT8}:   ssa.OpDiv8,
 912         opAndType{ODIV, TUINT8}:  ssa.OpDiv8u,
 913         opAndType{ODIV, TINT16}:  ssa.OpDiv16,
 914         opAndType{ODIV, TUINT16}: ssa.OpDiv16u,
 915         opAndType{ODIV, TINT32}:  ssa.OpDiv32,
 916         opAndType{ODIV, TUINT32}: ssa.OpDiv32u,
 917         opAndType{ODIV, TINT64}:  ssa.OpDiv64,
 918         opAndType{ODIV, TUINT64}: ssa.OpDiv64u,
 919
 920         opAndType{OMOD, TINT8}:   ssa.OpMod8,
 921         opAndType{OMOD, TUINT8}:  ssa.OpMod8u,
 922         opAndType{OMOD, TINT16}:  ssa.OpMod16,
 923         opAndType{OMOD, TUINT16}: ssa.OpMod16u,
 924         opAndType{OMOD, TINT32}:  ssa.OpMod32,
 925         opAndType{OMOD, TUINT32}: ssa.OpMod32u,
 926         opAndType{OMOD, TINT64}:  ssa.OpMod64,
 927         opAndType{OMOD, TUINT64}: ssa.OpMod64u,
 928
 929         opAndType{OAND, TINT8}:   ssa.OpAnd8,
 930         opAndType{OAND, TUINT8}:  ssa.OpAnd8,
 931         opAndType{OAND, TINT16}:  ssa.OpAnd16,
 932         opAndType{OAND, TUINT16}: ssa.OpAnd16,
 933         opAndType{OAND, TINT32}:  ssa.OpAnd32,
 934         opAndType{OAND, TUINT32}: ssa.OpAnd32,
 935         opAndType{OAND, TINT64}:  ssa.OpAnd64,
 936         opAndType{OAND, TUINT64}: ssa.OpAnd64,
 937
 938         opAndType{OOR, TINT8}:   ssa.OpOr8,
 939         opAndType{OOR, TUINT8}:  ssa.OpOr8,
 940         opAndType{OOR, TINT16}:  ssa.OpOr16,
 941         opAndType{OOR, TUINT16}: ssa.OpOr16,
 942         opAndType{OOR, TINT32}:  ssa.OpOr32,
 943         opAndType{OOR, TUINT32}: ssa.OpOr32,
 944         opAndType{OOR, TINT64}:  ssa.OpOr64,
 945         opAndType{OOR, TUINT64}: ssa.OpOr64,
 946
 947         opAndType{OXOR, TINT8}:   ssa.OpXor8,
 948         opAndType{OXOR, TUINT8}:  ssa.OpXor8,
 949         opAndType{OXOR, TINT16}:  ssa.OpXor16,
 950         opAndType{OXOR, TUINT16}: ssa.OpXor16,
 951         opAndType{OXOR, TINT32}:  ssa.OpXor32,
 952         opAndType{OXOR, TUINT32}: ssa.OpXor32,
 953         opAndType{OXOR, TINT64}:  ssa.OpXor64,
 954         opAndType{OXOR, TUINT64}: ssa.OpXor64,
 955
 956         opAndType{OEQ, TBOOL}:      ssa.OpEq8,
 957         opAndType{OEQ, TINT8}:      ssa.OpEq8,
 958         opAndType{OEQ, TUINT8}:     ssa.OpEq8,
 959         opAndType{OEQ, TINT16}:     ssa.OpEq16,
 960         opAndType{OEQ, TUINT16}:    ssa.OpEq16,
 961         opAndType{OEQ, TINT32}:     ssa.OpEq32,
 962         opAndType{OEQ, TUINT32}:    ssa.OpEq32,
 963         opAndType{OEQ, TINT64}:     ssa.OpEq64,
 964         opAndType{OEQ, TUINT64}:    ssa.OpEq64,
 965         opAndType{OEQ, TINTER}:     ssa.OpEqInter,
 966         opAndType{OEQ, TARRAY}:     ssa.OpEqSlice,
 967         opAndType{OEQ, TFUNC}:      ssa.OpEqPtr,
 968         opAndType{OEQ, TMAP}:       ssa.OpEqPtr,
 969         opAndType{OEQ, TCHAN}:      ssa.OpEqPtr,
 970         opAndType{OEQ, TPTR64}:     ssa.OpEqPtr,
 971         opAndType{OEQ, TUINTPTR}:   ssa.OpEqPtr,
 972         opAndType{OEQ, TUNSAFEPTR}: ssa.OpEqPtr,
 973         opAndType{OEQ, TFLOAT64}:   ssa.OpEq64F,
 974         opAndType{OEQ, TFLOAT32}:   ssa.OpEq32F,
 975
 976         opAndType{ONE, TBOOL}:      ssa.OpNeq8,
 977         opAndType{ONE, TINT8}:      ssa.OpNeq8,
 978         opAndType{ONE, TUINT8}:     ssa.OpNeq8,
 979         opAndType{ONE, TINT16}:     ssa.OpNeq16,
 980         opAndType{ONE, TUINT16}:    ssa.OpNeq16,
 981         opAndType{ONE, TINT32}:     ssa.OpNeq32,
 982         opAndType{ONE, TUINT32}:    ssa.OpNeq32,
 983         opAndType{ONE, TINT64}:     ssa.OpNeq64,
 984         opAndType{ONE, TUINT64}:    ssa.OpNeq64,
 985         opAndType{ONE, TINTER}:     ssa.OpNeqInter,
 986         opAndType{ONE, TARRAY}:     ssa.OpNeqSlice,
 987         opAndType{ONE, TFUNC}:      ssa.OpNeqPtr,
 988         opAndType{ONE, TMAP}:       ssa.OpNeqPtr,
 989         opAndType{ONE, TCHAN}:      ssa.OpNeqPtr,
 990         opAndType{ONE, TPTR64}:     ssa.OpNeqPtr,
 991         opAndType{ONE, TUINTPTR}:   ssa.OpNeqPtr,
 992         opAndType{ONE, TUNSAFEPTR}: ssa.OpNeqPtr,
 993         opAndType{ONE, TFLOAT64}:   ssa.OpNeq64F,
 994         opAndType{ONE, TFLOAT32}:   ssa.OpNeq32F,
 995
 996         opAndType{OLT, TINT8}:    ssa.OpLess8,
 997         opAndType{OLT, TUINT8}:   ssa.OpLess8U,
 998         opAndType{OLT, TINT16}:   ssa.OpLess16,
 999         opAndType{OLT, TUINT16}:  ssa.OpLess16U,
1000         opAndType{OLT, TINT32}:   ssa.OpLess32,
1001         opAndType{OLT, TUINT32}:  ssa.OpLess32U,
1002         opAndType{OLT, TINT64}:   ssa.OpLess64,
1003         opAndType{OLT, TUINT64}:  ssa.OpLess64U,
1004         opAndType{OLT, TFLOAT64}: ssa.OpLess64F,
1005         opAndType{OLT, TFLOAT32}: ssa.OpLess32F,
1006
1007         opAndType{OGT, TINT8}:    ssa.OpGreater8,
1008         opAndType{OGT, TUINT8}:   ssa.OpGreater8U,
1009         opAndType{OGT, TINT16}:   ssa.OpGreater16,
1010         opAndType{OGT, TUINT16}:  ssa.OpGreater16U,
1011         opAndType{OGT, TINT32}:   ssa.OpGreater32,
1012         opAndType{OGT, TUINT32}:  ssa.OpGreater32U,
1013         opAndType{OGT, TINT64}:   ssa.OpGreater64,
1014         opAndType{OGT, TUINT64}:  ssa.OpGreater64U,
1015         opAndType{OGT, TFLOAT64}: ssa.OpGreater64F,
1016         opAndType{OGT, TFLOAT32}: ssa.OpGreater32F,
1017
1018         opAndType{OLE, TINT8}:    ssa.OpLeq8,
1019         opAndType{OLE, TUINT8}:   ssa.OpLeq8U,
1020         opAndType{OLE, TINT16}:   ssa.OpLeq16,
1021         opAndType{OLE, TUINT16}:  ssa.OpLeq16U,
1022         opAndType{OLE, TINT32}:   ssa.OpLeq32,
1023         opAndType{OLE, TUINT32}:  ssa.OpLeq32U,
1024         opAndType{OLE, TINT64}:   ssa.OpLeq64,
1025         opAndType{OLE, TUINT64}:  ssa.OpLeq64U,
1026         opAndType{OLE, TFLOAT64}: ssa.OpLeq64F,
1027         opAndType{OLE, TFLOAT32}: ssa.OpLeq32F,
1028
1029         opAndType{OGE, TINT8}:    ssa.OpGeq8,
1030         opAndType{OGE, TUINT8}:   ssa.OpGeq8U,
1031         opAndType{OGE, TINT16}:   ssa.OpGeq16,
1032         opAndType{OGE, TUINT16}:  ssa.OpGeq16U,
1033         opAndType{OGE, TINT32}:   ssa.OpGeq32,
1034         opAndType{OGE, TUINT32}:  ssa.OpGeq32U,
1035         opAndType{OGE, TINT64}:   ssa.OpGeq64,
1036         opAndType{OGE, TUINT64}:  ssa.OpGeq64U,
1037         opAndType{OGE, TFLOAT64}: ssa.OpGeq64F,
1038         opAndType{OGE, TFLOAT32}: ssa.OpGeq32F,
1039
1040         opAndType{OLROT, TUINT8}:  ssa.OpLrot8,
1041         opAndType{OLROT, TUINT16}: ssa.OpLrot16,
1042         opAndType{OLROT, TUINT32}: ssa.OpLrot32,
1043         opAndType{OLROT, TUINT64}: ssa.OpLrot64,
1044
1045         opAndType{OSQRT, TFLOAT64}: ssa.OpSqrt,
1046 }
1047
1048 func (s *state) concreteEtype(t *Type) uint8 {
1049         e := t.Etype
1050         switch e {
1051         default:
1052                 return e
1053         case TINT:
1054                 if s.config.IntSize == 8 {
1055                         return TINT64
1056                 }
1057                 return TINT32
1058         case TUINT:
1059                 if s.config.IntSize == 8 {
1060                         return TUINT64
1061                 }
1062                 return TUINT32
1063         case TUINTPTR:
1064                 if s.config.PtrSize == 8 {
1065                         return TUINT64
1066                 }
1067                 return TUINT32
1068         }
1069 }
1070
1071 func (s *state) ssaOp(op uint8, t *Type) ssa.Op {
1072         etype := s.concreteEtype(t)
1073         x, ok := opToSSA[opAndType{op, etype}]
1074         if !ok {
1075                 s.Unimplementedf("unhandled binary op %s %s", opnames[op], Econv(int(etype), 0))
1076         }
1077         return x
1078 }
1079
1080 func floatForComplex(t *Type) *Type {
1081         if t.Size() == 8 {
1082                 return Types[TFLOAT32]
1083         } else {
1084                 return Types[TFLOAT64]
1085         }
1086 }
1087
1088 type opAndTwoTypes struct {
1089         op     uint8
1090         etype1 uint8
1091         etype2 uint8
1092 }
1093
1094 type twoTypes struct {
1095         etype1 uint8
1096         etype2 uint8
1097 }
1098
1099 type twoOpsAndType struct {
1100         op1              ssa.Op
1101         op2              ssa.Op
1102         intermediateType uint8
1103 }
1104
1105 var fpConvOpToSSA = map[twoTypes]twoOpsAndType{
1106
1107         twoTypes{TINT8, TFLOAT32}:  twoOpsAndType{ssa.OpSignExt8to32, ssa.OpCvt32to32F, TINT32},
1108         twoTypes{TINT16, TFLOAT32}: twoOpsAndType{ssa.OpSignExt16to32, ssa.OpCvt32to32F, TINT32},
1109         twoTypes{TINT32, TFLOAT32}: twoOpsAndType{ssa.OpCopy, ssa.OpCvt32to32F, TINT32},
1110         twoTypes{TINT64, TFLOAT32}: twoOpsAndType{ssa.OpCopy, ssa.OpCvt64to32F, TINT64},
1111
1112         twoTypes{TINT8, TFLOAT64}:  twoOpsAndType{ssa.OpSignExt8to32, ssa.OpCvt32to64F, TINT32},
1113         twoTypes{TINT16, TFLOAT64}: twoOpsAndType{ssa.OpSignExt16to32, ssa.OpCvt32to64F, TINT32},
1114         twoTypes{TINT32, TFLOAT64}: twoOpsAndType{ssa.OpCopy, ssa.OpCvt32to64F, TINT32},
1115         twoTypes{TINT64, TFLOAT64}: twoOpsAndType{ssa.OpCopy, ssa.OpCvt64to64F, TINT64},
1116
1117         twoTypes{TFLOAT32, TINT8}:  twoOpsAndType{ssa.OpCvt32Fto32, ssa.OpTrunc32to8, TINT32},
1118         twoTypes{TFLOAT32, TINT16}: twoOpsAndType{ssa.OpCvt32Fto32, ssa.OpTrunc32to16, TINT32},
1119         twoTypes{TFLOAT32, TINT32}: twoOpsAndType{ssa.OpCvt32Fto32, ssa.OpCopy, TINT32},
1120         twoTypes{TFLOAT32, TINT64}: twoOpsAndType{ssa.OpCvt32Fto64, ssa.OpCopy, TINT64},
1121
1122         twoTypes{TFLOAT64, TINT8}:  twoOpsAndType{ssa.OpCvt64Fto32, ssa.OpTrunc32to8, TINT32},
1123         twoTypes{TFLOAT64, TINT16}: twoOpsAndType{ssa.OpCvt64Fto32, ssa.OpTrunc32to16, TINT32},
1124         twoTypes{TFLOAT64, TINT32}: twoOpsAndType{ssa.OpCvt64Fto32, ssa.OpCopy, TINT32},
1125         twoTypes{TFLOAT64, TINT64}: twoOpsAndType{ssa.OpCvt64Fto64, ssa.OpCopy, TINT64},
1126         // unsigned
1127         twoTypes{TUINT8, TFLOAT32}:  twoOpsAndType{ssa.OpZeroExt8to32, ssa.OpCvt32to32F, TINT32},
1128         twoTypes{TUINT16, TFLOAT32}: twoOpsAndType{ssa.OpZeroExt16to32, ssa.OpCvt32to32F, TINT32},
1129         twoTypes{TUINT32, TFLOAT32}: twoOpsAndType{ssa.OpZeroExt32to64, ssa.OpCvt64to32F, TINT64}, // go wide to dodge unsigned
1130         twoTypes{TUINT64, TFLOAT32}: twoOpsAndType{ssa.OpCopy, ssa.OpInvalid, TUINT64},            // Cvt64Uto32F, branchy code expansion instead
1131
1132         twoTypes{TUINT8, TFLOAT64}:  twoOpsAndType{ssa.OpZeroExt8to32, ssa.OpCvt32to64F, TINT32},
1133         twoTypes{TUINT16, TFLOAT64}: twoOpsAndType{ssa.OpZeroExt16to32, ssa.OpCvt32to64F, TINT32},
1134         twoTypes{TUINT32, TFLOAT64}: twoOpsAndType{ssa.OpZeroExt32to64, ssa.OpCvt64to64F, TINT64}, // go wide to dodge unsigned
1135         twoTypes{TUINT64, TFLOAT64}: twoOpsAndType{ssa.OpCopy, ssa.OpInvalid, TUINT64},            // Cvt64Uto64F, branchy code expansion instead
1136
1137         twoTypes{TFLOAT32, TUINT8}:  twoOpsAndType{ssa.OpCvt32Fto32, ssa.OpTrunc32to8, TINT32},
1138         twoTypes{TFLOAT32, TUINT16}: twoOpsAndType{ssa.OpCvt32Fto32, ssa.OpTrunc32to16, TINT32},
1139         twoTypes{TFLOAT32, TUINT32}: twoOpsAndType{ssa.OpCvt32Fto64, ssa.OpTrunc64to32, TINT64}, // go wide to dodge unsigned
1140         twoTypes{TFLOAT32, TUINT64}: twoOpsAndType{ssa.OpInvalid, ssa.OpCopy, TUINT64},          // Cvt32Fto64U, branchy code expansion instead
1141
1142         twoTypes{TFLOAT64, TUINT8}:  twoOpsAndType{ssa.OpCvt64Fto32, ssa.OpTrunc32to8, TINT32},
1143         twoTypes{TFLOAT64, TUINT16}: twoOpsAndType{ssa.OpCvt64Fto32, ssa.OpTrunc32to16, TINT32},
1144         twoTypes{TFLOAT64, TUINT32}: twoOpsAndType{ssa.OpCvt64Fto64, ssa.OpTrunc64to32, TINT64}, // go wide to dodge unsigned
1145         twoTypes{TFLOAT64, TUINT64}: twoOpsAndType{ssa.OpInvalid, ssa.OpCopy, TUINT64},          // Cvt64Fto64U, branchy code expansion instead
1146
1147         // float
1148         twoTypes{TFLOAT64, TFLOAT32}: twoOpsAndType{ssa.OpCvt64Fto32F, ssa.OpCopy, TFLOAT32},
1149         twoTypes{TFLOAT64, TFLOAT64}: twoOpsAndType{ssa.OpCopy, ssa.OpCopy, TFLOAT64},
1150         twoTypes{TFLOAT32, TFLOAT32}: twoOpsAndType{ssa.OpCopy, ssa.OpCopy, TFLOAT32},
1151         twoTypes{TFLOAT32, TFLOAT64}: twoOpsAndType{ssa.OpCvt32Fto64F, ssa.OpCopy, TFLOAT64},
1152 }
1153
1154 var shiftOpToSSA = map[opAndTwoTypes]ssa.Op{
1155         opAndTwoTypes{OLSH, TINT8, TUINT8}:   ssa.OpLsh8x8,
1156         opAndTwoTypes{OLSH, TUINT8, TUINT8}:  ssa.OpLsh8x8,
1157         opAndTwoTypes{OLSH, TINT8, TUINT16}:  ssa.OpLsh8x16,
1158         opAndTwoTypes{OLSH, TUINT8, TUINT16}: ssa.OpLsh8x16,
1159         opAndTwoTypes{OLSH, TINT8, TUINT32}:  ssa.OpLsh8x32,
1160         opAndTwoTypes{OLSH, TUINT8, TUINT32}: ssa.OpLsh8x32,
1161         opAndTwoTypes{OLSH, TINT8, TUINT64}:  ssa.OpLsh8x64,
1162         opAndTwoTypes{OLSH, TUINT8, TUINT64}: ssa.OpLsh8x64,
1163
1164         opAndTwoTypes{OLSH, TINT16, TUINT8}:   ssa.OpLsh16x8,
1165         opAndTwoTypes{OLSH, TUINT16, TUINT8}:  ssa.OpLsh16x8,
1166         opAndTwoTypes{OLSH, TINT16, TUINT16}:  ssa.OpLsh16x16,
1167         opAndTwoTypes{OLSH, TUINT16, TUINT16}: ssa.OpLsh16x16,
1168         opAndTwoTypes{OLSH, TINT16, TUINT32}:  ssa.OpLsh16x32,
1169         opAndTwoTypes{OLSH, TUINT16, TUINT32}: ssa.OpLsh16x32,
1170         opAndTwoTypes{OLSH, TINT16, TUINT64}:  ssa.OpLsh16x64,
1171         opAndTwoTypes{OLSH, TUINT16, TUINT64}: ssa.OpLsh16x64,
1172
1173         opAndTwoTypes{OLSH, TINT32, TUINT8}:   ssa.OpLsh32x8,
1174         opAndTwoTypes{OLSH, TUINT32, TUINT8}:  ssa.OpLsh32x8,
1175         opAndTwoTypes{OLSH, TINT32, TUINT16}:  ssa.OpLsh32x16,
1176         opAndTwoTypes{OLSH, TUINT32, TUINT16}: ssa.OpLsh32x16,
1177         opAndTwoTypes{OLSH, TINT32, TUINT32}:  ssa.OpLsh32x32,
1178         opAndTwoTypes{OLSH, TUINT32, TUINT32}: ssa.OpLsh32x32,
1179         opAndTwoTypes{OLSH, TINT32, TUINT64}:  ssa.OpLsh32x64,
1180         opAndTwoTypes{OLSH, TUINT32, TUINT64}: ssa.OpLsh32x64,
1181
1182         opAndTwoTypes{OLSH, TINT64, TUINT8}:   ssa.OpLsh64x8,
1183         opAndTwoTypes{OLSH, TUINT64, TUINT8}:  ssa.OpLsh64x8,
1184         opAndTwoTypes{OLSH, TINT64, TUINT16}:  ssa.OpLsh64x16,
1185         opAndTwoTypes{OLSH, TUINT64, TUINT16}: ssa.OpLsh64x16,
1186         opAndTwoTypes{OLSH, TINT64, TUINT32}:  ssa.OpLsh64x32,
1187         opAndTwoTypes{OLSH, TUINT64, TUINT32}: ssa.OpLsh64x32,
1188         opAndTwoTypes{OLSH, TINT64, TUINT64}:  ssa.OpLsh64x64,
1189         opAndTwoTypes{OLSH, TUINT64, TUINT64}: ssa.OpLsh64x64,
1190
1191         opAndTwoTypes{ORSH, TINT8, TUINT8}:   ssa.OpRsh8x8,
1192         opAndTwoTypes{ORSH, TUINT8, TUINT8}:  ssa.OpRsh8Ux8,
1193         opAndTwoTypes{ORSH, TINT8, TUINT16}:  ssa.OpRsh8x16,
1194         opAndTwoTypes{ORSH, TUINT8, TUINT16}: ssa.OpRsh8Ux16,
1195         opAndTwoTypes{ORSH, TINT8, TUINT32}:  ssa.OpRsh8x32,
1196         opAndTwoTypes{ORSH, TUINT8, TUINT32}: ssa.OpRsh8Ux32,
1197         opAndTwoTypes{ORSH, TINT8, TUINT64}:  ssa.OpRsh8x64,
1198         opAndTwoTypes{ORSH, TUINT8, TUINT64}: ssa.OpRsh8Ux64,
1199
1200         opAndTwoTypes{ORSH, TINT16, TUINT8}:   ssa.OpRsh16x8,
1201         opAndTwoTypes{ORSH, TUINT16, TUINT8}:  ssa.OpRsh16Ux8,
1202         opAndTwoTypes{ORSH, TINT16, TUINT16}:  ssa.OpRsh16x16,
1203         opAndTwoTypes{ORSH, TUINT16, TUINT16}: ssa.OpRsh16Ux16,
1204         opAndTwoTypes{ORSH, TINT16, TUINT32}:  ssa.OpRsh16x32,
1205         opAndTwoTypes{ORSH, TUINT16, TUINT32}: ssa.OpRsh16Ux32,
1206         opAndTwoTypes{ORSH, TINT16, TUINT64}:  ssa.OpRsh16x64,
1207         opAndTwoTypes{ORSH, TUINT16, TUINT64}: ssa.OpRsh16Ux64,
1208
1209         opAndTwoTypes{ORSH, TINT32, TUINT8}:   ssa.OpRsh32x8,
1210         opAndTwoTypes{ORSH, TUINT32, TUINT8}:  ssa.OpRsh32Ux8,
1211         opAndTwoTypes{ORSH, TINT32, TUINT16}:  ssa.OpRsh32x16,
1212         opAndTwoTypes{ORSH, TUINT32, TUINT16}: ssa.OpRsh32Ux16,
1213         opAndTwoTypes{ORSH, TINT32, TUINT32}:  ssa.OpRsh32x32,
1214         opAndTwoTypes{ORSH, TUINT32, TUINT32}: ssa.OpRsh32Ux32,
1215         opAndTwoTypes{ORSH, TINT32, TUINT64}:  ssa.OpRsh32x64,
1216         opAndTwoTypes{ORSH, TUINT32, TUINT64}: ssa.OpRsh32Ux64,
1217
1218         opAndTwoTypes{ORSH, TINT64, TUINT8}:   ssa.OpRsh64x8,
1219         opAndTwoTypes{ORSH, TUINT64, TUINT8}:  ssa.OpRsh64Ux8,
1220         opAndTwoTypes{ORSH, TINT64, TUINT16}:  ssa.OpRsh64x16,
1221         opAndTwoTypes{ORSH, TUINT64, TUINT16}: ssa.OpRsh64Ux16,
1222         opAndTwoTypes{ORSH, TINT64, TUINT32}:  ssa.OpRsh64x32,
1223         opAndTwoTypes{ORSH, TUINT64, TUINT32}: ssa.OpRsh64Ux32,
1224         opAndTwoTypes{ORSH, TINT64, TUINT64}:  ssa.OpRsh64x64,
1225         opAndTwoTypes{ORSH, TUINT64, TUINT64}: ssa.OpRsh64Ux64,
1226 }
1227
1228 func (s *state) ssaShiftOp(op uint8, t *Type, u *Type) ssa.Op {
1229         etype1 := s.concreteEtype(t)
1230         etype2 := s.concreteEtype(u)
1231         x, ok := shiftOpToSSA[opAndTwoTypes{op, etype1, etype2}]
1232         if !ok {
1233                 s.Unimplementedf("unhandled shift op %s etype=%s/%s", opnames[op], Econv(int(etype1), 0), Econv(int(etype2), 0))
1234         }
1235         return x
1236 }
1237
1238 func (s *state) ssaRotateOp(op uint8, t *Type) ssa.Op {
1239         etype1 := s.concreteEtype(t)
1240         x, ok := opToSSA[opAndType{op, etype1}]
1241         if !ok {
1242                 s.Unimplementedf("unhandled rotate op %s etype=%s", opnames[op], Econv(int(etype1), 0))
1243         }
1244         return x
1245 }
1246
1247 // expr converts the expression n to ssa, adds it to s and returns the ssa result.
1248 func (s *state) expr(n *Node) *ssa.Value {
1249         s.pushLine(n.Lineno)
1250         defer s.popLine()
1251
1252         s.stmtList(n.Ninit)
1253         switch n.Op {
1254         case OCFUNC:
1255                 aux := s.lookupSymbol(n, &ssa.ExternSymbol{n.Type, n.Left.Sym})
1256                 return s.entryNewValue1A(ssa.OpAddr, n.Type, aux, s.sb)
1257         case OPARAM:
1258                 addr := s.addr(n, false)
1259                 return s.newValue2(ssa.OpLoad, n.Left.Type, addr, s.mem())
1260         case ONAME:
1261                 if n.Class == PFUNC {
1262                         // "value" of a function is the address of the function's closure
1263                         sym := funcsym(n.Sym)
1264                         aux := &ssa.ExternSymbol{n.Type, sym}
1265                         return s.entryNewValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sb)
1266                 }
1267                 if canSSA(n) {
1268                         return s.variable(n, n.Type)
1269                 }
1270                 addr := s.addr(n, false)
1271                 return s.newValue2(ssa.OpLoad, n.Type, addr, s.mem())
1272         case OCLOSUREVAR:
1273                 addr := s.addr(n, false)
1274                 return s.newValue2(ssa.OpLoad, n.Type, addr, s.mem())
1275         case OLITERAL:
1276                 switch n.Val().Ctype() {
1277                 case CTINT:
1278                         i := Mpgetfix(n.Val().U.(*Mpint))
1279                         switch n.Type.Size() {
1280                         case 1:
1281                                 return s.constInt8(n.Type, int8(i))
1282                         case 2:
1283                                 return s.constInt16(n.Type, int16(i))
1284                         case 4:
1285                                 return s.constInt32(n.Type, int32(i))
1286                         case 8:
1287                                 return s.constInt64(n.Type, i)
1288                         default:
1289                                 s.Fatalf("bad integer size %d", n.Type.Size())
1290                                 return nil
1291                         }
1292                 case CTSTR:
1293                         return s.entryNewValue0A(ssa.OpConstString, n.Type, n.Val().U)
1294                 case CTBOOL:
1295                         return s.constBool(n.Val().U.(bool))
1296                 case CTNIL:
1297                         t := n.Type
1298                         switch {
1299                         case t.IsSlice():
1300                                 return s.entryNewValue0(ssa.OpConstSlice, t)
1301                         case t.IsInterface():
1302                                 return s.entryNewValue0(ssa.OpConstInterface, t)
1303                         default:
1304                                 return s.entryNewValue0(ssa.OpConstNil, t)
1305                         }
1306                 case CTFLT:
1307                         f := n.Val().U.(*Mpflt)
1308                         switch n.Type.Size() {
1309                         case 4:
1310                                 // -0.0 literals need to be treated as if they were 0.0, adding 0.0 here
1311                                 // accomplishes this while not affecting other values.
1312                                 return s.constFloat32(n.Type, mpgetflt32(f)+0.0)
1313                         case 8:
1314                                 return s.constFloat64(n.Type, mpgetflt(f)+0.0)
1315                         default:
1316                                 s.Fatalf("bad float size %d", n.Type.Size())
1317                                 return nil
1318                         }
1319                 case CTCPLX:
1320                         c := n.Val().U.(*Mpcplx)
1321                         r := &c.Real
1322                         i := &c.Imag
1323                         switch n.Type.Size() {
1324                         case 8:
1325                                 {
1326                                         pt := Types[TFLOAT32]
1327                                         // -0.0 literals need to be treated as if they were 0.0, adding 0.0 here
1328                                         // accomplishes this while not affecting other values.
1329                                         return s.newValue2(ssa.OpComplexMake, n.Type,
1330                                                 s.constFloat32(pt, mpgetflt32(r)+0.0),
1331                                                 s.constFloat32(pt, mpgetflt32(i)+0.0))
1332                                 }
1333                         case 16:
1334                                 {
1335                                         pt := Types[TFLOAT64]
1336                                         return s.newValue2(ssa.OpComplexMake, n.Type,
1337                                                 s.constFloat64(pt, mpgetflt(r)+0.0),
1338                                                 s.constFloat64(pt, mpgetflt(i)+0.0))
1339                                 }
1340                         default:
1341                                 s.Fatalf("bad float size %d", n.Type.Size())
1342                                 return nil
1343                         }
1344
1345                 default:
1346                         s.Unimplementedf("unhandled OLITERAL %v", n.Val().Ctype())
1347                         return nil
1348                 }
1349         case OCONVNOP:
1350                 to := n.Type
1351                 from := n.Left.Type
1352
1353                 // Assume everything will work out, so set up our return value.
1354                 // Anything interesting that happens from here is a fatal.
1355                 x := s.expr(n.Left)
1356                 v := s.newValue1(ssa.OpCopy, to, x) // ensure that v has the right type
1357
1358                 // CONVNOP closure
1359                 if to.Etype == TFUNC && from.IsPtr() {
1360                         return v
1361                 }
1362
1363                 // named <--> unnamed type or typed <--> untyped const
1364                 if from.Etype == to.Etype {
1365                         return v
1366                 }
1367                 // unsafe.Pointer <--> *T
1368                 if to.Etype == TUNSAFEPTR && from.IsPtr() || from.Etype == TUNSAFEPTR && to.IsPtr() {
1369                         return v
1370                 }
1371
1372                 dowidth(from)
1373                 dowidth(to)
1374                 if from.Width != to.Width {
1375                         s.Fatalf("CONVNOP width mismatch %v (%d) -> %v (%d)\n", from, from.Width, to, to.Width)
1376                         return nil
1377                 }
1378                 if etypesign(from.Etype) != etypesign(to.Etype) {
1379                         s.Fatalf("CONVNOP sign mismatch %v (%s) -> %v (%s)\n", from, Econv(int(from.Etype), 0), to, Econv(int(to.Etype), 0))
1380                         return nil
1381                 }
1382
1383                 if flag_race != 0 {
1384                         // These appear to be fine, but they fail the
1385                         // integer constraint below, so okay them here.
1386                         // Sample non-integer conversion: map[string]string -> *uint8
1387                         return v
1388                 }
1389
1390                 if etypesign(from.Etype) == 0 {
1391                         s.Fatalf("CONVNOP unrecognized non-integer %v -> %v\n", from, to)
1392                         return nil
1393                 }
1394
1395                 // integer, same width, same sign
1396                 return v
1397
1398         case OCONV:
1399                 x := s.expr(n.Left)
1400                 ft := n.Left.Type // from type
1401                 tt := n.Type      // to type
1402                 if ft.IsInteger() && tt.IsInteger() {
1403                         var op ssa.Op
1404                         if tt.Size() == ft.Size() {
1405                                 op = ssa.OpCopy
1406                         } else if tt.Size() < ft.Size() {
1407                                 // truncation
1408                                 switch 10*ft.Size() + tt.Size() {
1409                                 case 21:
1410                                         op = ssa.OpTrunc16to8
1411                                 case 41:
1412                                         op = ssa.OpTrunc32to8
1413                                 case 42:
1414                                         op = ssa.OpTrunc32to16
1415                                 case 81:
1416                                         op = ssa.OpTrunc64to8
1417                                 case 82:
1418                                         op = ssa.OpTrunc64to16
1419                                 case 84:
1420                                         op = ssa.OpTrunc64to32
1421                                 default:
1422                                         s.Fatalf("weird integer truncation %s -> %s", ft, tt)
1423                                 }
1424                         } else if ft.IsSigned() {
1425                                 // sign extension
1426                                 switch 10*ft.Size() + tt.Size() {
1427                                 case 12:
1428                                         op = ssa.OpSignExt8to16
1429                                 case 14:
1430                                         op = ssa.OpSignExt8to32
1431                                 case 18:
1432                                         op = ssa.OpSignExt8to64
1433                                 case 24:
1434                                         op = ssa.OpSignExt16to32
1435                                 case 28:
1436                                         op = ssa.OpSignExt16to64
1437                                 case 48:
1438                                         op = ssa.OpSignExt32to64
1439                                 default:
1440                                         s.Fatalf("bad integer sign extension %s -> %s", ft, tt)
1441                                 }
1442                         } else {
1443                                 // zero extension
1444                                 switch 10*ft.Size() + tt.Size() {
1445                                 case 12:
1446                                         op = ssa.OpZeroExt8to16
1447                                 case 14:
1448                                         op = ssa.OpZeroExt8to32
1449                                 case 18:
1450                                         op = ssa.OpZeroExt8to64
1451                                 case 24:
1452                                         op = ssa.OpZeroExt16to32
1453                                 case 28:
1454                                         op = ssa.OpZeroExt16to64
1455                                 case 48:
1456                                         op = ssa.OpZeroExt32to64
1457                                 default:
1458                                         s.Fatalf("weird integer sign extension %s -> %s", ft, tt)
1459                                 }
1460                         }
1461                         return s.newValue1(op, n.Type, x)
1462                 }
1463
1464                 if ft.IsFloat() || tt.IsFloat() {
1465                         conv, ok := fpConvOpToSSA[twoTypes{s.concreteEtype(ft), s.concreteEtype(tt)}]
1466                         if !ok {
1467                                 s.Fatalf("weird float conversion %s -> %s", ft, tt)
1468                         }
1469                         op1, op2, it := conv.op1, conv.op2, conv.intermediateType
1470
1471                         if op1 != ssa.OpInvalid && op2 != ssa.OpInvalid {
1472                                 // normal case, not tripping over unsigned 64
1473                                 if op1 == ssa.OpCopy {
1474                                         if op2 == ssa.OpCopy {
1475                                                 return x
1476                                         }
1477                                         return s.newValue1(op2, n.Type, x)
1478                                 }
1479                                 if op2 == ssa.OpCopy {
1480                                         return s.newValue1(op1, n.Type, x)
1481                                 }
1482                                 return s.newValue1(op2, n.Type, s.newValue1(op1, Types[it], x))
1483                         }
1484                         // Tricky 64-bit unsigned cases.
1485                         if ft.IsInteger() {
1486                                 // therefore tt is float32 or float64, and ft is also unsigned
1487                                 if tt.Size() == 4 {
1488                                         return s.uint64Tofloat32(n, x, ft, tt)
1489                                 }
1490                                 if tt.Size() == 8 {
1491                                         return s.uint64Tofloat64(n, x, ft, tt)
1492                                 }
1493                                 s.Fatalf("weird unsigned integer to float conversion %s -> %s", ft, tt)
1494                         }
1495                         // therefore ft is float32 or float64, and tt is unsigned integer
1496                         if ft.Size() == 4 {
1497                                 return s.float32ToUint64(n, x, ft, tt)
1498                         }
1499                         if ft.Size() == 8 {
1500                                 return s.float64ToUint64(n, x, ft, tt)
1501                         }
1502                         s.Fatalf("weird float to unsigned integer conversion %s -> %s", ft, tt)
1503                         return nil
1504                 }
1505
1506                 if ft.IsComplex() && tt.IsComplex() {
1507                         var op ssa.Op
1508                         if ft.Size() == tt.Size() {
1509                                 op = ssa.OpCopy
1510                         } else if ft.Size() == 8 && tt.Size() == 16 {
1511                                 op = ssa.OpCvt32Fto64F
1512                         } else if ft.Size() == 16 && tt.Size() == 8 {
1513                                 op = ssa.OpCvt64Fto32F
1514                         } else {
1515                                 s.Fatalf("weird complex conversion %s -> %s", ft, tt)
1516                         }
1517                         ftp := floatForComplex(ft)
1518                         ttp := floatForComplex(tt)
1519                         return s.newValue2(ssa.OpComplexMake, tt,
1520                                 s.newValue1(op, ttp, s.newValue1(ssa.OpComplexReal, ftp, x)),
1521                                 s.newValue1(op, ttp, s.newValue1(ssa.OpComplexImag, ftp, x)))
1522                 }
1523
1524                 s.Unimplementedf("unhandled OCONV %s -> %s", Econv(int(n.Left.Type.Etype), 0), Econv(int(n.Type.Etype), 0))
1525                 return nil
1526
1527         case ODOTTYPE:
1528                 res, _ := s.dottype(n, false)
1529                 return res
1530
1531         // binary ops
1532         case OLT, OEQ, ONE, OLE, OGE, OGT:
1533                 a := s.expr(n.Left)
1534                 b := s.expr(n.Right)
1535                 if n.Left.Type.IsComplex() {
1536                         pt := floatForComplex(n.Left.Type)
1537                         op := s.ssaOp(OEQ, pt)
1538                         r := s.newValue2(op, Types[TBOOL], s.newValue1(ssa.OpComplexReal, pt, a), s.newValue1(ssa.OpComplexReal, pt, b))
1539                         i := s.newValue2(op, Types[TBOOL], s.newValue1(ssa.OpComplexImag, pt, a), s.newValue1(ssa.OpComplexImag, pt, b))
1540                         c := s.newValue2(ssa.OpAnd8, Types[TBOOL], r, i)
1541                         switch n.Op {
1542                         case OEQ:
1543                                 return c
1544                         case ONE:
1545                                 return s.newValue1(ssa.OpNot, Types[TBOOL], c)
1546                         default:
1547                                 s.Fatalf("ordered complex compare %s", opnames[n.Op])
1548                         }
1549                 }
1550                 return s.newValue2(s.ssaOp(n.Op, n.Left.Type), Types[TBOOL], a, b)
1551         case OMUL:
1552                 a := s.expr(n.Left)
1553                 b := s.expr(n.Right)
1554                 if n.Type.IsComplex() {
1555                         mulop := ssa.OpMul64F
1556                         addop := ssa.OpAdd64F
1557                         subop := ssa.OpSub64F
1558                         pt := floatForComplex(n.Type) // Could be Float32 or Float64
1559                         wt := Types[TFLOAT64]         // Compute in Float64 to minimize cancellation error
1560
1561                         areal := s.newValue1(ssa.OpComplexReal, pt, a)
1562                         breal := s.newValue1(ssa.OpComplexReal, pt, b)
1563                         aimag := s.newValue1(ssa.OpComplexImag, pt, a)
1564                         bimag := s.newValue1(ssa.OpComplexImag, pt, b)
1565
1566                         if pt != wt { // Widen for calculation
1567                                 areal = s.newValue1(ssa.OpCvt32Fto64F, wt, areal)
1568                                 breal = s.newValue1(ssa.OpCvt32Fto64F, wt, breal)
1569                                 aimag = s.newValue1(ssa.OpCvt32Fto64F, wt, aimag)
1570                                 bimag = s.newValue1(ssa.OpCvt32Fto64F, wt, bimag)
1571                         }
1572
1573                         xreal := s.newValue2(subop, wt, s.newValue2(mulop, wt, areal, breal), s.newValue2(mulop, wt, aimag, bimag))
1574                         ximag := s.newValue2(addop, wt, s.newValue2(mulop, wt, areal, bimag), s.newValue2(mulop, wt, aimag, breal))
1575
1576                         if pt != wt { // Narrow to store back
1577                                 xreal = s.newValue1(ssa.OpCvt64Fto32F, pt, xreal)
1578                                 ximag = s.newValue1(ssa.OpCvt64Fto32F, pt, ximag)
1579                         }
1580
1581                         return s.newValue2(ssa.OpComplexMake, n.Type, xreal, ximag)
1582                 }
1583                 return s.newValue2(s.ssaOp(n.Op, n.Type), a.Type, a, b)
1584
1585         case ODIV:
1586                 a := s.expr(n.Left)
1587                 b := s.expr(n.Right)
1588                 if n.Type.IsComplex() {
1589                         // TODO this is not executed because the front-end substitutes a runtime call.
1590                         // That probably ought to change; with modest optimization the widen/narrow
1591                         // conversions could all be elided in larger expression trees.
1592                         mulop := ssa.OpMul64F
1593                         addop := ssa.OpAdd64F
1594                         subop := ssa.OpSub64F
1595                         divop := ssa.OpDiv64F
1596                         pt := floatForComplex(n.Type) // Could be Float32 or Float64
1597                         wt := Types[TFLOAT64]         // Compute in Float64 to minimize cancellation error
1598
1599                         areal := s.newValue1(ssa.OpComplexReal, pt, a)
1600                         breal := s.newValue1(ssa.OpComplexReal, pt, b)
1601                         aimag := s.newValue1(ssa.OpComplexImag, pt, a)
1602                         bimag := s.newValue1(ssa.OpComplexImag, pt, b)
1603
1604                         if pt != wt { // Widen for calculation
1605                                 areal = s.newValue1(ssa.OpCvt32Fto64F, wt, areal)
1606                                 breal = s.newValue1(ssa.OpCvt32Fto64F, wt, breal)
1607                                 aimag = s.newValue1(ssa.OpCvt32Fto64F, wt, aimag)
1608                                 bimag = s.newValue1(ssa.OpCvt32Fto64F, wt, bimag)
1609                         }
1610
1611                         denom := s.newValue2(addop, wt, s.newValue2(mulop, wt, breal, breal), s.newValue2(mulop, wt, bimag, bimag))
1612                         xreal := s.newValue2(addop, wt, s.newValue2(mulop, wt, areal, breal), s.newValue2(mulop, wt, aimag, bimag))
1613                         ximag := s.newValue2(subop, wt, s.newValue2(mulop, wt, aimag, breal), s.newValue2(mulop, wt, areal, bimag))
1614
1615                         // TODO not sure if this is best done in wide precision or narrow
1616                         // Double-rounding might be an issue.
1617                         // Note that the pre-SSA implementation does the entire calculation
1618                         // in wide format, so wide is compatible.
1619                         xreal = s.newValue2(divop, wt, xreal, denom)
1620                         ximag = s.newValue2(divop, wt, ximag, denom)
1621
1622                         if pt != wt { // Narrow to store back
1623                                 xreal = s.newValue1(ssa.OpCvt64Fto32F, pt, xreal)
1624                                 ximag = s.newValue1(ssa.OpCvt64Fto32F, pt, ximag)
1625                         }
1626
1627                         return s.newValue2(ssa.OpComplexMake, n.Type, xreal, ximag)
1628                 }
1629                 return s.newValue2(s.ssaOp(n.Op, n.Type), a.Type, a, b)
1630         case OADD, OSUB:
1631                 a := s.expr(n.Left)
1632                 b := s.expr(n.Right)
1633                 if n.Type.IsComplex() {
1634                         pt := floatForComplex(n.Type)
1635                         op := s.ssaOp(n.Op, pt)
1636                         return s.newValue2(ssa.OpComplexMake, n.Type,
1637                                 s.newValue2(op, pt, s.newValue1(ssa.OpComplexReal, pt, a), s.newValue1(ssa.OpComplexReal, pt, b)),
1638                                 s.newValue2(op, pt, s.newValue1(ssa.OpComplexImag, pt, a), s.newValue1(ssa.OpComplexImag, pt, b)))
1639                 }
1640                 return s.newValue2(s.ssaOp(n.Op, n.Type), a.Type, a, b)
1641         case OAND, OOR, OMOD, OHMUL, OXOR:
1642                 a := s.expr(n.Left)
1643                 b := s.expr(n.Right)
1644                 return s.newValue2(s.ssaOp(n.Op, n.Type), a.Type, a, b)
1645         case OLSH, ORSH:
1646                 a := s.expr(n.Left)
1647                 b := s.expr(n.Right)
1648                 return s.newValue2(s.ssaShiftOp(n.Op, n.Type, n.Right.Type), a.Type, a, b)
1649         case OLROT:
1650                 a := s.expr(n.Left)
1651                 i := n.Right.Int()
1652                 if i <= 0 || i >= n.Type.Size()*8 {
1653                         s.Fatalf("Wrong rotate distance for LROT, expected 1 through %d, saw %d", n.Type.Size()*8-1, i)
1654                 }
1655                 return s.newValue1I(s.ssaRotateOp(n.Op, n.Type), a.Type, i, a)
1656         case OANDAND, OOROR:
1657                 // To implement OANDAND (and OOROR), we introduce a
1658                 // new temporary variable to hold the result. The
1659                 // variable is associated with the OANDAND node in the
1660                 // s.vars table (normally variables are only
1661                 // associated with ONAME nodes). We convert
1662                 //     A && B
1663                 // to
1664                 //     var = A
1665                 //     if var {
1666                 //         var = B
1667                 //     }
1668                 // Using var in the subsequent block introduces the
1669                 // necessary phi variable.
1670                 el := s.expr(n.Left)
1671                 s.vars[n] = el
1672
1673                 b := s.endBlock()
1674                 b.Kind = ssa.BlockIf
1675                 b.Control = el
1676                 // In theory, we should set b.Likely here based on context.
1677                 // However, gc only gives us likeliness hints
1678                 // in a single place, for plain OIF statements,
1679                 // and passing around context is finnicky, so don't bother for now.
1680
1681                 bRight := s.f.NewBlock(ssa.BlockPlain)
1682                 bResult := s.f.NewBlock(ssa.BlockPlain)
1683                 if n.Op == OANDAND {
1684                         b.AddEdgeTo(bRight)
1685                         b.AddEdgeTo(bResult)
1686                 } else if n.Op == OOROR {
1687                         b.AddEdgeTo(bResult)
1688                         b.AddEdgeTo(bRight)
1689                 }
1690
1691                 s.startBlock(bRight)
1692                 er := s.expr(n.Right)
1693                 s.vars[n] = er
1694
1695                 b = s.endBlock()
1696                 b.AddEdgeTo(bResult)
1697
1698                 s.startBlock(bResult)
1699                 return s.variable(n, Types[TBOOL])
1700         case OCOMPLEX:
1701                 r := s.expr(n.Left)
1702                 i := s.expr(n.Right)
1703                 return s.newValue2(ssa.OpComplexMake, n.Type, r, i)
1704
1705         // unary ops
1706         case OMINUS:
1707                 a := s.expr(n.Left)
1708                 if n.Type.IsComplex() {
1709                         tp := floatForComplex(n.Type)
1710                         negop := s.ssaOp(n.Op, tp)
1711                         return s.newValue2(ssa.OpComplexMake, n.Type,
1712                                 s.newValue1(negop, tp, s.newValue1(ssa.OpComplexReal, tp, a)),
1713                                 s.newValue1(negop, tp, s.newValue1(ssa.OpComplexImag, tp, a)))
1714                 }
1715                 return s.newValue1(s.ssaOp(n.Op, n.Type), a.Type, a)
1716         case ONOT, OCOM, OSQRT:
1717                 a := s.expr(n.Left)
1718                 return s.newValue1(s.ssaOp(n.Op, n.Type), a.Type, a)
1719         case OIMAG, OREAL:
1720                 a := s.expr(n.Left)
1721                 return s.newValue1(s.ssaOp(n.Op, n.Left.Type), n.Type, a)
1722         case OPLUS:
1723                 return s.expr(n.Left)
1724
1725         case OADDR:
1726                 return s.addr(n.Left, n.Bounded)
1727
1728         case OINDREG:
1729                 if int(n.Reg) != Thearch.REGSP {
1730                         s.Unimplementedf("OINDREG of non-SP register %s in expr: %v", obj.Rconv(int(n.Reg)), n)
1731                         return nil
1732                 }
1733                 addr := s.entryNewValue1I(ssa.OpOffPtr, Ptrto(n.Type), n.Xoffset, s.sp)
1734                 return s.newValue2(ssa.OpLoad, n.Type, addr, s.mem())
1735
1736         case OIND:
1737                 p := s.expr(n.Left)
1738                 s.nilCheck(p)
1739                 return s.newValue2(ssa.OpLoad, n.Type, p, s.mem())
1740
1741         case ODOT:
1742                 // TODO: fix when we can SSA struct types.
1743                 p := s.addr(n, false)
1744                 return s.newValue2(ssa.OpLoad, n.Type, p, s.mem())
1745
1746         case ODOTPTR:
1747                 p := s.expr(n.Left)
1748                 s.nilCheck(p)
1749                 p = s.newValue2(ssa.OpAddPtr, p.Type, p, s.constIntPtr(Types[TUINTPTR], n.Xoffset))
1750                 return s.newValue2(ssa.OpLoad, n.Type, p, s.mem())
1751
1752         case OINDEX:
1753                 switch {
1754                 case n.Left.Type.IsString():
1755                         a := s.expr(n.Left)
1756                         i := s.expr(n.Right)
1757                         i = s.extendIndex(i)
1758                         if !n.Bounded {
1759                                 len := s.newValue1(ssa.OpStringLen, Types[TINT], a)
1760                                 s.boundsCheck(i, len)
1761                         }
1762                         ptrtyp := Ptrto(Types[TUINT8])
1763                         ptr := s.newValue1(ssa.OpStringPtr, ptrtyp, a)
1764                         ptr = s.newValue2(ssa.OpAddPtr, ptrtyp, ptr, i)
1765                         return s.newValue2(ssa.OpLoad, Types[TUINT8], ptr, s.mem())
1766                 case n.Left.Type.IsSlice():
1767                         p := s.addr(n, false)
1768                         return s.newValue2(ssa.OpLoad, n.Left.Type.Type, p, s.mem())
1769                 case n.Left.Type.IsArray():
1770                         // TODO: fix when we can SSA arrays of length 1.
1771                         p := s.addr(n, false)
1772                         return s.newValue2(ssa.OpLoad, n.Left.Type.Type, p, s.mem())
1773                 default:
1774                         s.Fatalf("bad type for index %v", n.Left.Type)
1775                         return nil
1776                 }
1777
1778         case OLEN, OCAP:
1779                 switch {
1780                 case n.Left.Type.IsSlice():
1781                         op := ssa.OpSliceLen
1782                         if n.Op == OCAP {
1783                                 op = ssa.OpSliceCap
1784                         }
1785                         return s.newValue1(op, Types[TINT], s.expr(n.Left))
1786                 case n.Left.Type.IsString(): // string; not reachable for OCAP
1787                         return s.newValue1(ssa.OpStringLen, Types[TINT], s.expr(n.Left))
1788                 case n.Left.Type.IsMap(), n.Left.Type.IsChan():
1789                         return s.referenceTypeBuiltin(n, s.expr(n.Left))
1790                 default: // array
1791                         return s.constInt(Types[TINT], n.Left.Type.Bound)
1792                 }
1793
1794         case OSPTR:
1795                 a := s.expr(n.Left)
1796                 if n.Left.Type.IsSlice() {
1797                         return s.newValue1(ssa.OpSlicePtr, n.Type, a)
1798                 } else {
1799                         return s.newValue1(ssa.OpStringPtr, n.Type, a)
1800                 }
1801
1802         case OITAB:
1803                 a := s.expr(n.Left)
1804                 return s.newValue1(ssa.OpITab, n.Type, a)
1805
1806         case OEFACE:
1807                 tab := s.expr(n.Left)
1808                 data := s.expr(n.Right)
1809                 // The frontend allows putting things like struct{*byte} in
1810                 // the data portion of an eface.  But we don't want struct{*byte}
1811                 // as a register type because (among other reasons) the liveness
1812                 // analysis is confused by the "fat" variables that result from
1813                 // such types being spilled.
1814                 // So here we ensure that we are selecting the underlying pointer
1815                 // when we build an eface.
1816                 for !data.Type.IsPtr() {
1817                         switch {
1818                         case data.Type.IsArray():
1819                                 data = s.newValue2(ssa.OpArrayIndex, data.Type.Elem(), data, s.constInt(Types[TINT], 0))
1820                         case data.Type.IsStruct():
1821                                 for i := data.Type.NumFields() - 1; i >= 0; i-- {
1822                                         f := data.Type.FieldType(i)
1823                                         if f.Size() == 0 {
1824                                                 // eface type could also be struct{p *byte; q [0]int}
1825                                                 continue
1826                                         }
1827                                         data = s.newValue1I(ssa.OpStructSelect, f, data.Type.FieldOff(i), data)
1828                                         break
1829                                 }
1830                         default:
1831                                 s.Fatalf("type being put into an eface isn't a pointer")
1832                         }
1833                 }
1834                 return s.newValue2(ssa.OpIMake, n.Type, tab, data)
1835
1836         case OSLICE, OSLICEARR:
1837                 v := s.expr(n.Left)
1838                 var i, j *ssa.Value
1839                 if n.Right.Left != nil {
1840                         i = s.extendIndex(s.expr(n.Right.Left))
1841                 }
1842                 if n.Right.Right != nil {
1843                         j = s.extendIndex(s.expr(n.Right.Right))
1844                 }
1845                 p, l, c := s.slice(n.Left.Type, v, i, j, nil)
1846                 return s.newValue3(ssa.OpSliceMake, n.Type, p, l, c)
1847         case OSLICESTR:
1848                 v := s.expr(n.Left)
1849                 var i, j *ssa.Value
1850                 if n.Right.Left != nil {
1851                         i = s.extendIndex(s.expr(n.Right.Left))
1852                 }
1853                 if n.Right.Right != nil {
1854                         j = s.extendIndex(s.expr(n.Right.Right))
1855                 }
1856                 p, l, _ := s.slice(n.Left.Type, v, i, j, nil)
1857                 return s.newValue2(ssa.OpStringMake, n.Type, p, l)
1858         case OSLICE3, OSLICE3ARR:
1859                 v := s.expr(n.Left)
1860                 var i *ssa.Value
1861                 if n.Right.Left != nil {
1862                         i = s.extendIndex(s.expr(n.Right.Left))
1863                 }
1864                 j := s.extendIndex(s.expr(n.Right.Right.Left))
1865                 k := s.extendIndex(s.expr(n.Right.Right.Right))
1866                 p, l, c := s.slice(n.Left.Type, v, i, j, k)
1867                 return s.newValue3(ssa.OpSliceMake, n.Type, p, l, c)
1868
1869         case OCALLFUNC, OCALLINTER, OCALLMETH:
1870                 return s.call(n, callNormal)
1871
1872         case OGETG:
1873                 return s.newValue0(ssa.OpGetG, n.Type)
1874
1875         case OAPPEND:
1876                 // append(s, e1, e2, e3).  Compile like:
1877                 // ptr,len,cap := s
1878                 // newlen := len + 3
1879                 // if newlen > s.cap {
1880                 //     ptr,_,cap = growslice(s, newlen)
1881                 // }
1882                 // *(ptr+len) = e1
1883                 // *(ptr+len+1) = e2
1884                 // *(ptr+len+2) = e3
1885                 // makeslice(ptr,newlen,cap)
1886
1887                 et := n.Type.Type
1888                 pt := Ptrto(et)
1889
1890                 // Evaluate slice
1891                 slice := s.expr(n.List.N)
1892
1893                 // Allocate new blocks
1894                 grow := s.f.NewBlock(ssa.BlockPlain)
1895                 assign := s.f.NewBlock(ssa.BlockPlain)
1896
1897                 // Decide if we need to grow
1898                 nargs := int64(count(n.List) - 1)
1899                 p := s.newValue1(ssa.OpSlicePtr, pt, slice)
1900                 l := s.newValue1(ssa.OpSliceLen, Types[TINT], slice)
1901                 c := s.newValue1(ssa.OpSliceCap, Types[TINT], slice)
1902                 nl := s.newValue2(s.ssaOp(OADD, Types[TINT]), Types[TINT], l, s.constInt(Types[TINT], nargs))
1903                 cmp := s.newValue2(s.ssaOp(OGT, Types[TINT]), Types[TBOOL], nl, c)
1904                 s.vars[&ptrVar] = p
1905                 s.vars[&capVar] = c
1906                 b := s.endBlock()
1907                 b.Kind = ssa.BlockIf
1908                 b.Likely = ssa.BranchUnlikely
1909                 b.Control = cmp
1910                 b.AddEdgeTo(grow)
1911                 b.AddEdgeTo(assign)
1912
1913                 // Call growslice
1914                 s.startBlock(grow)
1915                 taddr := s.newValue1A(ssa.OpAddr, Types[TUINTPTR], &ssa.ExternSymbol{Types[TUINTPTR], typenamesym(n.Type)}, s.sb)
1916
1917                 r := s.rtcall(growslice, true, []*Type{pt, Types[TINT], Types[TINT]}, taddr, p, l, c, nl)
1918
1919                 s.vars[&ptrVar] = r[0]
1920                 // Note: we don't need to read r[1], the result's length.  It will be nl.
1921                 // (or maybe we should, we just have to spill/restore nl otherwise?)
1922                 s.vars[&capVar] = r[2]
1923                 b = s.endBlock()
1924                 b.AddEdgeTo(assign)
1925
1926                 // assign new elements to slots
1927                 s.startBlock(assign)
1928
1929                 // Evaluate args
1930                 args := make([]*ssa.Value, 0, nargs)
1931                 store := make([]bool, 0, nargs)
1932                 for l := n.List.Next; l != nil; l = l.Next {
1933                         if canSSAType(l.N.Type) {
1934                                 args = append(args, s.expr(l.N))
1935                                 store = append(store, true)
1936                         } else {
1937                                 args = append(args, s.addr(l.N, false))
1938                                 store = append(store, false)
1939                         }
1940                 }
1941
1942                 p = s.variable(&ptrVar, pt)          // generates phi for ptr
1943                 c = s.variable(&capVar, Types[TINT]) // generates phi for cap
1944                 p2 := s.newValue2(ssa.OpPtrIndex, pt, p, l)
1945                 for i, arg := range args {
1946                         addr := s.newValue2(ssa.OpPtrIndex, pt, p2, s.constInt(Types[TUINTPTR], int64(i)))
1947                         if store[i] {
1948                                 s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, et.Size(), addr, arg, s.mem())
1949                         } else {
1950                                 s.vars[&memVar] = s.newValue3I(ssa.OpMove, ssa.TypeMem, et.Size(), addr, arg, s.mem())
1951                         }
1952                         if haspointers(et) {
1953                                 // TODO: just one write barrier call for all of these writes?
1954                                 // TODO: maybe just one writeBarrierEnabled check?
1955                                 s.insertWB(et, addr)
1956                         }
1957                 }
1958
1959                 // make result
1960                 delete(s.vars, &ptrVar)
1961                 delete(s.vars, &capVar)
1962                 return s.newValue3(ssa.OpSliceMake, n.Type, p, nl, c)
1963
1964         default:
1965                 s.Unimplementedf("unhandled expr %s", opnames[n.Op])
1966                 return nil
1967         }
1968 }
1969
1970 func (s *state) assign(left *Node, right *ssa.Value, wb bool) {
1971         if left.Op == ONAME && isblank(left) {
1972                 return
1973         }
1974         t := left.Type
1975         dowidth(t)
1976         if right == nil {
1977                 // right == nil means use the zero value of the assigned type.
1978                 if !canSSA(left) {
1979                         // if we can't ssa this memory, treat it as just zeroing out the backing memory
1980                         addr := s.addr(left, false)
1981                         if left.Op == ONAME {
1982                                 s.vars[&memVar] = s.newValue1A(ssa.OpVarDef, ssa.TypeMem, left, s.mem())
1983                         }
1984                         s.vars[&memVar] = s.newValue2I(ssa.OpZero, ssa.TypeMem, t.Size(), addr, s.mem())
1985                         return
1986                 }
1987                 right = s.zeroVal(t)
1988         }
1989         if left.Op == ONAME && canSSA(left) {
1990                 // Update variable assignment.
1991                 s.vars[left] = right
1992                 return
1993         }
1994         // not ssa-able.  Treat as a store.
1995         addr := s.addr(left, false)
1996         if left.Op == ONAME {
1997                 s.vars[&memVar] = s.newValue1A(ssa.OpVarDef, ssa.TypeMem, left, s.mem())
1998         }
1999         s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, t.Size(), addr, right, s.mem())
2000         if wb {
2001                 s.insertWB(left.Type, addr)
2002         }
2003 }
2004
2005 // zeroVal returns the zero value for type t.
2006 func (s *state) zeroVal(t *Type) *ssa.Value {
2007         switch {
2008         case t.IsInteger():
2009                 switch t.Size() {
2010                 case 1:
2011                         return s.constInt8(t, 0)
2012                 case 2:
2013                         return s.constInt16(t, 0)
2014                 case 4:
2015                         return s.constInt32(t, 0)
2016                 case 8:
2017                         return s.constInt64(t, 0)
2018                 default:
2019                         s.Fatalf("bad sized integer type %s", t)
2020                 }
2021         case t.IsFloat():
2022                 switch t.Size() {
2023                 case 4:
2024                         return s.constFloat32(t, 0)
2025                 case 8:
2026                         return s.constFloat64(t, 0)
2027                 default:
2028                         s.Fatalf("bad sized float type %s", t)
2029                 }
2030         case t.IsComplex():
2031                 switch t.Size() {
2032                 case 8:
2033                         z := s.constFloat32(Types[TFLOAT32], 0)
2034                         return s.entryNewValue2(ssa.OpComplexMake, t, z, z)
2035                 case 16:
2036                         z := s.constFloat64(Types[TFLOAT64], 0)
2037                         return s.entryNewValue2(ssa.OpComplexMake, t, z, z)
2038                 default:
2039                         s.Fatalf("bad sized complex type %s", t)
2040                 }
2041
2042         case t.IsString():
2043                 return s.entryNewValue0A(ssa.OpConstString, t, "")
2044         case t.IsPtr():
2045                 return s.entryNewValue0(ssa.OpConstNil, t)
2046         case t.IsBoolean():
2047                 return s.constBool(false)
2048         case t.IsInterface():
2049                 return s.entryNewValue0(ssa.OpConstInterface, t)
2050         case t.IsSlice():
2051                 return s.entryNewValue0(ssa.OpConstSlice, t)
2052         }
2053         s.Unimplementedf("zero for type %v not implemented", t)
2054         return nil
2055 }
2056
2057 type callKind int8
2058
2059 const (
2060         callNormal callKind = iota
2061         callDefer
2062         callGo
2063 )
2064
2065 func (s *state) call(n *Node, k callKind) *ssa.Value {
2066         var sym *Sym           // target symbol (if static)
2067         var closure *ssa.Value // ptr to closure to run (if dynamic)
2068         var codeptr *ssa.Value // ptr to target code (if dynamic)
2069         var rcvr *ssa.Value    // receiver to set
2070         fn := n.Left
2071         switch n.Op {
2072         case OCALLFUNC:
2073                 if k == callNormal && fn.Op == ONAME && fn.Class == PFUNC {
2074                         sym = fn.Sym
2075                         break
2076                 }
2077                 closure = s.expr(fn)
2078                 if closure == nil {
2079                         return nil // TODO: remove when expr always returns non-nil
2080                 }
2081         case OCALLMETH:
2082                 if fn.Op != ODOTMETH {
2083                         Fatalf("OCALLMETH: n.Left not an ODOTMETH: %v", fn)
2084                 }
2085                 if fn.Right.Op != ONAME {
2086                         Fatalf("OCALLMETH: n.Left.Right not a ONAME: %v", fn.Right)
2087                 }
2088                 if k == callNormal {
2089                         sym = fn.Right.Sym
2090                         break
2091                 }
2092                 n2 := *fn.Right
2093                 n2.Class = PFUNC
2094                 closure = s.expr(&n2)
2095                 // Note: receiver is already assigned in n.List, so we don't
2096                 // want to set it here.
2097         case OCALLINTER:
2098                 if fn.Op != ODOTINTER {
2099                         Fatalf("OCALLINTER: n.Left not an ODOTINTER: %v", Oconv(int(fn.Op), 0))
2100                 }
2101                 i := s.expr(fn.Left)
2102                 itab := s.newValue1(ssa.OpITab, Types[TUINTPTR], i)
2103                 itabidx := fn.Xoffset + 3*int64(Widthptr) + 8 // offset of fun field in runtime.itab
2104                 itab = s.newValue1I(ssa.OpOffPtr, Types[TUINTPTR], itabidx, itab)
2105                 if k == callNormal {
2106                         codeptr = s.newValue2(ssa.OpLoad, Types[TUINTPTR], itab, s.mem())
2107                 } else {
2108                         closure = itab
2109                 }
2110                 rcvr = s.newValue1(ssa.OpIData, Types[TUINTPTR], i)
2111         }
2112         dowidth(fn.Type)
2113         stksize := fn.Type.Argwid // includes receiver
2114
2115         // Run all argument assignments.  The arg slots have already
2116         // been offset by the appropriate amount (+2*widthptr for go/defer,
2117         // +widthptr for interface calls).
2118         // For OCALLMETH, the receiver is set in these statements.
2119         s.stmtList(n.List)
2120
2121         // Set receiver (for interface calls)
2122         if rcvr != nil {
2123                 argStart := Ctxt.FixedFrameSize()
2124                 if k != callNormal {
2125                         argStart += int64(2 * Widthptr)
2126                 }
2127                 addr := s.entryNewValue1I(ssa.OpOffPtr, Types[TUINTPTR], argStart, s.sp)
2128                 s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, int64(Widthptr), addr, rcvr, s.mem())
2129         }
2130
2131         // Defer/go args
2132         if k != callNormal {
2133                 // Write argsize and closure (args to Newproc/Deferproc).
2134                 argsize := s.constInt32(Types[TUINT32], int32(stksize))
2135                 s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, 4, s.sp, argsize, s.mem())
2136                 addr := s.entryNewValue1I(ssa.OpOffPtr, Ptrto(Types[TUINTPTR]), int64(Widthptr), s.sp)
2137                 s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, int64(Widthptr), addr, closure, s.mem())
2138                 stksize += 2 * int64(Widthptr)
2139         }
2140
2141         // call target
2142         bNext := s.f.NewBlock(ssa.BlockPlain)
2143         var call *ssa.Value
2144         switch {
2145         case k == callDefer:
2146                 call = s.newValue1(ssa.OpDeferCall, ssa.TypeMem, s.mem())
2147         case k == callGo:
2148                 call = s.newValue1(ssa.OpGoCall, ssa.TypeMem, s.mem())
2149         case closure != nil:
2150                 codeptr = s.newValue2(ssa.OpLoad, Types[TUINTPTR], closure, s.mem())
2151                 call = s.newValue3(ssa.OpClosureCall, ssa.TypeMem, codeptr, closure, s.mem())
2152         case codeptr != nil:
2153                 call = s.newValue2(ssa.OpInterCall, ssa.TypeMem, codeptr, s.mem())
2154         case sym != nil:
2155                 call = s.newValue1A(ssa.OpStaticCall, ssa.TypeMem, sym, s.mem())
2156         default:
2157                 Fatalf("bad call type %s %v", opnames[n.Op], n)
2158         }
2159         call.AuxInt = stksize // Call operations carry the argsize of the callee along with them
2160
2161         // Finish call block
2162         s.vars[&memVar] = call
2163         b := s.endBlock()
2164         b.Kind = ssa.BlockCall
2165         b.Control = call
2166         b.AddEdgeTo(bNext)
2167
2168         // Read result from stack at the start of the fallthrough block
2169         s.startBlock(bNext)
2170         var titer Iter
2171         fp := Structfirst(&titer, Getoutarg(n.Left.Type))
2172         if fp == nil || k != callNormal {
2173                 // call has no return value. Continue with the next statement.
2174                 return nil
2175         }
2176         a := s.entryNewValue1I(ssa.OpOffPtr, Ptrto(fp.Type), fp.Width, s.sp)
2177         return s.newValue2(ssa.OpLoad, fp.Type, a, call)
2178 }
2179
2180 // etypesign returns the signed-ness of e, for integer/pointer etypes.
2181 // -1 means signed, +1 means unsigned, 0 means non-integer/non-pointer.
2182 func etypesign(e uint8) int8 {
2183         switch e {
2184         case TINT8, TINT16, TINT32, TINT64, TINT:
2185                 return -1
2186         case TUINT8, TUINT16, TUINT32, TUINT64, TUINT, TUINTPTR, TUNSAFEPTR:
2187                 return +1
2188         }
2189         return 0
2190 }
2191
2192 // lookupSymbol is used to retrieve the symbol (Extern, Arg or Auto) used for a particular node.
2193 // This improves the effectiveness of cse by using the same Aux values for the
2194 // same symbols.
2195 func (s *state) lookupSymbol(n *Node, sym interface{}) interface{} {
2196         switch sym.(type) {
2197         default:
2198                 s.Fatalf("sym %v is of uknown type %T", sym, sym)
2199         case *ssa.ExternSymbol, *ssa.ArgSymbol, *ssa.AutoSymbol:
2200                 // these are the only valid types
2201         }
2202
2203         if lsym, ok := s.varsyms[n]; ok {
2204                 return lsym
2205         } else {
2206                 s.varsyms[n] = sym
2207                 return sym
2208         }
2209 }
2210
2211 // addr converts the address of the expression n to SSA, adds it to s and returns the SSA result.
2212 // The value that the returned Value represents is guaranteed to be non-nil.
2213 // If bounded is true then this address does not require a nil check for its operand
2214 // even if that would otherwise be implied.
2215 func (s *state) addr(n *Node, bounded bool) *ssa.Value {
2216         switch n.Op {
2217         case ONAME:
2218                 switch n.Class {
2219                 case PEXTERN:
2220                         // global variable
2221                         aux := &ssa.ExternSymbol{n.Type, n.Sym}
2222                         v := s.entryNewValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sb)
2223                         // TODO: Make OpAddr use AuxInt as well as Aux.
2224                         if n.Xoffset != 0 {
2225                                 v = s.entryNewValue1I(ssa.OpOffPtr, v.Type, n.Xoffset, v)
2226                         }
2227                         return v
2228                 case PPARAM:
2229                         // parameter slot
2230                         v := s.decladdrs[n]
2231                         if v == nil {
2232                                 if flag_race != 0 && n.String() == ".fp" {
2233                                         s.Unimplementedf("race detector mishandles nodfp")
2234                                 }
2235                                 s.Fatalf("addr of undeclared ONAME %v. declared: %v", n, s.decladdrs)
2236                         }
2237                         return v
2238                 case PAUTO:
2239                         // We need to regenerate the address of autos
2240                         // at every use.  This prevents LEA instructions
2241                         // from occurring before the corresponding VarDef
2242                         // op and confusing the liveness analysis into thinking
2243                         // the variable is live at function entry.
2244                         // TODO: I'm not sure if this really works or we're just
2245                         // getting lucky.  We might need a real dependency edge
2246                         // between vardef and addr ops.
2247                         aux := &ssa.AutoSymbol{Typ: n.Type, Node: n}
2248                         return s.newValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sp)
2249                 case PPARAMOUT: // Same as PAUTO -- cannot generate LEA early.
2250                         // ensure that we reuse symbols for out parameters so
2251                         // that cse works on their addresses
2252                         aux := s.lookupSymbol(n, &ssa.ArgSymbol{Typ: n.Type, Node: n})
2253                         return s.newValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sp)
2254                 case PAUTO | PHEAP, PPARAM | PHEAP, PPARAMOUT | PHEAP, PPARAMREF:
2255                         return s.expr(n.Name.Heapaddr)
2256                 default:
2257                         s.Unimplementedf("variable address class %v not implemented", n.Class)
2258                         return nil
2259                 }
2260         case OINDREG:
2261                 // indirect off a register
2262                 // used for storing/loading arguments/returns to/from callees
2263                 if int(n.Reg) != Thearch.REGSP {
2264                         s.Unimplementedf("OINDREG of non-SP register %s in addr: %v", obj.Rconv(int(n.Reg)), n)
2265                         return nil
2266                 }
2267                 return s.entryNewValue1I(ssa.OpOffPtr, Ptrto(n.Type), n.Xoffset, s.sp)
2268         case OINDEX:
2269                 if n.Left.Type.IsSlice() {
2270                         a := s.expr(n.Left)
2271                         i := s.expr(n.Right)
2272                         i = s.extendIndex(i)
2273                         len := s.newValue1(ssa.OpSliceLen, Types[TUINTPTR], a)
2274                         if !n.Bounded {
2275                                 s.boundsCheck(i, len)
2276                         }
2277                         p := s.newValue1(ssa.OpSlicePtr, Ptrto(n.Left.Type.Type), a)
2278                         return s.newValue2(ssa.OpPtrIndex, Ptrto(n.Left.Type.Type), p, i)
2279                 } else { // array
2280                         a := s.addr(n.Left, bounded)
2281                         i := s.expr(n.Right)
2282                         i = s.extendIndex(i)
2283                         len := s.constInt(Types[TINT], n.Left.Type.Bound)
2284                         if !n.Bounded {
2285                                 s.boundsCheck(i, len)
2286                         }
2287                         return s.newValue2(ssa.OpPtrIndex, Ptrto(n.Left.Type.Type), a, i)
2288                 }
2289         case OIND:
2290                 p := s.expr(n.Left)
2291                 if !bounded {
2292                         s.nilCheck(p)
2293                 }
2294                 return p
2295         case ODOT:
2296                 p := s.addr(n.Left, bounded)
2297                 return s.newValue2(ssa.OpAddPtr, p.Type, p, s.constIntPtr(Types[TUINTPTR], n.Xoffset))
2298         case ODOTPTR:
2299                 p := s.expr(n.Left)
2300                 if !bounded {
2301                         s.nilCheck(p)
2302                 }
2303                 return s.newValue2(ssa.OpAddPtr, p.Type, p, s.constIntPtr(Types[TUINTPTR], n.Xoffset))
2304         case OCLOSUREVAR:
2305                 return s.newValue2(ssa.OpAddPtr, Ptrto(n.Type),
2306                         s.entryNewValue0(ssa.OpGetClosurePtr, Types[TUINTPTR]),
2307                         s.constIntPtr(Types[TUINTPTR], n.Xoffset))
2308         case OPARAM:
2309                 p := n.Left
2310                 if p.Op != ONAME || !(p.Class == PPARAM|PHEAP || p.Class == PPARAMOUT|PHEAP) {
2311                         s.Fatalf("OPARAM not of ONAME,{PPARAM,PPARAMOUT}|PHEAP, instead %s", nodedump(p, 0))
2312                 }
2313
2314                 // Recover original offset to address passed-in param value.
2315                 original_p := *p
2316                 original_p.Xoffset = n.Xoffset
2317                 aux := &ssa.ArgSymbol{Typ: n.Type, Node: &original_p}
2318                 return s.entryNewValue1A(ssa.OpAddr, Ptrto(n.Type), aux, s.sp)
2319         case OCONVNOP:
2320                 addr := s.addr(n.Left, bounded)
2321                 to := Ptrto(n.Type)
2322                 return s.newValue1(ssa.OpCopy, to, addr) // ensure that addr has the right type
2323
2324         default:
2325                 s.Unimplementedf("unhandled addr %v", Oconv(int(n.Op), 0))
2326                 return nil
2327         }
2328 }
2329
2330 // canSSA reports whether n is SSA-able.
2331 // n must be an ONAME.
2332 func canSSA(n *Node) bool {
2333         if n.Op != ONAME {
2334                 return false
2335         }
2336         if n.Addrtaken {
2337                 return false
2338         }
2339         if n.Class&PHEAP != 0 {
2340                 return false
2341         }
2342         switch n.Class {
2343         case PEXTERN, PPARAMOUT, PPARAMREF:
2344                 return false
2345         }
2346         if n.Class == PPARAM && n.String() == ".this" {
2347                 // wrappers generated by genwrapper need to update
2348                 // the .this pointer in place.
2349                 return false
2350         }
2351         return canSSAType(n.Type)
2352         // TODO: try to make more variables SSAable?
2353 }
2354
2355 // canSSA reports whether variables of type t are SSA-able.
2356 func canSSAType(t *Type) bool {
2357         dowidth(t)
2358         if t.Width > int64(4*Widthptr) {
2359                 // 4*Widthptr is an arbitrary constant.  We want it
2360                 // to be at least 3*Widthptr so slices can be registerized.
2361                 // Too big and we'll introduce too much register pressure.
2362                 return false
2363         }
2364         switch t.Etype {
2365         case TARRAY:
2366                 if Isslice(t) {
2367                         return true
2368                 }
2369                 // We can't do arrays because dynamic indexing is
2370                 // not supported on SSA variables.
2371                 // TODO: maybe allow if length is <=1?  All indexes
2372                 // are constant?  Might be good for the arrays
2373                 // introduced by the compiler for variadic functions.
2374                 return false
2375         case TSTRUCT:
2376                 if countfield(t) > 4 {
2377                         // 4 is an arbitrary constant.  Same reasoning
2378                         // as above, lots of small fields would waste
2379                         // register space needed by other values.
2380                         return false
2381                 }
2382                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
2383                         if !canSSAType(t1.Type) {
2384                                 return false
2385                         }
2386                 }
2387                 return false // until it is implemented
2388                 //return true
2389         default:
2390                 return true
2391         }
2392 }
2393
2394 // nilCheck generates nil pointer checking code.
2395 // Starts a new block on return, unless nil checks are disabled.
2396 // Used only for automatically inserted nil checks,
2397 // not for user code like 'x != nil'.
2398 func (s *state) nilCheck(ptr *ssa.Value) {
2399         if Disable_checknil != 0 {
2400                 return
2401         }
2402         c := s.newValue1(ssa.OpIsNonNil, Types[TBOOL], ptr)
2403         b := s.endBlock()
2404         b.Kind = ssa.BlockIf
2405         b.Control = c
2406         b.Likely = ssa.BranchLikely
2407         bNext := s.f.NewBlock(ssa.BlockPlain)
2408         bPanic := s.f.NewBlock(ssa.BlockPlain)
2409         b.AddEdgeTo(bNext)
2410         b.AddEdgeTo(bPanic)
2411         s.startBlock(bPanic)
2412         // TODO: implicit nil checks somehow?
2413         chk := s.newValue2(ssa.OpPanicNilCheck, ssa.TypeMem, ptr, s.mem())
2414         s.endBlock()
2415         bPanic.Kind = ssa.BlockExit
2416         bPanic.Control = chk
2417         s.startBlock(bNext)
2418 }
2419
2420 // boundsCheck generates bounds checking code.  Checks if 0 <= idx < len, branches to exit if not.
2421 // Starts a new block on return.
2422 func (s *state) boundsCheck(idx, len *ssa.Value) {
2423         if Debug['B'] != 0 {
2424                 return
2425         }
2426         // TODO: convert index to full width?
2427         // TODO: if index is 64-bit and we're compiling to 32-bit, check that high 32 bits are zero.
2428
2429         // bounds check
2430         cmp := s.newValue2(ssa.OpIsInBounds, Types[TBOOL], idx, len)
2431         s.check(cmp, Panicindex)
2432 }
2433
2434 // sliceBoundsCheck generates slice bounds checking code.  Checks if 0 <= idx <= len, branches to exit if not.
2435 // Starts a new block on return.
2436 func (s *state) sliceBoundsCheck(idx, len *ssa.Value) {
2437         if Debug['B'] != 0 {
2438                 return
2439         }
2440         // TODO: convert index to full width?
2441         // TODO: if index is 64-bit and we're compiling to 32-bit, check that high 32 bits are zero.
2442
2443         // bounds check
2444         cmp := s.newValue2(ssa.OpIsSliceInBounds, Types[TBOOL], idx, len)
2445         s.check(cmp, panicslice)
2446 }
2447
2448 // If cmp (a bool) is true, panic using the given function.
2449 func (s *state) check(cmp *ssa.Value, fn *Node) {
2450         b := s.endBlock()
2451         b.Kind = ssa.BlockIf
2452         b.Control = cmp
2453         b.Likely = ssa.BranchLikely
2454         bNext := s.f.NewBlock(ssa.BlockPlain)
2455         bPanic := s.f.NewBlock(ssa.BlockPlain)
2456         b.AddEdgeTo(bNext)
2457         b.AddEdgeTo(bPanic)
2458         s.startBlock(bPanic)
2459         // The panic call takes/returns memory to ensure that the right
2460         // memory state is observed if the panic happens.
2461         s.rtcall(fn, false, nil)
2462
2463         s.startBlock(bNext)
2464 }
2465
2466 // rtcall issues a call to the given runtime function fn with the listed args.
2467 // Returns a slice of results of the given result types.
2468 // The call is added to the end of the current block.
2469 // If returns is false, the block is marked as an exit block.
2470 // If returns is true, the block is marked as a call block.  A new block
2471 // is started to load the return values.
2472 func (s *state) rtcall(fn *Node, returns bool, results []*Type, args ...*ssa.Value) []*ssa.Value {
2473         // Write args to the stack
2474         var off int64 // TODO: arch-dependent starting offset?
2475         for _, arg := range args {
2476                 t := arg.Type
2477                 off = Rnd(off, t.Alignment())
2478                 ptr := s.sp
2479                 if off != 0 {
2480                         ptr = s.newValue1I(ssa.OpOffPtr, Types[TUINTPTR], off, s.sp)
2481                 }
2482                 size := t.Size()
2483                 s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, size, ptr, arg, s.mem())
2484                 off += size
2485         }
2486         off = Rnd(off, int64(Widthptr))
2487
2488         // Issue call
2489         call := s.newValue1A(ssa.OpStaticCall, ssa.TypeMem, fn.Sym, s.mem())
2490         s.vars[&memVar] = call
2491
2492         // Finish block
2493         b := s.endBlock()
2494         if !returns {
2495                 b.Kind = ssa.BlockExit
2496                 b.Control = call
2497                 call.AuxInt = off
2498                 if len(results) > 0 {
2499                         Fatalf("panic call can't have results")
2500                 }
2501                 return nil
2502         }
2503         b.Kind = ssa.BlockCall
2504         b.Control = call
2505         bNext := s.f.NewBlock(ssa.BlockPlain)
2506         b.AddEdgeTo(bNext)
2507         s.startBlock(bNext)
2508
2509         // Load results
2510         res := make([]*ssa.Value, len(results))
2511         for i, t := range results {
2512                 off = Rnd(off, t.Alignment())
2513                 ptr := s.sp
2514                 if off != 0 {
2515                         ptr = s.newValue1I(ssa.OpOffPtr, Types[TUINTPTR], off, s.sp)
2516                 }
2517                 res[i] = s.newValue2(ssa.OpLoad, t, ptr, s.mem())
2518                 off += t.Size()
2519         }
2520         off = Rnd(off, int64(Widthptr))
2521
2522         // Remember how much callee stack space we needed.
2523         call.AuxInt = off
2524
2525         return res
2526 }
2527
2528 // insertWB inserts a write barrier.  A value of type t has already
2529 // been stored at location p.  Tell the runtime about this write.
2530 // Note: there must be no GC suspension points between the write and
2531 // the call that this function inserts.
2532 func (s *state) insertWB(t *Type, p *ssa.Value) {
2533         // if writeBarrierEnabled {
2534         //   typedmemmove_nostore(&t, p)
2535         // }
2536         bThen := s.f.NewBlock(ssa.BlockPlain)
2537
2538         aux := &ssa.ExternSymbol{Types[TBOOL], syslook("writeBarrierEnabled", 0).Sym}
2539         flagaddr := s.newValue1A(ssa.OpAddr, Ptrto(Types[TBOOL]), aux, s.sb)
2540         flag := s.newValue2(ssa.OpLoad, Types[TBOOL], flagaddr, s.mem())
2541         b := s.endBlock()
2542         b.Kind = ssa.BlockIf
2543         b.Likely = ssa.BranchUnlikely
2544         b.Control = flag
2545         b.AddEdgeTo(bThen)
2546
2547         s.startBlock(bThen)
2548         // TODO: writebarrierptr_nostore if just one pointer word (or a few?)
2549         taddr := s.newValue1A(ssa.OpAddr, Types[TUINTPTR], &ssa.ExternSymbol{Types[TUINTPTR], typenamesym(t)}, s.sb)
2550         s.rtcall(typedmemmove_nostore, true, nil, taddr, p)
2551
2552         b.AddEdgeTo(s.curBlock)
2553 }
2554
2555 // slice computes the slice v[i:j:k] and returns ptr, len, and cap of result.
2556 // i,j,k may be nil, in which case they are set to their default value.
2557 // t is a slice, ptr to array, or string type.
2558 func (s *state) slice(t *Type, v, i, j, k *ssa.Value) (p, l, c *ssa.Value) {
2559         var elemtype *Type
2560         var ptrtype *Type
2561         var ptr *ssa.Value
2562         var len *ssa.Value
2563         var cap *ssa.Value
2564         zero := s.constInt(Types[TINT], 0)
2565         switch {
2566         case t.IsSlice():
2567                 elemtype = t.Type
2568                 ptrtype = Ptrto(elemtype)
2569                 ptr = s.newValue1(ssa.OpSlicePtr, ptrtype, v)
2570                 len = s.newValue1(ssa.OpSliceLen, Types[TINT], v)
2571                 cap = s.newValue1(ssa.OpSliceCap, Types[TINT], v)
2572         case t.IsString():
2573                 elemtype = Types[TUINT8]
2574                 ptrtype = Ptrto(elemtype)
2575                 ptr = s.newValue1(ssa.OpStringPtr, ptrtype, v)
2576                 len = s.newValue1(ssa.OpStringLen, Types[TINT], v)
2577                 cap = len
2578         case t.IsPtr():
2579                 if !t.Type.IsArray() {
2580                         s.Fatalf("bad ptr to array in slice %v\n", t)
2581                 }
2582                 elemtype = t.Type.Type
2583                 ptrtype = Ptrto(elemtype)
2584                 s.nilCheck(v)
2585                 ptr = v
2586                 len = s.constInt(Types[TINT], t.Type.Bound)
2587                 cap = len
2588         default:
2589                 s.Fatalf("bad type in slice %v\n", t)
2590         }
2591
2592         // Set default values
2593         if i == nil {
2594                 i = zero
2595         }
2596         if j == nil {
2597                 j = len
2598         }
2599         if k == nil {
2600                 k = cap
2601         }
2602
2603         // Panic if slice indices are not in bounds.
2604         s.sliceBoundsCheck(i, j)
2605         if j != k {
2606                 s.sliceBoundsCheck(j, k)
2607         }
2608         if k != cap {
2609                 s.sliceBoundsCheck(k, cap)
2610         }
2611
2612         // Generate the following code assuming that indexes are in bounds.
2613         // The conditional is to make sure that we don't generate a slice
2614         // that points to the next object in memory.
2615         // rlen = (SubPtr j i)
2616         // rcap = (SubPtr k i)
2617         // p = ptr
2618         // if rcap != 0 {
2619         //    p = (AddPtr ptr (MulPtr low (ConstPtr size)))
2620         // }
2621         // result = (SliceMake p size)
2622         rlen := s.newValue2(ssa.OpSubPtr, Types[TINT], j, i)
2623         var rcap *ssa.Value
2624         switch {
2625         case t.IsString():
2626                 // Capacity of the result is unimportant.  However, we use
2627                 // rcap to test if we've generated a zero-length slice.
2628                 // Use length of strings for that.
2629                 rcap = rlen
2630         case j == k:
2631                 rcap = rlen
2632         default:
2633                 rcap = s.newValue2(ssa.OpSubPtr, Types[TINT], k, i)
2634         }
2635
2636         s.vars[&ptrVar] = ptr
2637
2638         // Generate code to test the resulting slice length.
2639         var cmp *ssa.Value
2640         if s.config.IntSize == 8 {
2641                 cmp = s.newValue2(ssa.OpNeq64, Types[TBOOL], rcap, s.constInt(Types[TINT], 0))
2642         } else {
2643                 cmp = s.newValue2(ssa.OpNeq32, Types[TBOOL], rcap, s.constInt(Types[TINT], 0))
2644         }
2645
2646         b := s.endBlock()
2647         b.Kind = ssa.BlockIf
2648         b.Likely = ssa.BranchLikely
2649         b.Control = cmp
2650
2651         // Generate code for non-zero length slice case.
2652         nz := s.f.NewBlock(ssa.BlockPlain)
2653         b.AddEdgeTo(nz)
2654         s.startBlock(nz)
2655         var inc *ssa.Value
2656         if elemtype.Width == 1 {
2657                 inc = i
2658         } else {
2659                 inc = s.newValue2(ssa.OpMulPtr, Types[TUINTPTR], i, s.constInt(Types[TINT], elemtype.Width))
2660         }
2661         s.vars[&ptrVar] = s.newValue2(ssa.OpAddPtr, ptrtype, ptr, inc)
2662         s.endBlock()
2663
2664         // All done.
2665         merge := s.f.NewBlock(ssa.BlockPlain)
2666         b.AddEdgeTo(merge)
2667         nz.AddEdgeTo(merge)
2668         s.startBlock(merge)
2669         rptr := s.variable(&ptrVar, ptrtype)
2670         delete(s.vars, &ptrVar)
2671         return rptr, rlen, rcap
2672 }
2673
2674 type u2fcvtTab struct {
2675         geq, cvt2F, and, rsh, or, add ssa.Op
2676         one                           func(*state, ssa.Type, int64) *ssa.Value
2677 }
2678
2679 var u64_f64 u2fcvtTab = u2fcvtTab{
2680         geq:   ssa.OpGeq64,
2681         cvt2F: ssa.OpCvt64to64F,
2682         and:   ssa.OpAnd64,
2683         rsh:   ssa.OpRsh64Ux64,
2684         or:    ssa.OpOr64,
2685         add:   ssa.OpAdd64F,
2686         one:   (*state).constInt64,
2687 }
2688
2689 var u64_f32 u2fcvtTab = u2fcvtTab{
2690         geq:   ssa.OpGeq64,
2691         cvt2F: ssa.OpCvt64to32F,
2692         and:   ssa.OpAnd64,
2693         rsh:   ssa.OpRsh64Ux64,
2694         or:    ssa.OpOr64,
2695         add:   ssa.OpAdd32F,
2696         one:   (*state).constInt64,
2697 }
2698
2699 // Excess generality on a machine with 64-bit integer registers.
2700 // Not used on AMD64.
2701 var u32_f32 u2fcvtTab = u2fcvtTab{
2702         geq:   ssa.OpGeq32,
2703         cvt2F: ssa.OpCvt32to32F,
2704         and:   ssa.OpAnd32,
2705         rsh:   ssa.OpRsh32Ux32,
2706         or:    ssa.OpOr32,
2707         add:   ssa.OpAdd32F,
2708         one: func(s *state, t ssa.Type, x int64) *ssa.Value {
2709                 return s.constInt32(t, int32(x))
2710         },
2711 }
2712
2713 func (s *state) uint64Tofloat64(n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2714         return s.uintTofloat(&u64_f64, n, x, ft, tt)
2715 }
2716
2717 func (s *state) uint64Tofloat32(n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2718         return s.uintTofloat(&u64_f32, n, x, ft, tt)
2719 }
2720
2721 func (s *state) uintTofloat(cvttab *u2fcvtTab, n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2722         // if x >= 0 {
2723         //    result = (floatY) x
2724         // } else {
2725         //        y = uintX(x) ; y = x & 1
2726         //        z = uintX(x) ; z = z >> 1
2727         //        z = z >> 1
2728         //        z = z | y
2729         //        result = floatY(z)
2730         //        result = result + result
2731         // }
2732         //
2733         // Code borrowed from old code generator.
2734         // What's going on: large 64-bit "unsigned" looks like
2735         // negative number to hardware's integer-to-float
2736         // conversion.  However, because the mantissa is only
2737         // 63 bits, we don't need the LSB, so instead we do an
2738         // unsigned right shift (divide by two), convert, and
2739         // double.  However, before we do that, we need to be
2740         // sure that we do not lose a "1" if that made the
2741         // difference in the resulting rounding.  Therefore, we
2742         // preserve it, and OR (not ADD) it back in.  The case
2743         // that matters is when the eleven discarded bits are
2744         // equal to 10000000001; that rounds up, and the 1 cannot
2745         // be lost else it would round down if the LSB of the
2746         // candidate mantissa is 0.
2747         cmp := s.newValue2(cvttab.geq, Types[TBOOL], x, s.zeroVal(ft))
2748         b := s.endBlock()
2749         b.Kind = ssa.BlockIf
2750         b.Control = cmp
2751         b.Likely = ssa.BranchLikely
2752
2753         bThen := s.f.NewBlock(ssa.BlockPlain)
2754         bElse := s.f.NewBlock(ssa.BlockPlain)
2755         bAfter := s.f.NewBlock(ssa.BlockPlain)
2756
2757         b.AddEdgeTo(bThen)
2758         s.startBlock(bThen)
2759         a0 := s.newValue1(cvttab.cvt2F, tt, x)
2760         s.vars[n] = a0
2761         s.endBlock()
2762         bThen.AddEdgeTo(bAfter)
2763
2764         b.AddEdgeTo(bElse)
2765         s.startBlock(bElse)
2766         one := cvttab.one(s, ft, 1)
2767         y := s.newValue2(cvttab.and, ft, x, one)
2768         z := s.newValue2(cvttab.rsh, ft, x, one)
2769         z = s.newValue2(cvttab.or, ft, z, y)
2770         a := s.newValue1(cvttab.cvt2F, tt, z)
2771         a1 := s.newValue2(cvttab.add, tt, a, a)
2772         s.vars[n] = a1
2773         s.endBlock()
2774         bElse.AddEdgeTo(bAfter)
2775
2776         s.startBlock(bAfter)
2777         return s.variable(n, n.Type)
2778 }
2779
2780 // referenceTypeBuiltin generates code for the len/cap builtins for maps and channels.
2781 func (s *state) referenceTypeBuiltin(n *Node, x *ssa.Value) *ssa.Value {
2782         if !n.Left.Type.IsMap() && !n.Left.Type.IsChan() {
2783                 s.Fatalf("node must be a map or a channel")
2784         }
2785         // if n == nil {
2786         //   return 0
2787         // } else {
2788         //   // len
2789         //   return *((*int)n)
2790         //   // cap
2791         //   return *(((*int)n)+1)
2792         // }
2793         lenType := n.Type
2794         nilValue := s.newValue0(ssa.OpConstNil, Types[TUINTPTR])
2795         cmp := s.newValue2(ssa.OpEqPtr, Types[TBOOL], x, nilValue)
2796         b := s.endBlock()
2797         b.Kind = ssa.BlockIf
2798         b.Control = cmp
2799         b.Likely = ssa.BranchUnlikely
2800
2801         bThen := s.f.NewBlock(ssa.BlockPlain)
2802         bElse := s.f.NewBlock(ssa.BlockPlain)
2803         bAfter := s.f.NewBlock(ssa.BlockPlain)
2804
2805         // length/capacity of a nil map/chan is zero
2806         b.AddEdgeTo(bThen)
2807         s.startBlock(bThen)
2808         s.vars[n] = s.zeroVal(lenType)
2809         s.endBlock()
2810         bThen.AddEdgeTo(bAfter)
2811
2812         b.AddEdgeTo(bElse)
2813         s.startBlock(bElse)
2814         if n.Op == OLEN {
2815                 // length is stored in the first word for map/chan
2816                 s.vars[n] = s.newValue2(ssa.OpLoad, lenType, x, s.mem())
2817         } else if n.Op == OCAP {
2818                 // capacity is stored in the second word for chan
2819                 sw := s.newValue1I(ssa.OpOffPtr, lenType.PtrTo(), lenType.Width, x)
2820                 s.vars[n] = s.newValue2(ssa.OpLoad, lenType, sw, s.mem())
2821         } else {
2822                 s.Fatalf("op must be OLEN or OCAP")
2823         }
2824         s.endBlock()
2825         bElse.AddEdgeTo(bAfter)
2826
2827         s.startBlock(bAfter)
2828         return s.variable(n, lenType)
2829 }
2830
2831 type f2uCvtTab struct {
2832         ltf, cvt2U, subf ssa.Op
2833         value            func(*state, ssa.Type, float64) *ssa.Value
2834 }
2835
2836 var f32_u64 f2uCvtTab = f2uCvtTab{
2837         ltf:   ssa.OpLess32F,
2838         cvt2U: ssa.OpCvt32Fto64,
2839         subf:  ssa.OpSub32F,
2840         value: (*state).constFloat32,
2841 }
2842
2843 var f64_u64 f2uCvtTab = f2uCvtTab{
2844         ltf:   ssa.OpLess64F,
2845         cvt2U: ssa.OpCvt64Fto64,
2846         subf:  ssa.OpSub64F,
2847         value: (*state).constFloat64,
2848 }
2849
2850 func (s *state) float32ToUint64(n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2851         return s.floatToUint(&f32_u64, n, x, ft, tt)
2852 }
2853 func (s *state) float64ToUint64(n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2854         return s.floatToUint(&f64_u64, n, x, ft, tt)
2855 }
2856
2857 func (s *state) floatToUint(cvttab *f2uCvtTab, n *Node, x *ssa.Value, ft, tt *Type) *ssa.Value {
2858         // if x < 9223372036854775808.0 {
2859         //      result = uintY(x)
2860         // } else {
2861         //      y = x - 9223372036854775808.0
2862         //      z = uintY(y)
2863         //      result = z | -9223372036854775808
2864         // }
2865         twoToThe63 := cvttab.value(s, ft, 9223372036854775808.0)
2866         cmp := s.newValue2(cvttab.ltf, Types[TBOOL], x, twoToThe63)
2867         b := s.endBlock()
2868         b.Kind = ssa.BlockIf
2869         b.Control = cmp
2870         b.Likely = ssa.BranchLikely
2871
2872         bThen := s.f.NewBlock(ssa.BlockPlain)
2873         bElse := s.f.NewBlock(ssa.BlockPlain)
2874         bAfter := s.f.NewBlock(ssa.BlockPlain)
2875
2876         b.AddEdgeTo(bThen)
2877         s.startBlock(bThen)
2878         a0 := s.newValue1(cvttab.cvt2U, tt, x)
2879         s.vars[n] = a0
2880         s.endBlock()
2881         bThen.AddEdgeTo(bAfter)
2882
2883         b.AddEdgeTo(bElse)
2884         s.startBlock(bElse)
2885         y := s.newValue2(cvttab.subf, ft, x, twoToThe63)
2886         y = s.newValue1(cvttab.cvt2U, tt, y)
2887         z := s.constInt64(tt, -9223372036854775808)
2888         a1 := s.newValue2(ssa.OpOr64, tt, y, z)
2889         s.vars[n] = a1
2890         s.endBlock()
2891         bElse.AddEdgeTo(bAfter)
2892
2893         s.startBlock(bAfter)
2894         return s.variable(n, n.Type)
2895 }
2896
2897 // ifaceType returns the value for the word containing the type.
2898 // n is the node for the interface expression.
2899 // v is the corresponding value.
2900 func (s *state) ifaceType(n *Node, v *ssa.Value) *ssa.Value {
2901         byteptr := Ptrto(Types[TUINT8]) // type used in runtime prototypes for runtime type (*byte)
2902
2903         if isnilinter(n.Type) {
2904                 // Have *eface. The type is the first word in the struct.
2905                 return s.newValue1(ssa.OpITab, byteptr, v)
2906         }
2907
2908         // Have *iface.
2909         // The first word in the struct is the *itab.
2910         // If the *itab is nil, return 0.
2911         // Otherwise, the second word in the *itab is the type.
2912
2913         tab := s.newValue1(ssa.OpITab, byteptr, v)
2914         s.vars[&typVar] = tab
2915         isnonnil := s.newValue2(ssa.OpNeqPtr, Types[TBOOL], tab, s.entryNewValue0(ssa.OpConstNil, byteptr))
2916         b := s.endBlock()
2917         b.Kind = ssa.BlockIf
2918         b.Control = isnonnil
2919         b.Likely = ssa.BranchLikely
2920
2921         bLoad := s.f.NewBlock(ssa.BlockPlain)
2922         bEnd := s.f.NewBlock(ssa.BlockPlain)
2923
2924         b.AddEdgeTo(bLoad)
2925         b.AddEdgeTo(bEnd)
2926         bLoad.AddEdgeTo(bEnd)
2927
2928         s.startBlock(bLoad)
2929         off := s.newValue1I(ssa.OpOffPtr, byteptr, int64(Widthptr), tab)
2930         s.vars[&typVar] = s.newValue2(ssa.OpLoad, byteptr, off, s.mem())
2931         s.endBlock()
2932
2933         s.startBlock(bEnd)
2934         typ := s.variable(&typVar, byteptr)
2935         delete(s.vars, &typVar)
2936         return typ
2937 }
2938
2939 // dottype generates SSA for a type assertion node.
2940 // commaok indicates whether to panic or return a bool.
2941 // If commaok is false, resok will be nil.
2942 func (s *state) dottype(n *Node, commaok bool) (res, resok *ssa.Value) {
2943         iface := s.expr(n.Left)
2944         typ := s.ifaceType(n.Left, iface)  // actual concrete type
2945         target := s.expr(typename(n.Type)) // target type
2946         if !isdirectiface(n.Type) {
2947                 // walk rewrites ODOTTYPE/OAS2DOTTYPE into runtime calls except for this case.
2948                 Fatalf("dottype needs a direct iface type %s", n.Type)
2949         }
2950
2951         // TODO:  If we have a nonempty interface and its itab field is nil,
2952         // then this test is redundant and ifaceType should just branch directly to bFail.
2953         cond := s.newValue2(ssa.OpEqPtr, Types[TBOOL], typ, target)
2954         b := s.endBlock()
2955         b.Kind = ssa.BlockIf
2956         b.Control = cond
2957         b.Likely = ssa.BranchLikely
2958
2959         byteptr := Ptrto(Types[TUINT8])
2960
2961         bOk := s.f.NewBlock(ssa.BlockPlain)
2962         bFail := s.f.NewBlock(ssa.BlockPlain)
2963         b.AddEdgeTo(bOk)
2964         b.AddEdgeTo(bFail)
2965
2966         if !commaok {
2967                 // on failure, panic by calling panicdottype
2968                 s.startBlock(bFail)
2969                 taddr := s.newValue1A(ssa.OpAddr, byteptr, &ssa.ExternSymbol{byteptr, typenamesym(n.Left.Type)}, s.sb)
2970                 s.rtcall(panicdottype, false, nil, typ, target, taddr)
2971
2972                 // on success, return idata field
2973                 s.startBlock(bOk)
2974                 return s.newValue1(ssa.OpIData, n.Type, iface), nil
2975         }
2976
2977         // commaok is the more complicated case because we have
2978         // a control flow merge point.
2979         bEnd := s.f.NewBlock(ssa.BlockPlain)
2980
2981         // type assertion succeeded
2982         s.startBlock(bOk)
2983         s.vars[&idataVar] = s.newValue1(ssa.OpIData, n.Type, iface)
2984         s.vars[&okVar] = s.constBool(true)
2985         s.endBlock()
2986         bOk.AddEdgeTo(bEnd)
2987
2988         // type assertion failed
2989         s.startBlock(bFail)
2990         s.vars[&idataVar] = s.entryNewValue0(ssa.OpConstNil, byteptr)
2991         s.vars[&okVar] = s.constBool(false)
2992         s.endBlock()
2993         bFail.AddEdgeTo(bEnd)
2994
2995         // merge point
2996         s.startBlock(bEnd)
2997         res = s.variable(&idataVar, byteptr)
2998         resok = s.variable(&okVar, Types[TBOOL])
2999         delete(s.vars, &idataVar)
3000         delete(s.vars, &okVar)
3001         return res, resok
3002 }
3003
3004 // checkgoto checks that a goto from from to to does not
3005 // jump into a block or jump over variable declarations.
3006 // It is a copy of checkgoto in the pre-SSA backend,
3007 // modified only for line number handling.
3008 // TODO: document how this works and why it is designed the way it is.
3009 func (s *state) checkgoto(from *Node, to *Node) {
3010         if from.Sym == to.Sym {
3011                 return
3012         }
3013
3014         nf := 0
3015         for fs := from.Sym; fs != nil; fs = fs.Link {
3016                 nf++
3017         }
3018         nt := 0
3019         for fs := to.Sym; fs != nil; fs = fs.Link {
3020                 nt++
3021         }
3022         fs := from.Sym
3023         for ; nf > nt; nf-- {
3024                 fs = fs.Link
3025         }
3026         if fs != to.Sym {
3027                 // decide what to complain about.
3028                 // prefer to complain about 'into block' over declarations,
3029                 // so scan backward to find most recent block or else dcl.
3030                 var block *Sym
3031
3032                 var dcl *Sym
3033                 ts := to.Sym
3034                 for ; nt > nf; nt-- {
3035                         if ts.Pkg == nil {
3036                                 block = ts
3037                         } else {
3038                                 dcl = ts
3039                         }
3040                         ts = ts.Link
3041                 }
3042
3043                 for ts != fs {
3044                         if ts.Pkg == nil {
3045                                 block = ts
3046                         } else {
3047                                 dcl = ts
3048                         }
3049                         ts = ts.Link
3050                         fs = fs.Link
3051                 }
3052
3053                 lno := int(from.Left.Lineno)
3054                 if block != nil {
3055                         yyerrorl(lno, "goto %v jumps into block starting at %v", from.Left.Sym, Ctxt.Line(int(block.Lastlineno)))
3056                 } else {
3057                         yyerrorl(lno, "goto %v jumps over declaration of %v at %v", from.Left.Sym, dcl, Ctxt.Line(int(dcl.Lastlineno)))
3058                 }
3059         }
3060 }
3061
3062 // variable returns the value of a variable at the current location.
3063 func (s *state) variable(name *Node, t ssa.Type) *ssa.Value {
3064         v := s.vars[name]
3065         if v == nil {
3066                 // TODO: get type?  Take Sym as arg?
3067                 v = s.newValue0A(ssa.OpFwdRef, t, name)
3068                 s.vars[name] = v
3069         }
3070         return v
3071 }
3072
3073 func (s *state) mem() *ssa.Value {
3074         return s.variable(&memVar, ssa.TypeMem)
3075 }
3076
3077 func (s *state) linkForwardReferences() {
3078         // Build ssa graph.  Each variable on its first use in a basic block
3079         // leaves a FwdRef in that block representing the incoming value
3080         // of that variable.  This function links that ref up with possible definitions,
3081         // inserting Phi values as needed.  This is essentially the algorithm
3082         // described by Brau, Buchwald, Hack, Leißa, Mallon, and Zwinkau:
3083         // http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
3084         for _, b := range s.f.Blocks {
3085                 for _, v := range b.Values {
3086                         if v.Op != ssa.OpFwdRef {
3087                                 continue
3088                         }
3089                         name := v.Aux.(*Node)
3090                         v.Op = ssa.OpCopy
3091                         v.Aux = nil
3092                         v.SetArgs1(s.lookupVarIncoming(b, v.Type, name))
3093                 }
3094         }
3095 }
3096
3097 // lookupVarIncoming finds the variable's value at the start of block b.
3098 func (s *state) lookupVarIncoming(b *ssa.Block, t ssa.Type, name *Node) *ssa.Value {
3099         // TODO(khr): have lookupVarIncoming overwrite the fwdRef or copy it
3100         // will be used in, instead of having the result used in a copy value.
3101         if b == s.f.Entry {
3102                 if name == &memVar {
3103                         return s.startmem
3104                 }
3105                 // variable is live at the entry block.  Load it.
3106                 addr := s.decladdrs[name]
3107                 if addr == nil {
3108                         // TODO: closure args reach here.
3109                         s.Unimplementedf("unhandled closure arg %s at entry to function %s", name, b.Func.Name)
3110                 }
3111                 if _, ok := addr.Aux.(*ssa.ArgSymbol); !ok {
3112                         s.Fatalf("variable live at start of function %s is not an argument %s", b.Func.Name, name)
3113                 }
3114                 return s.entryNewValue2(ssa.OpLoad, t, addr, s.startmem)
3115         }
3116         var vals []*ssa.Value
3117         for _, p := range b.Preds {
3118                 vals = append(vals, s.lookupVarOutgoing(p, t, name))
3119         }
3120         if len(vals) == 0 {
3121                 // This block is dead; we have no predecessors and we're not the entry block.
3122                 // It doesn't matter what we use here as long as it is well-formed,
3123                 // so use the default/zero value.
3124                 if name == &memVar {
3125                         return s.startmem
3126                 }
3127                 return s.zeroVal(name.Type)
3128         }
3129         v0 := vals[0]
3130         for i := 1; i < len(vals); i++ {
3131                 if vals[i] != v0 {
3132                         // need a phi value
3133                         v := b.NewValue0(s.peekLine(), ssa.OpPhi, t)
3134                         v.AddArgs(vals...)
3135                         return v
3136                 }
3137         }
3138         return v0
3139 }
3140
3141 // lookupVarOutgoing finds the variable's value at the end of block b.
3142 func (s *state) lookupVarOutgoing(b *ssa.Block, t ssa.Type, name *Node) *ssa.Value {
3143         m := s.defvars[b.ID]
3144         if v, ok := m[name]; ok {
3145                 return v
3146         }
3147         // The variable is not defined by b and we haven't
3148         // looked it up yet.  Generate v, a copy value which
3149         // will be the outgoing value of the variable.  Then
3150         // look up w, the incoming value of the variable.
3151         // Make v = copy(w).  We need the extra copy to
3152         // prevent infinite recursion when looking up the
3153         // incoming value of the variable.
3154         v := b.NewValue0(s.peekLine(), ssa.OpCopy, t)
3155         m[name] = v
3156         v.AddArg(s.lookupVarIncoming(b, t, name))
3157         return v
3158 }
3159
3160 // TODO: the above mutually recursive functions can lead to very deep stacks.  Fix that.
3161
3162 // an unresolved branch
3163 type branch struct {
3164         p *obj.Prog  // branch instruction
3165         b *ssa.Block // target
3166 }
3167
3168 type genState struct {
3169         // branches remembers all the branch instructions we've seen
3170         // and where they would like to go.
3171         branches []branch
3172
3173         // bstart remembers where each block starts (indexed by block ID)
3174         bstart []*obj.Prog
3175
3176         // deferBranches remembers all the defer branches we've seen.
3177         deferBranches []*obj.Prog
3178
3179         // deferTarget remembers the (last) deferreturn call site.
3180         deferTarget *obj.Prog
3181 }
3182
3183 // genssa appends entries to ptxt for each instruction in f.
3184 // gcargs and gclocals are filled in with pointer maps for the frame.
3185 func genssa(f *ssa.Func, ptxt *obj.Prog, gcargs, gclocals *Sym) {
3186         var s genState
3187
3188         e := f.Config.Frontend().(*ssaExport)
3189         // We're about to emit a bunch of Progs.
3190         // Since the only way to get here is to explicitly request it,
3191         // just fail on unimplemented instead of trying to unwind our mess.
3192         e.mustImplement = true
3193
3194         // Remember where each block starts.
3195         s.bstart = make([]*obj.Prog, f.NumBlocks())
3196
3197         var valueProgs map[*obj.Prog]*ssa.Value
3198         var blockProgs map[*obj.Prog]*ssa.Block
3199         const logProgs = true
3200         if logProgs {
3201                 valueProgs = make(map[*obj.Prog]*ssa.Value, f.NumValues())
3202                 blockProgs = make(map[*obj.Prog]*ssa.Block, f.NumBlocks())
3203                 f.Logf("genssa %s\n", f.Name)
3204                 blockProgs[Pc] = f.Blocks[0]
3205         }
3206
3207         // Emit basic blocks
3208         for i, b := range f.Blocks {
3209                 s.bstart[b.ID] = Pc
3210                 // Emit values in block
3211                 for _, v := range b.Values {
3212                         x := Pc
3213                         s.genValue(v)
3214                         if logProgs {
3215                                 for ; x != Pc; x = x.Link {
3216                                         valueProgs[x] = v
3217                                 }
3218                         }
3219                 }
3220                 // Emit control flow instructions for block
3221                 var next *ssa.Block
3222                 if i < len(f.Blocks)-1 {
3223                         next = f.Blocks[i+1]
3224                 }
3225                 x := Pc
3226                 s.genBlock(b, next)
3227                 if logProgs {
3228                         for ; x != Pc; x = x.Link {
3229                                 blockProgs[x] = b
3230                         }
3231                 }
3232         }
3233
3234         // Resolve branches
3235         for _, br := range s.branches {
3236                 br.p.To.Val = s.bstart[br.b.ID]
3237         }
3238         if s.deferBranches != nil && s.deferTarget == nil {
3239                 // This can happen when the function has a defer but
3240                 // no return (because it has an infinite loop).
3241                 s.deferReturn()
3242                 Prog(obj.ARET)
3243         }
3244         for _, p := range s.deferBranches {
3245                 p.To.Val = s.deferTarget
3246         }
3247
3248         if logProgs {
3249                 for p := ptxt; p != nil; p = p.Link {
3250                         var s string
3251                         if v, ok := valueProgs[p]; ok {
3252                                 s = v.String()
3253                         } else if b, ok := blockProgs[p]; ok {
3254                                 s = b.String()
3255                         } else {
3256                                 s = "   " // most value and branch strings are 2-3 characters long
3257                         }
3258                         f.Logf("%s\t%s\n", s, p)
3259                 }
3260                 if f.Config.HTML != nil {
3261                         saved := ptxt.Ctxt.LineHist.PrintFilenameOnly
3262                         ptxt.Ctxt.LineHist.PrintFilenameOnly = true
3263                         var buf bytes.Buffer
3264                         buf.WriteString("<code>")
3265                         buf.WriteString("<dl class=\"ssa-gen\">")
3266                         for p := ptxt; p != nil; p = p.Link {
3267                                 buf.WriteString("<dt class=\"ssa-prog-src\">")
3268                                 if v, ok := valueProgs[p]; ok {
3269                                         buf.WriteString(v.HTML())
3270                                 } else if b, ok := blockProgs[p]; ok {
3271                                         buf.WriteString(b.HTML())
3272                                 }
3273                                 buf.WriteString("</dt>")
3274                                 buf.WriteString("<dd class=\"ssa-prog\">")
3275                                 buf.WriteString(html.EscapeString(p.String()))
3276                                 buf.WriteString("</dd>")
3277                                 buf.WriteString("</li>")
3278                         }
3279                         buf.WriteString("</dl>")
3280                         buf.WriteString("</code>")
3281                         f.Config.HTML.WriteColumn("genssa", buf.String())
3282                         ptxt.Ctxt.LineHist.PrintFilenameOnly = saved
3283                 }
3284         }
3285
3286         // Emit static data
3287         if f.StaticData != nil {
3288                 for _, n := range f.StaticData.([]*Node) {
3289                         if !gen_as_init(n, false) {
3290                                 Fatalf("non-static data marked as static: %v\n\n", n, f)
3291                         }
3292                 }
3293         }
3294
3295         // Allocate stack frame
3296         allocauto(ptxt)
3297
3298         // Generate gc bitmaps.
3299         liveness(Curfn, ptxt, gcargs, gclocals)
3300         gcsymdup(gcargs)
3301         gcsymdup(gclocals)
3302
3303         // Add frame prologue.  Zero ambiguously live variables.
3304         Thearch.Defframe(ptxt)
3305         if Debug['f'] != 0 {
3306                 frame(0)
3307         }
3308
3309         // Remove leftover instrumentation from the instruction stream.
3310         removevardef(ptxt)
3311
3312         f.Config.HTML.Close()
3313 }
3314
3315 // opregreg emits instructions for
3316 //     dest := dest(To) op src(From)
3317 // and also returns the created obj.Prog so it
3318 // may be further adjusted (offset, scale, etc).
3319 func opregreg(op int, dest, src int16) *obj.Prog {
3320         p := Prog(op)
3321         p.From.Type = obj.TYPE_REG
3322         p.To.Type = obj.TYPE_REG
3323         p.To.Reg = dest
3324         p.From.Reg = src
3325         return p
3326 }
3327
3328 func (s *genState) genValue(v *ssa.Value) {
3329         lineno = v.Line
3330         switch v.Op {
3331         case ssa.OpAMD64ADDQ:
3332                 // TODO: use addq instead of leaq if target is in the right register.
3333                 p := Prog(x86.ALEAQ)
3334                 p.From.Type = obj.TYPE_MEM
3335                 p.From.Reg = regnum(v.Args[0])
3336                 p.From.Scale = 1
3337                 p.From.Index = regnum(v.Args[1])
3338                 p.To.Type = obj.TYPE_REG
3339                 p.To.Reg = regnum(v)
3340         case ssa.OpAMD64ADDL:
3341                 p := Prog(x86.ALEAL)
3342                 p.From.Type = obj.TYPE_MEM
3343                 p.From.Reg = regnum(v.Args[0])
3344                 p.From.Scale = 1
3345                 p.From.Index = regnum(v.Args[1])
3346                 p.To.Type = obj.TYPE_REG
3347                 p.To.Reg = regnum(v)
3348         case ssa.OpAMD64ADDW:
3349                 p := Prog(x86.ALEAW)
3350                 p.From.Type = obj.TYPE_MEM
3351                 p.From.Reg = regnum(v.Args[0])
3352                 p.From.Scale = 1
3353                 p.From.Index = regnum(v.Args[1])
3354                 p.To.Type = obj.TYPE_REG
3355                 p.To.Reg = regnum(v)
3356         // 2-address opcode arithmetic, symmetric
3357         case ssa.OpAMD64ADDB, ssa.OpAMD64ADDSS, ssa.OpAMD64ADDSD,
3358                 ssa.OpAMD64ANDQ, ssa.OpAMD64ANDL, ssa.OpAMD64ANDW, ssa.OpAMD64ANDB,
3359                 ssa.OpAMD64ORQ, ssa.OpAMD64ORL, ssa.OpAMD64ORW, ssa.OpAMD64ORB,
3360                 ssa.OpAMD64XORQ, ssa.OpAMD64XORL, ssa.OpAMD64XORW, ssa.OpAMD64XORB,
3361                 ssa.OpAMD64MULQ, ssa.OpAMD64MULL, ssa.OpAMD64MULW, ssa.OpAMD64MULB,
3362                 ssa.OpAMD64MULSS, ssa.OpAMD64MULSD, ssa.OpAMD64PXOR:
3363                 r := regnum(v)
3364                 x := regnum(v.Args[0])
3365                 y := regnum(v.Args[1])
3366                 if x != r && y != r {
3367                         opregreg(regMoveByTypeAMD64(v.Type), r, x)
3368                         x = r
3369                 }
3370                 p := Prog(v.Op.Asm())
3371                 p.From.Type = obj.TYPE_REG
3372                 p.To.Type = obj.TYPE_REG
3373                 p.To.Reg = r
3374                 if x == r {
3375                         p.From.Reg = y
3376                 } else {
3377                         p.From.Reg = x
3378                 }
3379         // 2-address opcode arithmetic, not symmetric
3380         case ssa.OpAMD64SUBQ, ssa.OpAMD64SUBL, ssa.OpAMD64SUBW, ssa.OpAMD64SUBB:
3381                 r := regnum(v)
3382                 x := regnum(v.Args[0])
3383                 y := regnum(v.Args[1])
3384                 var neg bool
3385                 if y == r {
3386                         // compute -(y-x) instead
3387                         x, y = y, x
3388                         neg = true
3389                 }
3390                 if x != r {
3391                         opregreg(regMoveByTypeAMD64(v.Type), r, x)
3392                 }
3393                 opregreg(v.Op.Asm(), r, y)
3394
3395                 if neg {
3396                         p := Prog(x86.ANEGQ) // TODO: use correct size?  This is mostly a hack until regalloc does 2-address correctly
3397                         p.To.Type = obj.TYPE_REG
3398                         p.To.Reg = r
3399                 }
3400         case ssa.OpAMD64SUBSS, ssa.OpAMD64SUBSD, ssa.OpAMD64DIVSS, ssa.OpAMD64DIVSD:
3401                 r := regnum(v)
3402                 x := regnum(v.Args[0])
3403                 y := regnum(v.Args[1])
3404                 if y == r && x != r {
3405                         // r/y := x op r/y, need to preserve x and rewrite to
3406                         // r/y := r/y op x15
3407                         x15 := int16(x86.REG_X15)
3408                         // register move y to x15
3409                         // register move x to y
3410                         // rename y with x15
3411                         opregreg(regMoveByTypeAMD64(v.Type), x15, y)
3412                         opregreg(regMoveByTypeAMD64(v.Type), r, x)
3413                         y = x15
3414                 } else if x != r {
3415                         opregreg(regMoveByTypeAMD64(v.Type), r, x)
3416                 }
3417                 opregreg(v.Op.Asm(), r, y)
3418
3419         case ssa.OpAMD64DIVQ, ssa.OpAMD64DIVL, ssa.OpAMD64DIVW,
3420                 ssa.OpAMD64DIVQU, ssa.OpAMD64DIVLU, ssa.OpAMD64DIVWU,
3421                 ssa.OpAMD64MODQ, ssa.OpAMD64MODL, ssa.OpAMD64MODW,
3422                 ssa.OpAMD64MODQU, ssa.OpAMD64MODLU, ssa.OpAMD64MODWU:
3423
3424                 // Arg[0] is already in AX as it's the only register we allow
3425                 // and AX is the only output
3426                 x := regnum(v.Args[1])
3427
3428                 // CPU faults upon signed overflow, which occurs when most
3429                 // negative int is divided by -1.
3430                 var j *obj.Prog
3431                 if v.Op == ssa.OpAMD64DIVQ || v.Op == ssa.OpAMD64DIVL ||
3432                         v.Op == ssa.OpAMD64DIVW || v.Op == ssa.OpAMD64MODQ ||
3433                         v.Op == ssa.OpAMD64MODL || v.Op == ssa.OpAMD64MODW {
3434
3435                         var c *obj.Prog
3436                         switch v.Op {
3437                         case ssa.OpAMD64DIVQ, ssa.OpAMD64MODQ:
3438                                 c = Prog(x86.ACMPQ)
3439                                 j = Prog(x86.AJEQ)
3440                                 // go ahead and sign extend to save doing it later
3441                                 Prog(x86.ACQO)
3442
3443                         case ssa.OpAMD64DIVL, ssa.OpAMD64MODL:
3444                                 c = Prog(x86.ACMPL)
3445                                 j = Prog(x86.AJEQ)
3446                                 Prog(x86.ACDQ)
3447
3448                         case ssa.OpAMD64DIVW, ssa.OpAMD64MODW:
3449                                 c = Prog(x86.ACMPW)
3450                                 j = Prog(x86.AJEQ)
3451                                 Prog(x86.ACWD)
3452                         }
3453                         c.From.Type = obj.TYPE_REG
3454                         c.From.Reg = x
3455                         c.To.Type = obj.TYPE_CONST
3456                         c.To.Offset = -1
3457
3458                         j.To.Type = obj.TYPE_BRANCH
3459
3460                 }
3461
3462                 // for unsigned ints, we sign extend by setting DX = 0
3463                 // signed ints were sign extended above
3464                 if v.Op == ssa.OpAMD64DIVQU || v.Op == ssa.OpAMD64MODQU ||
3465                         v.Op == ssa.OpAMD64DIVLU || v.Op == ssa.OpAMD64MODLU ||
3466                         v.Op == ssa.OpAMD64DIVWU || v.Op == ssa.OpAMD64MODWU {
3467                         c := Prog(x86.AXORQ)
3468                         c.From.Type = obj.TYPE_REG
3469                         c.From.Reg = x86.REG_DX
3470                         c.To.Type = obj.TYPE_REG
3471                         c.To.Reg = x86.REG_DX
3472                 }
3473
3474                 p := Prog(v.Op.Asm())
3475                 p.From.Type = obj.TYPE_REG
3476                 p.From.Reg = x
3477
3478                 // signed division, rest of the check for -1 case
3479                 if j != nil {
3480                         j2 := Prog(obj.AJMP)
3481                         j2.To.Type = obj.TYPE_BRANCH
3482
3483                         var n *obj.Prog
3484                         if v.Op == ssa.OpAMD64DIVQ || v.Op == ssa.OpAMD64DIVL ||
3485                                 v.Op == ssa.OpAMD64DIVW {
3486                                 // n * -1 = -n
3487                                 n = Prog(x86.ANEGQ)
3488                                 n.To.Type = obj.TYPE_REG
3489                                 n.To.Reg = x86.REG_AX
3490                         } else {
3491                                 // n % -1 == 0
3492                                 n = Prog(x86.AXORQ)
3493                                 n.From.Type = obj.TYPE_REG
3494                                 n.From.Reg = x86.REG_DX
3495                                 n.To.Type = obj.TYPE_REG
3496                                 n.To.Reg = x86.REG_DX
3497                         }
3498
3499                         j.To.Val = n
3500                         j2.To.Val = Pc
3501                 }
3502
3503         case ssa.OpAMD64HMULL, ssa.OpAMD64HMULW, ssa.OpAMD64HMULB,
3504                 ssa.OpAMD64HMULLU, ssa.OpAMD64HMULWU, ssa.OpAMD64HMULBU:
3505                 // the frontend rewrites constant division by 8/16/32 bit integers into
3506                 // HMUL by a constant
3507
3508                 // Arg[0] is already in AX as it's the only register we allow
3509                 // and DX is the only output we care about (the high bits)
3510                 p := Prog(v.Op.Asm())
3511                 p.From.Type = obj.TYPE_REG
3512                 p.From.Reg = regnum(v.Args[1])
3513
3514                 // IMULB puts the high portion in AH instead of DL,
3515                 // so move it to DL for consistency
3516                 if v.Type.Size() == 1 {
3517                         m := Prog(x86.AMOVB)
3518                         m.From.Type = obj.TYPE_REG
3519                         m.From.Reg = x86.REG_AH
3520                         m.To.Type = obj.TYPE_REG
3521                         m.To.Reg = x86.REG_DX
3522                 }
3523
3524         case ssa.OpAMD64SHLQ, ssa.OpAMD64SHLL, ssa.OpAMD64SHLW, ssa.OpAMD64SHLB,
3525                 ssa.OpAMD64SHRQ, ssa.OpAMD64SHRL, ssa.OpAMD64SHRW, ssa.OpAMD64SHRB,
3526                 ssa.OpAMD64SARQ, ssa.OpAMD64SARL, ssa.OpAMD64SARW, ssa.OpAMD64SARB:
3527                 x := regnum(v.Args[0])
3528                 r := regnum(v)
3529                 if x != r {
3530                         if r == x86.REG_CX {
3531                                 v.Fatalf("can't implement %s, target and shift both in CX", v.LongString())
3532                         }
3533                         p := Prog(regMoveAMD64(v.Type.Size()))
3534                         p.From.Type = obj.TYPE_REG
3535                         p.From.Reg = x
3536                         p.To.Type = obj.TYPE_REG
3537                         p.To.Reg = r
3538                 }
3539                 p := Prog(v.Op.Asm())
3540                 p.From.Type = obj.TYPE_REG
3541                 p.From.Reg = regnum(v.Args[1]) // should be CX
3542                 p.To.Type = obj.TYPE_REG
3543                 p.To.Reg = r
3544         case ssa.OpAMD64ADDQconst, ssa.OpAMD64ADDLconst, ssa.OpAMD64ADDWconst:
3545                 // TODO: use addq instead of leaq if target is in the right register.
3546                 var asm int
3547                 switch v.Op {
3548                 case ssa.OpAMD64ADDQconst:
3549                         asm = x86.ALEAQ
3550                 case ssa.OpAMD64ADDLconst:
3551                         asm = x86.ALEAL
3552                 case ssa.OpAMD64ADDWconst:
3553                         asm = x86.ALEAW
3554                 }
3555                 p := Prog(asm)
3556                 p.From.Type = obj.TYPE_MEM
3557                 p.From.Reg = regnum(v.Args[0])
3558                 p.From.Offset = v.AuxInt
3559                 p.To.Type = obj.TYPE_REG
3560                 p.To.Reg = regnum(v)
3561         case ssa.OpAMD64MULQconst, ssa.OpAMD64MULLconst, ssa.OpAMD64MULWconst, ssa.OpAMD64MULBconst:
3562                 r := regnum(v)
3563                 x := regnum(v.Args[0])
3564                 if r != x {
3565                         p := Prog(regMoveAMD64(v.Type.Size()))
3566                         p.From.Type = obj.TYPE_REG
3567                         p.From.Reg = x
3568                         p.To.Type = obj.TYPE_REG
3569                         p.To.Reg = r
3570                 }
3571                 p := Prog(v.Op.Asm())
3572                 p.From.Type = obj.TYPE_CONST
3573                 p.From.Offset = v.AuxInt
3574                 p.To.Type = obj.TYPE_REG
3575                 p.To.Reg = r
3576                 // TODO: Teach doasm to compile the three-address multiply imul $c, r1, r2
3577                 // instead of using the MOVQ above.
3578                 //p.From3 = new(obj.Addr)
3579                 //p.From3.Type = obj.TYPE_REG
3580                 //p.From3.Reg = regnum(v.Args[0])
3581         case ssa.OpAMD64ADDBconst,
3582                 ssa.OpAMD64ANDQconst, ssa.OpAMD64ANDLconst, ssa.OpAMD64ANDWconst, ssa.OpAMD64ANDBconst,
3583                 ssa.OpAMD64ORQconst, ssa.OpAMD64ORLconst, ssa.OpAMD64ORWconst, ssa.OpAMD64ORBconst,
3584                 ssa.OpAMD64XORQconst, ssa.OpAMD64XORLconst, ssa.OpAMD64XORWconst, ssa.OpAMD64XORBconst,
3585                 ssa.OpAMD64SUBQconst, ssa.OpAMD64SUBLconst, ssa.OpAMD64SUBWconst, ssa.OpAMD64SUBBconst,
3586                 ssa.OpAMD64SHLQconst, ssa.OpAMD64SHLLconst, ssa.OpAMD64SHLWconst, ssa.OpAMD64SHLBconst,
3587                 ssa.OpAMD64SHRQconst, ssa.OpAMD64SHRLconst, ssa.OpAMD64SHRWconst, ssa.OpAMD64SHRBconst,
3588                 ssa.OpAMD64SARQconst, ssa.OpAMD64SARLconst, ssa.OpAMD64SARWconst, ssa.OpAMD64SARBconst,
3589                 ssa.OpAMD64ROLQconst, ssa.OpAMD64ROLLconst, ssa.OpAMD64ROLWconst, ssa.OpAMD64ROLBconst:
3590                 // This code compensates for the fact that the register allocator
3591                 // doesn't understand 2-address instructions yet.  TODO: fix that.
3592                 x := regnum(v.Args[0])
3593                 r := regnum(v)
3594                 if x != r {
3595                         p := Prog(regMoveAMD64(v.Type.Size()))
3596                         p.From.Type = obj.TYPE_REG
3597                         p.From.Reg = x
3598                         p.To.Type = obj.TYPE_REG
3599                         p.To.Reg = r
3600                 }
3601                 p := Prog(v.Op.Asm())
3602                 p.From.Type = obj.TYPE_CONST
3603                 p.From.Offset = v.AuxInt
3604                 p.To.Type = obj.TYPE_REG
3605                 p.To.Reg = r
3606         case ssa.OpAMD64SBBQcarrymask, ssa.OpAMD64SBBLcarrymask:
3607                 r := regnum(v)
3608                 p := Prog(v.Op.Asm())
3609                 p.From.Type = obj.TYPE_REG
3610                 p.From.Reg = r
3611                 p.To.Type = obj.TYPE_REG
3612                 p.To.Reg = r
3613         case ssa.OpAMD64LEAQ1, ssa.OpAMD64LEAQ2, ssa.OpAMD64LEAQ4, ssa.OpAMD64LEAQ8:
3614                 p := Prog(x86.ALEAQ)
3615                 p.From.Type = obj.TYPE_MEM
3616                 p.From.Reg = regnum(v.Args[0])
3617                 switch v.Op {
3618                 case ssa.OpAMD64LEAQ1:
3619                         p.From.Scale = 1
3620                 case ssa.OpAMD64LEAQ2:
3621                         p.From.Scale = 2
3622                 case ssa.OpAMD64LEAQ4:
3623                         p.From.Scale = 4
3624                 case ssa.OpAMD64LEAQ8:
3625                         p.From.Scale = 8
3626                 }
3627                 p.From.Index = regnum(v.Args[1])
3628                 addAux(&p.From, v)
3629                 p.To.Type = obj.TYPE_REG
3630                 p.To.Reg = regnum(v)
3631         case ssa.OpAMD64LEAQ:
3632                 p := Prog(x86.ALEAQ)
3633                 p.From.Type = obj.TYPE_MEM
3634                 p.From.Reg = regnum(v.Args[0])
3635                 addAux(&p.From, v)
3636                 p.To.Type = obj.TYPE_REG
3637                 p.To.Reg = regnum(v)
3638         case ssa.OpAMD64CMPQ, ssa.OpAMD64CMPL, ssa.OpAMD64CMPW, ssa.OpAMD64CMPB,
3639                 ssa.OpAMD64TESTQ, ssa.OpAMD64TESTL, ssa.OpAMD64TESTW, ssa.OpAMD64TESTB:
3640                 opregreg(v.Op.Asm(), regnum(v.Args[1]), regnum(v.Args[0]))
3641         case ssa.OpAMD64UCOMISS, ssa.OpAMD64UCOMISD:
3642                 // Go assembler has swapped operands for UCOMISx relative to CMP,
3643                 // must account for that right here.
3644                 opregreg(v.Op.Asm(), regnum(v.Args[0]), regnum(v.Args[1]))
3645         case ssa.OpAMD64CMPQconst, ssa.OpAMD64CMPLconst, ssa.OpAMD64CMPWconst, ssa.OpAMD64CMPBconst,
3646                 ssa.OpAMD64TESTQconst, ssa.OpAMD64TESTLconst, ssa.OpAMD64TESTWconst, ssa.OpAMD64TESTBconst:
3647                 p := Prog(v.Op.Asm())
3648                 p.From.Type = obj.TYPE_REG
3649                 p.From.Reg = regnum(v.Args[0])
3650                 p.To.Type = obj.TYPE_CONST
3651                 p.To.Offset = v.AuxInt
3652         case ssa.OpAMD64MOVBconst, ssa.OpAMD64MOVWconst, ssa.OpAMD64MOVLconst, ssa.OpAMD64MOVQconst:
3653                 x := regnum(v)
3654                 p := Prog(v.Op.Asm())
3655                 p.From.Type = obj.TYPE_CONST
3656                 var i int64
3657                 switch v.Op {
3658                 case ssa.OpAMD64MOVBconst:
3659                         i = int64(int8(v.AuxInt))
3660                 case ssa.OpAMD64MOVWconst:
3661                         i = int64(int16(v.AuxInt))
3662                 case ssa.OpAMD64MOVLconst:
3663                         i = int64(int32(v.AuxInt))
3664                 case ssa.OpAMD64MOVQconst:
3665                         i = v.AuxInt
3666                 }
3667                 p.From.Offset = i
3668                 p.To.Type = obj.TYPE_REG
3669                 p.To.Reg = x
3670         case ssa.OpAMD64MOVSSconst, ssa.OpAMD64MOVSDconst:
3671                 x := regnum(v)
3672                 p := Prog(v.Op.Asm())
3673                 p.From.Type = obj.TYPE_FCONST
3674                 p.From.Val = math.Float64frombits(uint64(v.AuxInt))
3675                 p.To.Type = obj.TYPE_REG
3676                 p.To.Reg = x
3677         case ssa.OpAMD64MOVQload, ssa.OpAMD64MOVSSload, ssa.OpAMD64MOVSDload, ssa.OpAMD64MOVLload, ssa.OpAMD64MOVWload, ssa.OpAMD64MOVBload, ssa.OpAMD64MOVBQSXload, ssa.OpAMD64MOVBQZXload:
3678                 p := Prog(v.Op.Asm())
3679                 p.From.Type = obj.TYPE_MEM
3680                 p.From.Reg = regnum(v.Args[0])
3681                 addAux(&p.From, v)
3682                 p.To.Type = obj.TYPE_REG
3683                 p.To.Reg = regnum(v)
3684         case ssa.OpAMD64MOVQloadidx8, ssa.OpAMD64MOVSDloadidx8:
3685                 p := Prog(v.Op.Asm())
3686                 p.From.Type = obj.TYPE_MEM
3687                 p.From.Reg = regnum(v.Args[0])
3688                 addAux(&p.From, v)
3689                 p.From.Scale = 8
3690                 p.From.Index = regnum(v.Args[1])
3691                 p.To.Type = obj.TYPE_REG
3692                 p.To.Reg = regnum(v)
3693         case ssa.OpAMD64MOVSSloadidx4:
3694                 p := Prog(v.Op.Asm())
3695                 p.From.Type = obj.TYPE_MEM
3696                 p.From.Reg = regnum(v.Args[0])
3697                 addAux(&p.From, v)
3698                 p.From.Scale = 4
3699                 p.From.Index = regnum(v.Args[1])
3700                 p.To.Type = obj.TYPE_REG
3701                 p.To.Reg = regnum(v)
3702         case ssa.OpAMD64MOVQstore, ssa.OpAMD64MOVSSstore, ssa.OpAMD64MOVSDstore, ssa.OpAMD64MOVLstore, ssa.OpAMD64MOVWstore, ssa.OpAMD64MOVBstore:
3703                 p := Prog(v.Op.Asm())
3704                 p.From.Type = obj.TYPE_REG
3705                 p.From.Reg = regnum(v.Args[1])
3706                 p.To.Type = obj.TYPE_MEM
3707                 p.To.Reg = regnum(v.Args[0])
3708                 addAux(&p.To, v)
3709         case ssa.OpAMD64MOVQstoreidx8, ssa.OpAMD64MOVSDstoreidx8:
3710                 p := Prog(v.Op.Asm())
3711                 p.From.Type = obj.TYPE_REG
3712                 p.From.Reg = regnum(v.Args[2])
3713                 p.To.Type = obj.TYPE_MEM
3714                 p.To.Reg = regnum(v.Args[0])
3715                 p.To.Scale = 8
3716                 p.To.Index = regnum(v.Args[1])
3717                 addAux(&p.To, v)
3718         case ssa.OpAMD64MOVSSstoreidx4:
3719                 p := Prog(v.Op.Asm())
3720                 p.From.Type = obj.TYPE_REG
3721                 p.From.Reg = regnum(v.Args[2])
3722                 p.To.Type = obj.TYPE_MEM
3723                 p.To.Reg = regnum(v.Args[0])
3724                 p.To.Scale = 4
3725                 p.To.Index = regnum(v.Args[1])
3726                 addAux(&p.To, v)
3727         case ssa.OpAMD64MOVLQSX, ssa.OpAMD64MOVWQSX, ssa.OpAMD64MOVBQSX, ssa.OpAMD64MOVLQZX, ssa.OpAMD64MOVWQZX, ssa.OpAMD64MOVBQZX,
3728                 ssa.OpAMD64CVTSL2SS, ssa.OpAMD64CVTSL2SD, ssa.OpAMD64CVTSQ2SS, ssa.OpAMD64CVTSQ2SD,
3729                 ssa.OpAMD64CVTTSS2SL, ssa.OpAMD64CVTTSD2SL, ssa.OpAMD64CVTTSS2SQ, ssa.OpAMD64CVTTSD2SQ,
3730                 ssa.OpAMD64CVTSS2SD, ssa.OpAMD64CVTSD2SS:
3731                 opregreg(v.Op.Asm(), regnum(v), regnum(v.Args[0]))
3732         case ssa.OpAMD64DUFFZERO:
3733                 p := Prog(obj.ADUFFZERO)
3734                 p.To.Type = obj.TYPE_ADDR
3735                 p.To.Sym = Linksym(Pkglookup("duffzero", Runtimepkg))
3736                 p.To.Offset = v.AuxInt
3737         case ssa.OpAMD64MOVOconst:
3738                 if v.AuxInt != 0 {
3739                         v.Unimplementedf("MOVOconst can only do constant=0")
3740                 }
3741                 r := regnum(v)
3742                 opregreg(x86.AXORPS, r, r)
3743
3744         case ssa.OpCopy: // TODO: lower to MOVQ earlier?
3745                 if v.Type.IsMemory() {
3746                         return
3747                 }
3748                 x := regnum(v.Args[0])
3749                 y := regnum(v)
3750                 if x != y {
3751                         opregreg(regMoveByTypeAMD64(v.Type), y, x)
3752                 }
3753         case ssa.OpLoadReg:
3754                 if v.Type.IsFlags() {
3755                         v.Unimplementedf("load flags not implemented: %v", v.LongString())
3756                         return
3757                 }
3758                 p := Prog(movSizeByType(v.Type))
3759                 n := autoVar(v.Args[0])
3760                 p.From.Type = obj.TYPE_MEM
3761                 p.From.Name = obj.NAME_AUTO
3762                 p.From.Node = n
3763                 p.From.Sym = Linksym(n.Sym)
3764                 p.To.Type = obj.TYPE_REG
3765                 p.To.Reg = regnum(v)
3766
3767         case ssa.OpStoreReg:
3768                 if v.Type.IsFlags() {
3769                         v.Unimplementedf("store flags not implemented: %v", v.LongString())
3770                         return
3771                 }
3772                 p := Prog(movSizeByType(v.Type))
3773                 p.From.Type = obj.TYPE_REG
3774                 p.From.Reg = regnum(v.Args[0])
3775                 n := autoVar(v)
3776                 p.To.Type = obj.TYPE_MEM
3777                 p.To.Name = obj.NAME_AUTO
3778                 p.To.Node = n
3779                 p.To.Sym = Linksym(n.Sym)
3780         case ssa.OpPhi:
3781                 // just check to make sure regalloc and stackalloc did it right
3782                 if v.Type.IsMemory() {
3783                         return
3784                 }
3785                 f := v.Block.Func
3786                 loc := f.RegAlloc[v.ID]
3787                 for _, a := range v.Args {
3788                         if aloc := f.RegAlloc[a.ID]; aloc != loc { // TODO: .Equal() instead?
3789                                 v.Fatalf("phi arg at different location than phi: %v @ %v, but arg %v @ %v\n%s\n", v, loc, a, aloc, v.Block.Func)
3790                         }
3791                 }
3792         case ssa.OpConst8, ssa.OpConst16, ssa.OpConst32, ssa.OpConst64, ssa.OpConstString, ssa.OpConstNil, ssa.OpConstBool,
3793                 ssa.OpConst32F, ssa.OpConst64F:
3794                 if v.Block.Func.RegAlloc[v.ID] != nil {
3795                         v.Fatalf("const value %v shouldn't have a location", v)
3796                 }
3797
3798         case ssa.OpArg:
3799                 // memory arg needs no code
3800                 // TODO: check that only mem arg goes here.
3801         case ssa.OpAMD64LoweredPanicNilCheck:
3802                 if Debug_checknil != 0 && v.Line > 1 { // v.Line==1 in generated wrappers
3803                         Warnl(int(v.Line), "generated nil check")
3804                 }
3805                 // Write to memory address 0. It doesn't matter what we write; use AX.
3806                 // Input 0 is the pointer we just checked, use it as the destination.
3807                 r := regnum(v.Args[0])
3808                 q := Prog(x86.AMOVL)
3809                 q.From.Type = obj.TYPE_REG
3810                 q.From.Reg = x86.REG_AX
3811                 q.To.Type = obj.TYPE_MEM
3812                 q.To.Reg = r
3813         case ssa.OpAMD64LoweredGetClosurePtr:
3814                 // Output is hardwired to DX only,
3815                 // and DX contains the closure pointer on
3816                 // closure entry, and this "instruction"
3817                 // is scheduled to the very beginning
3818                 // of the entry block.
3819         case ssa.OpAMD64LoweredGetG:
3820                 r := regnum(v)
3821                 // See the comments in cmd/internal/obj/x86/obj6.go
3822                 // near CanUse1InsnTLS for a detailed explanation of these instructions.
3823                 if x86.CanUse1InsnTLS(Ctxt) {
3824                         // MOVQ (TLS), r
3825                         p := Prog(x86.AMOVQ)
3826                         p.From.Type = obj.TYPE_MEM
3827                         p.From.Reg = x86.REG_TLS
3828                         p.To.Type = obj.TYPE_REG
3829                         p.To.Reg = r
3830                 } else {
3831                         // MOVQ TLS, r
3832                         // MOVQ (r)(TLS*1), r
3833                         p := Prog(x86.AMOVQ)
3834                         p.From.Type = obj.TYPE_REG
3835                         p.From.Reg = x86.REG_TLS
3836                         p.To.Type = obj.TYPE_REG
3837                         p.To.Reg = r
3838                         q := Prog(x86.AMOVQ)
3839                         q.From.Type = obj.TYPE_MEM
3840                         q.From.Reg = r
3841                         q.From.Index = x86.REG_TLS
3842                         q.From.Scale = 1
3843                         q.To.Type = obj.TYPE_REG
3844                         q.To.Reg = r
3845                 }
3846         case ssa.OpAMD64CALLstatic:
3847                 p := Prog(obj.ACALL)
3848                 p.To.Type = obj.TYPE_MEM
3849                 p.To.Name = obj.NAME_EXTERN
3850                 p.To.Sym = Linksym(v.Aux.(*Sym))
3851                 if Maxarg < v.AuxInt {
3852                         Maxarg = v.AuxInt
3853                 }
3854         case ssa.OpAMD64CALLclosure:
3855                 p := Prog(obj.ACALL)
3856                 p.To.Type = obj.TYPE_REG
3857                 p.To.Reg = regnum(v.Args[0])
3858                 if Maxarg < v.AuxInt {
3859                         Maxarg = v.AuxInt
3860                 }
3861         case ssa.OpAMD64CALLdefer:
3862                 p := Prog(obj.ACALL)
3863                 p.To.Type = obj.TYPE_MEM
3864                 p.To.Name = obj.NAME_EXTERN
3865                 p.To.Sym = Linksym(Deferproc.Sym)
3866                 if Maxarg < v.AuxInt {
3867                         Maxarg = v.AuxInt
3868                 }
3869                 // defer returns in rax:
3870                 // 0 if we should continue executing
3871                 // 1 if we should jump to deferreturn call
3872                 p = Prog(x86.ATESTL)
3873                 p.From.Type = obj.TYPE_REG
3874                 p.From.Reg = x86.REG_AX
3875                 p.To.Type = obj.TYPE_REG
3876                 p.To.Reg = x86.REG_AX
3877                 p = Prog(x86.AJNE)
3878                 p.To.Type = obj.TYPE_BRANCH
3879                 s.deferBranches = append(s.deferBranches, p)
3880         case ssa.OpAMD64CALLgo:
3881                 p := Prog(obj.ACALL)
3882                 p.To.Type = obj.TYPE_MEM
3883                 p.To.Name = obj.NAME_EXTERN
3884                 p.To.Sym = Linksym(Newproc.Sym)
3885                 if Maxarg < v.AuxInt {
3886                         Maxarg = v.AuxInt
3887                 }
3888         case ssa.OpAMD64CALLinter:
3889                 p := Prog(obj.ACALL)
3890                 p.To.Type = obj.TYPE_REG
3891                 p.To.Reg = regnum(v.Args[0])
3892                 if Maxarg < v.AuxInt {
3893                         Maxarg = v.AuxInt
3894                 }
3895         case ssa.OpAMD64NEGQ, ssa.OpAMD64NEGL, ssa.OpAMD64NEGW, ssa.OpAMD64NEGB,
3896                 ssa.OpAMD64NOTQ, ssa.OpAMD64NOTL, ssa.OpAMD64NOTW, ssa.OpAMD64NOTB:
3897                 x := regnum(v.Args[0])
3898                 r := regnum(v)
3899                 if x != r {
3900                         p := Prog(regMoveAMD64(v.Type.Size()))
3901                         p.From.Type = obj.TYPE_REG
3902                         p.From.Reg = x
3903                         p.To.Type = obj.TYPE_REG
3904                         p.To.Reg = r
3905                 }
3906                 p := Prog(v.Op.Asm())
3907                 p.To.Type = obj.TYPE_REG
3908                 p.To.Reg = r
3909         case ssa.OpAMD64SQRTSD:
3910                 p := Prog(v.Op.Asm())
3911                 p.From.Type = obj.TYPE_REG
3912                 p.From.Reg = regnum(v.Args[0])
3913                 p.To.Type = obj.TYPE_REG
3914                 p.To.Reg = regnum(v)
3915         case ssa.OpSP, ssa.OpSB:
3916                 // nothing to do
3917         case ssa.OpAMD64SETEQ, ssa.OpAMD64SETNE,
3918                 ssa.OpAMD64SETL, ssa.OpAMD64SETLE,
3919                 ssa.OpAMD64SETG, ssa.OpAMD64SETGE,
3920                 ssa.OpAMD64SETGF, ssa.OpAMD64SETGEF,
3921                 ssa.OpAMD64SETB, ssa.OpAMD64SETBE,
3922                 ssa.OpAMD64SETORD, ssa.OpAMD64SETNAN,
3923                 ssa.OpAMD64SETA, ssa.OpAMD64SETAE:
3924                 p := Prog(v.Op.Asm())
3925                 p.To.Type = obj.TYPE_REG
3926                 p.To.Reg = regnum(v)
3927
3928         case ssa.OpAMD64SETNEF:
3929                 p := Prog(v.Op.Asm())
3930                 p.To.Type = obj.TYPE_REG
3931                 p.To.Reg = regnum(v)
3932                 q := Prog(x86.ASETPS)
3933                 q.To.Type = obj.TYPE_REG
3934                 q.To.Reg = x86.REG_AX
3935                 // TODO AORQ copied from old code generator, why not AORB?
3936                 opregreg(x86.AORQ, regnum(v), x86.REG_AX)
3937
3938         case ssa.OpAMD64SETEQF:
3939                 p := Prog(v.Op.Asm())
3940                 p.To.Type = obj.TYPE_REG
3941                 p.To.Reg = regnum(v)
3942                 q := Prog(x86.ASETPC)
3943                 q.To.Type = obj.TYPE_REG
3944                 q.To.Reg = x86.REG_AX
3945                 // TODO AANDQ copied from old code generator, why not AANDB?
3946                 opregreg(x86.AANDQ, regnum(v), x86.REG_AX)
3947
3948         case ssa.OpAMD64InvertFlags:
3949                 v.Fatalf("InvertFlags should never make it to codegen %v", v)
3950         case ssa.OpAMD64REPSTOSQ:
3951                 Prog(x86.AREP)
3952                 Prog(x86.ASTOSQ)
3953         case ssa.OpAMD64REPMOVSB:
3954                 Prog(x86.AREP)
3955                 Prog(x86.AMOVSB)
3956         case ssa.OpVarDef:
3957                 Gvardef(v.Aux.(*Node))
3958         case ssa.OpVarKill:
3959                 gvarkill(v.Aux.(*Node))
3960         default:
3961                 v.Unimplementedf("genValue not implemented: %s", v.LongString())
3962         }
3963 }
3964
3965 // movSizeByType returns the MOV instruction of the given type.
3966 func movSizeByType(t ssa.Type) (asm int) {
3967         // For x86, there's no difference between reg move opcodes
3968         // and memory move opcodes.
3969         asm = regMoveByTypeAMD64(t)
3970         return
3971 }
3972
3973 // movZero generates a register indirect move with a 0 immediate and keeps track of bytes left and next offset
3974 func movZero(as int, width int64, nbytes int64, offset int64, regnum int16) (nleft int64, noff int64) {
3975         p := Prog(as)
3976         // TODO: use zero register on archs that support it.
3977         p.From.Type = obj.TYPE_CONST
3978         p.From.Offset = 0
3979         p.To.Type = obj.TYPE_MEM
3980         p.To.Reg = regnum
3981         p.To.Offset = offset
3982         offset += width
3983         nleft = nbytes - width
3984         return nleft, offset
3985 }
3986
3987 var blockJump = [...]struct {
3988         asm, invasm int
3989 }{
3990         ssa.BlockAMD64EQ:  {x86.AJEQ, x86.AJNE},
3991         ssa.BlockAMD64NE:  {x86.AJNE, x86.AJEQ},
3992         ssa.BlockAMD64LT:  {x86.AJLT, x86.AJGE},
3993         ssa.BlockAMD64GE:  {x86.AJGE, x86.AJLT},
3994         ssa.BlockAMD64LE:  {x86.AJLE, x86.AJGT},
3995         ssa.BlockAMD64GT:  {x86.AJGT, x86.AJLE},
3996         ssa.BlockAMD64ULT: {x86.AJCS, x86.AJCC},
3997         ssa.BlockAMD64UGE: {x86.AJCC, x86.AJCS},
3998         ssa.BlockAMD64UGT: {x86.AJHI, x86.AJLS},
3999         ssa.BlockAMD64ULE: {x86.AJLS, x86.AJHI},
4000         ssa.BlockAMD64ORD: {x86.AJPC, x86.AJPS},
4001         ssa.BlockAMD64NAN: {x86.AJPS, x86.AJPC},
4002 }
4003
4004 type floatingEQNEJump struct {
4005         jump, index int
4006 }
4007
4008 var eqfJumps = [2][2]floatingEQNEJump{
4009         {{x86.AJNE, 1}, {x86.AJPS, 1}}, // next == b.Succs[0]
4010         {{x86.AJNE, 1}, {x86.AJPC, 0}}, // next == b.Succs[1]
4011 }
4012 var nefJumps = [2][2]floatingEQNEJump{
4013         {{x86.AJNE, 0}, {x86.AJPC, 1}}, // next == b.Succs[0]
4014         {{x86.AJNE, 0}, {x86.AJPS, 0}}, // next == b.Succs[1]
4015 }
4016
4017 func oneFPJump(b *ssa.Block, jumps *floatingEQNEJump, likely ssa.BranchPrediction, branches []branch) []branch {
4018         p := Prog(jumps.jump)
4019         p.To.Type = obj.TYPE_BRANCH
4020         to := jumps.index
4021         branches = append(branches, branch{p, b.Succs[to]})
4022         if to == 1 {
4023                 likely = -likely
4024         }
4025         // liblink reorders the instruction stream as it sees fit.
4026         // Pass along what we know so liblink can make use of it.
4027         // TODO: Once we've fully switched to SSA,
4028         // make liblink leave our output alone.
4029         switch likely {
4030         case ssa.BranchUnlikely:
4031                 p.From.Type = obj.TYPE_CONST
4032                 p.From.Offset = 0
4033         case ssa.BranchLikely:
4034                 p.From.Type = obj.TYPE_CONST
4035                 p.From.Offset = 1
4036         }
4037         return branches
4038 }
4039
4040 func genFPJump(s *genState, b, next *ssa.Block, jumps *[2][2]floatingEQNEJump) {
4041         likely := b.Likely
4042         switch next {
4043         case b.Succs[0]:
4044                 s.branches = oneFPJump(b, &jumps[0][0], likely, s.branches)
4045                 s.branches = oneFPJump(b, &jumps[0][1], likely, s.branches)
4046         case b.Succs[1]:
4047                 s.branches = oneFPJump(b, &jumps[1][0], likely, s.branches)
4048                 s.branches = oneFPJump(b, &jumps[1][1], likely, s.branches)
4049         default:
4050                 s.branches = oneFPJump(b, &jumps[1][0], likely, s.branches)
4051                 s.branches = oneFPJump(b, &jumps[1][1], likely, s.branches)
4052                 q := Prog(obj.AJMP)
4053                 q.To.Type = obj.TYPE_BRANCH
4054                 s.branches = append(s.branches, branch{q, b.Succs[1]})
4055         }
4056 }
4057
4058 func (s *genState) genBlock(b, next *ssa.Block) {
4059         lineno = b.Line
4060
4061         switch b.Kind {
4062         case ssa.BlockPlain, ssa.BlockCall:
4063                 if b.Succs[0] != next {
4064                         p := Prog(obj.AJMP)
4065                         p.To.Type = obj.TYPE_BRANCH
4066                         s.branches = append(s.branches, branch{p, b.Succs[0]})
4067                 }
4068         case ssa.BlockExit:
4069                 Prog(obj.AUNDEF) // tell plive.go that we never reach here
4070         case ssa.BlockRet:
4071                 if hasdefer {
4072                         s.deferReturn()
4073                 }
4074                 Prog(obj.ARET)
4075         case ssa.BlockRetJmp:
4076                 p := Prog(obj.AJMP)
4077                 p.To.Type = obj.TYPE_MEM
4078                 p.To.Name = obj.NAME_EXTERN
4079                 p.To.Sym = Linksym(b.Aux.(*Sym))
4080
4081         case ssa.BlockAMD64EQF:
4082                 genFPJump(s, b, next, &eqfJumps)
4083
4084         case ssa.BlockAMD64NEF:
4085                 genFPJump(s, b, next, &nefJumps)
4086
4087         case ssa.BlockAMD64EQ, ssa.BlockAMD64NE,
4088                 ssa.BlockAMD64LT, ssa.BlockAMD64GE,
4089                 ssa.BlockAMD64LE, ssa.BlockAMD64GT,
4090                 ssa.BlockAMD64ULT, ssa.BlockAMD64UGT,
4091                 ssa.BlockAMD64ULE, ssa.BlockAMD64UGE:
4092                 jmp := blockJump[b.Kind]
4093                 likely := b.Likely
4094                 var p *obj.Prog
4095                 switch next {
4096                 case b.Succs[0]:
4097                         p = Prog(jmp.invasm)
4098                         likely *= -1
4099                         p.To.Type = obj.TYPE_BRANCH
4100                         s.branches = append(s.branches, branch{p, b.Succs[1]})
4101                 case b.Succs[1]:
4102                         p = Prog(jmp.asm)
4103                         p.To.Type = obj.TYPE_BRANCH
4104                         s.branches = append(s.branches, branch{p, b.Succs[0]})
4105                 default:
4106                         p = Prog(jmp.asm)
4107                         p.To.Type = obj.TYPE_BRANCH
4108                         s.branches = append(s.branches, branch{p, b.Succs[0]})
4109                         q := Prog(obj.AJMP)
4110                         q.To.Type = obj.TYPE_BRANCH
4111                         s.branches = append(s.branches, branch{q, b.Succs[1]})
4112                 }
4113
4114                 // liblink reorders the instruction stream as it sees fit.
4115                 // Pass along what we know so liblink can make use of it.
4116                 // TODO: Once we've fully switched to SSA,
4117                 // make liblink leave our output alone.
4118                 switch likely {
4119                 case ssa.BranchUnlikely:
4120                         p.From.Type = obj.TYPE_CONST
4121                         p.From.Offset = 0
4122                 case ssa.BranchLikely:
4123                         p.From.Type = obj.TYPE_CONST
4124                         p.From.Offset = 1
4125                 }
4126
4127         default:
4128                 b.Unimplementedf("branch not implemented: %s. Control: %s", b.LongString(), b.Control.LongString())
4129         }
4130 }
4131
4132 func (s *genState) deferReturn() {
4133         // Deferred calls will appear to be returning to
4134         // the CALL deferreturn(SB) that we are about to emit.
4135         // However, the stack trace code will show the line
4136         // of the instruction byte before the return PC.
4137         // To avoid that being an unrelated instruction,
4138         // insert an actual hardware NOP that will have the right line number.
4139         // This is different from obj.ANOP, which is a virtual no-op
4140         // that doesn't make it into the instruction stream.
4141         s.deferTarget = Pc
4142         Thearch.Ginsnop()
4143         p := Prog(obj.ACALL)
4144         p.To.Type = obj.TYPE_MEM
4145         p.To.Name = obj.NAME_EXTERN
4146         p.To.Sym = Linksym(Deferreturn.Sym)
4147 }
4148
4149 // addAux adds the offset in the aux fields (AuxInt and Aux) of v to a.
4150 func addAux(a *obj.Addr, v *ssa.Value) {
4151         if a.Type != obj.TYPE_MEM {
4152                 v.Fatalf("bad addAux addr %s", a)
4153         }
4154         // add integer offset
4155         a.Offset += v.AuxInt
4156
4157         // If no additional symbol offset, we're done.
4158         if v.Aux == nil {
4159                 return
4160         }
4161         // Add symbol's offset from its base register.
4162         switch sym := v.Aux.(type) {
4163         case *ssa.ExternSymbol:
4164                 a.Name = obj.NAME_EXTERN
4165                 a.Sym = Linksym(sym.Sym.(*Sym))
4166         case *ssa.ArgSymbol:
4167                 n := sym.Node.(*Node)
4168                 a.Name = obj.NAME_PARAM
4169                 a.Node = n
4170                 a.Sym = Linksym(n.Orig.Sym)
4171                 a.Offset += n.Xoffset // TODO: why do I have to add this here?  I don't for auto variables.
4172         case *ssa.AutoSymbol:
4173                 n := sym.Node.(*Node)
4174                 a.Name = obj.NAME_AUTO
4175                 a.Node = n
4176                 a.Sym = Linksym(n.Sym)
4177         default:
4178                 v.Fatalf("aux in %s not implemented %#v", v, v.Aux)
4179         }
4180 }
4181
4182 // extendIndex extends v to a full pointer width.
4183 func (s *state) extendIndex(v *ssa.Value) *ssa.Value {
4184         size := v.Type.Size()
4185         if size == s.config.PtrSize {
4186                 return v
4187         }
4188         if size > s.config.PtrSize {
4189                 // TODO: truncate 64-bit indexes on 32-bit pointer archs.  We'd need to test
4190                 // the high word and branch to out-of-bounds failure if it is not 0.
4191                 s.Unimplementedf("64->32 index truncation not implemented")
4192                 return v
4193         }
4194
4195         // Extend value to the required size
4196         var op ssa.Op
4197         if v.Type.IsSigned() {
4198                 switch 10*size + s.config.PtrSize {
4199                 case 14:
4200                         op = ssa.OpSignExt8to32
4201                 case 18:
4202                         op = ssa.OpSignExt8to64
4203                 case 24:
4204                         op = ssa.OpSignExt16to32
4205                 case 28:
4206                         op = ssa.OpSignExt16to64
4207                 case 48:
4208                         op = ssa.OpSignExt32to64
4209                 default:
4210                         s.Fatalf("bad signed index extension %s", v.Type)
4211                 }
4212         } else {
4213                 switch 10*size + s.config.PtrSize {
4214                 case 14:
4215                         op = ssa.OpZeroExt8to32
4216                 case 18:
4217                         op = ssa.OpZeroExt8to64
4218                 case 24:
4219                         op = ssa.OpZeroExt16to32
4220                 case 28:
4221                         op = ssa.OpZeroExt16to64
4222                 case 48:
4223                         op = ssa.OpZeroExt32to64
4224                 default:
4225                         s.Fatalf("bad unsigned index extension %s", v.Type)
4226                 }
4227         }
4228         return s.newValue1(op, Types[TUINTPTR], v)
4229 }
4230
4231 // ssaRegToReg maps ssa register numbers to obj register numbers.
4232 var ssaRegToReg = [...]int16{
4233         x86.REG_AX,
4234         x86.REG_CX,
4235         x86.REG_DX,
4236         x86.REG_BX,
4237         x86.REG_SP,
4238         x86.REG_BP,
4239         x86.REG_SI,
4240         x86.REG_DI,
4241         x86.REG_R8,
4242         x86.REG_R9,
4243         x86.REG_R10,
4244         x86.REG_R11,
4245         x86.REG_R12,
4246         x86.REG_R13,
4247         x86.REG_R14,
4248         x86.REG_R15,
4249         x86.REG_X0,
4250         x86.REG_X1,
4251         x86.REG_X2,
4252         x86.REG_X3,
4253         x86.REG_X4,
4254         x86.REG_X5,
4255         x86.REG_X6,
4256         x86.REG_X7,
4257         x86.REG_X8,
4258         x86.REG_X9,
4259         x86.REG_X10,
4260         x86.REG_X11,
4261         x86.REG_X12,
4262         x86.REG_X13,
4263         x86.REG_X14,
4264         x86.REG_X15,
4265         0, // SB isn't a real register.  We fill an Addr.Reg field with 0 in this case.
4266         // TODO: arch-dependent
4267 }
4268
4269 // regMoveAMD64 returns the register->register move opcode for the given width.
4270 // TODO: generalize for all architectures?
4271 func regMoveAMD64(width int64) int {
4272         switch width {
4273         case 1:
4274                 return x86.AMOVB
4275         case 2:
4276                 return x86.AMOVW
4277         case 4:
4278                 return x86.AMOVL
4279         case 8:
4280                 return x86.AMOVQ
4281         default:
4282                 panic("bad int register width")
4283         }
4284 }
4285
4286 func regMoveByTypeAMD64(t ssa.Type) int {
4287         width := t.Size()
4288         if t.IsFloat() {
4289                 switch width {
4290                 case 4:
4291                         return x86.AMOVSS
4292                 case 8:
4293                         return x86.AMOVSD
4294                 default:
4295                         panic("bad float register width")
4296                 }
4297         } else {
4298                 switch width {
4299                 case 1:
4300                         return x86.AMOVB
4301                 case 2:
4302                         return x86.AMOVW
4303                 case 4:
4304                         return x86.AMOVL
4305                 case 8:
4306                         return x86.AMOVQ
4307                 default:
4308                         panic("bad int register width")
4309                 }
4310         }
4311
4312         panic("bad register type")
4313 }
4314
4315 // regnum returns the register (in cmd/internal/obj numbering) to
4316 // which v has been allocated.  Panics if v is not assigned to a
4317 // register.
4318 // TODO: Make this panic again once it stops happening routinely.
4319 func regnum(v *ssa.Value) int16 {
4320         reg := v.Block.Func.RegAlloc[v.ID]
4321         if reg == nil {
4322                 v.Unimplementedf("nil regnum for value: %s\n%s\n", v.LongString(), v.Block.Func)
4323                 return 0
4324         }
4325         return ssaRegToReg[reg.(*ssa.Register).Num]
4326 }
4327
4328 // autoVar returns a *Node representing the auto variable assigned to v.
4329 func autoVar(v *ssa.Value) *Node {
4330         return v.Block.Func.RegAlloc[v.ID].(*ssa.LocalSlot).N.(*Node)
4331 }
4332
4333 // ssaExport exports a bunch of compiler services for the ssa backend.
4334 type ssaExport struct {
4335         log           bool
4336         unimplemented bool
4337         mustImplement bool
4338 }
4339
4340 func (s *ssaExport) TypeBool() ssa.Type    { return Types[TBOOL] }
4341 func (s *ssaExport) TypeInt8() ssa.Type    { return Types[TINT8] }
4342 func (s *ssaExport) TypeInt16() ssa.Type   { return Types[TINT16] }
4343 func (s *ssaExport) TypeInt32() ssa.Type   { return Types[TINT32] }
4344 func (s *ssaExport) TypeInt64() ssa.Type   { return Types[TINT64] }
4345 func (s *ssaExport) TypeUInt8() ssa.Type   { return Types[TUINT8] }
4346 func (s *ssaExport) TypeUInt16() ssa.Type  { return Types[TUINT16] }
4347 func (s *ssaExport) TypeUInt32() ssa.Type  { return Types[TUINT32] }
4348 func (s *ssaExport) TypeUInt64() ssa.Type  { return Types[TUINT64] }
4349 func (s *ssaExport) TypeFloat32() ssa.Type { return Types[TFLOAT32] }
4350 func (s *ssaExport) TypeFloat64() ssa.Type { return Types[TFLOAT64] }
4351 func (s *ssaExport) TypeInt() ssa.Type     { return Types[TINT] }
4352 func (s *ssaExport) TypeUintptr() ssa.Type { return Types[TUINTPTR] }
4353 func (s *ssaExport) TypeString() ssa.Type  { return Types[TSTRING] }
4354 func (s *ssaExport) TypeBytePtr() ssa.Type { return Ptrto(Types[TUINT8]) }
4355
4356 // StringData returns a symbol (a *Sym wrapped in an interface) which
4357 // is the data component of a global string constant containing s.
4358 func (*ssaExport) StringData(s string) interface{} {
4359         // TODO: is idealstring correct?  It might not matter...
4360         _, data := stringsym(s)
4361         return &ssa.ExternSymbol{Typ: idealstring, Sym: data}
4362 }
4363
4364 func (e *ssaExport) Auto(t ssa.Type) fmt.Stringer {
4365         n := temp(t.(*Type))   // Note: adds new auto to Curfn.Func.Dcl list
4366         e.mustImplement = true // This modifies the input to SSA, so we want to make sure we succeed from here!
4367         return n
4368 }
4369
4370 func (e ssaExport) CanSSA(t ssa.Type) bool {
4371         return canSSAType(t.(*Type))
4372 }
4373
4374 // Log logs a message from the compiler.
4375 func (e *ssaExport) Logf(msg string, args ...interface{}) {
4376         // If e was marked as unimplemented, anything could happen. Ignore.
4377         if e.log && !e.unimplemented {
4378                 fmt.Printf(msg, args...)
4379         }
4380 }
4381
4382 // Fatal reports a compiler error and exits.
4383 func (e *ssaExport) Fatalf(msg string, args ...interface{}) {
4384         // If e was marked as unimplemented, anything could happen. Ignore.
4385         if !e.unimplemented {
4386                 Fatalf(msg, args...)
4387         }
4388 }
4389
4390 // Unimplemented reports that the function cannot be compiled.
4391 // It will be removed once SSA work is complete.
4392 func (e *ssaExport) Unimplementedf(msg string, args ...interface{}) {
4393         if e.mustImplement {
4394                 Fatalf(msg, args...)
4395         }
4396         const alwaysLog = false // enable to calculate top unimplemented features
4397         if !e.unimplemented && (e.log || alwaysLog) {
4398                 // first implementation failure, print explanation
4399                 fmt.Printf("SSA unimplemented: "+msg+"\n", args...)
4400         }
4401         e.unimplemented = true
4402 }