src/cmd/compile/internal/gc/sinit.go

   1 // Copyright 2009 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 "fmt"
   8
   9 // static initialization
  10 const (
  11         InitNotStarted = 0
  12         InitDone       = 1
  13         InitPending    = 2
  14 )
  15
  16 type InitEntry struct {
  17         Xoffset int64 // struct, array only
  18         Expr    *Node // bytes of run-time computed expressions
  19 }
  20
  21 type InitPlan struct {
  22         E []InitEntry
  23 }
  24
  25 var (
  26         initlist  []*Node
  27         initplans map[*Node]*InitPlan
  28         inittemps = make(map[*Node]*Node)
  29 )
  30
  31 // init1 walks the AST starting at n, and accumulates in out
  32 // the list of definitions needing init code in dependency order.
  33 func init1(n *Node, out *[]*Node) {
  34         if n == nil {
  35                 return
  36         }
  37         init1(n.Left, out)
  38         init1(n.Right, out)
  39         for _, n1 := range n.List.Slice() {
  40                 init1(n1, out)
  41         }
  42
  43         if n.Left != nil && n.Type != nil && n.Left.Op == OTYPE && n.Class == PFUNC {
  44                 // Methods called as Type.Method(receiver, ...).
  45                 // Definitions for method expressions are stored in type->nname.
  46                 init1(n.Type.Nname(), out)
  47         }
  48
  49         if n.Op != ONAME {
  50                 return
  51         }
  52         switch n.Class {
  53         case PEXTERN, PFUNC:
  54         default:
  55                 if isblank(n) && n.Name.Curfn == nil && n.Name.Defn != nil && n.Name.Defn.Initorder == InitNotStarted {
  56                         // blank names initialization is part of init() but not
  57                         // when they are inside a function.
  58                         break
  59                 }
  60                 return
  61         }
  62
  63         if n.Initorder == InitDone {
  64                 return
  65         }
  66         if n.Initorder == InitPending {
  67                 // Since mutually recursive sets of functions are allowed,
  68                 // we don't necessarily raise an error if n depends on a node
  69                 // which is already waiting for its dependencies to be visited.
  70                 //
  71                 // initlist contains a cycle of identifiers referring to each other.
  72                 // If this cycle contains a variable, then this variable refers to itself.
  73                 // Conversely, if there exists an initialization cycle involving
  74                 // a variable in the program, the tree walk will reach a cycle
  75                 // involving that variable.
  76                 if n.Class != PFUNC {
  77                         foundinitloop(n, n)
  78                 }
  79
  80                 for i := len(initlist) - 1; i >= 0; i-- {
  81                         x := initlist[i]
  82                         if x == n {
  83                                 break
  84                         }
  85                         if x.Class != PFUNC {
  86                                 foundinitloop(n, x)
  87                         }
  88                 }
  89
  90                 // The loop involves only functions, ok.
  91                 return
  92         }
  93
  94         // reached a new unvisited node.
  95         n.Initorder = InitPending
  96         initlist = append(initlist, n)
  97
  98         // make sure that everything n depends on is initialized.
  99         // n->defn is an assignment to n
 100         if defn := n.Name.Defn; defn != nil {
 101                 switch defn.Op {
 102                 default:
 103                         Dump("defn", defn)
 104                         Fatalf("init1: bad defn")
 105
 106                 case ODCLFUNC:
 107                         init2list(defn.Nbody, out)
 108
 109                 case OAS:
 110                         if defn.Left != n {
 111                                 Dump("defn", defn)
 112                                 Fatalf("init1: bad defn")
 113                         }
 114                         if isblank(defn.Left) && candiscard(defn.Right) {
 115                                 defn.Op = OEMPTY
 116                                 defn.Left = nil
 117                                 defn.Right = nil
 118                                 break
 119                         }
 120
 121                         init2(defn.Right, out)
 122                         if Debug['j'] != 0 {
 123                                 fmt.Printf("%v\n", n.Sym)
 124                         }
 125                         if isblank(n) || !staticinit(n, out) {
 126                                 if Debug['%'] != 0 {
 127                                         Dump("nonstatic", defn)
 128                                 }
 129                                 *out = append(*out, defn)
 130                         }
 131
 132                 case OAS2FUNC, OAS2MAPR, OAS2DOTTYPE, OAS2RECV:
 133                         if defn.Initorder == InitDone {
 134                                 break
 135                         }
 136                         defn.Initorder = InitPending
 137                         for _, n2 := range defn.Rlist.Slice() {
 138                                 init1(n2, out)
 139                         }
 140                         if Debug['%'] != 0 {
 141                                 Dump("nonstatic", defn)
 142                         }
 143                         *out = append(*out, defn)
 144                         defn.Initorder = InitDone
 145                 }
 146         }
 147
 148         last := len(initlist) - 1
 149         if initlist[last] != n {
 150                 Fatalf("bad initlist %v", initlist)
 151         }
 152         initlist[last] = nil // allow GC
 153         initlist = initlist[:last]
 154
 155         n.Initorder = InitDone
 156         return
 157 }
 158
 159 // foundinitloop prints an init loop error and exits.
 160 func foundinitloop(node, visited *Node) {
 161         // If there have already been errors printed,
 162         // those errors probably confused us and
 163         // there might not be a loop. Let the user
 164         // fix those first.
 165         flusherrors()
 166         if nerrors > 0 {
 167                 errorexit()
 168         }
 169
 170         // Find the index of node and visited in the initlist.
 171         var nodeindex, visitedindex int
 172         for ; initlist[nodeindex] != node; nodeindex++ {
 173         }
 174         for ; initlist[visitedindex] != visited; visitedindex++ {
 175         }
 176
 177         // There is a loop involving visited. We know about node and
 178         // initlist = n1 <- ... <- visited <- ... <- node <- ...
 179         fmt.Printf("%v: initialization loop:\n", visited.Line())
 180
 181         // Print visited -> ... -> n1 -> node.
 182         for _, n := range initlist[visitedindex:] {
 183                 fmt.Printf("\t%v %v refers to\n", n.Line(), n.Sym)
 184         }
 185
 186         // Print node -> ... -> visited.
 187         for _, n := range initlist[nodeindex:visitedindex] {
 188                 fmt.Printf("\t%v %v refers to\n", n.Line(), n.Sym)
 189         }
 190
 191         fmt.Printf("\t%v %v\n", visited.Line(), visited.Sym)
 192         errorexit()
 193 }
 194
 195 // recurse over n, doing init1 everywhere.
 196 func init2(n *Node, out *[]*Node) {
 197         if n == nil || n.Initorder == InitDone {
 198                 return
 199         }
 200
 201         if n.Op == ONAME && n.Ninit.Len() != 0 {
 202                 Fatalf("name %v with ninit: %+v\n", n.Sym, n)
 203         }
 204
 205         init1(n, out)
 206         init2(n.Left, out)
 207         init2(n.Right, out)
 208         init2list(n.Ninit, out)
 209         init2list(n.List, out)
 210         init2list(n.Rlist, out)
 211         init2list(n.Nbody, out)
 212
 213         if n.Op == OCLOSURE {
 214                 init2list(n.Func.Closure.Nbody, out)
 215         }
 216         if n.Op == ODOTMETH || n.Op == OCALLPART {
 217                 init2(n.Type.Nname(), out)
 218         }
 219 }
 220
 221 func init2list(l Nodes, out *[]*Node) {
 222         for _, n := range l.Slice() {
 223                 init2(n, out)
 224         }
 225 }
 226
 227 func initreorder(l []*Node, out *[]*Node) {
 228         var n *Node
 229         for _, n = range l {
 230                 switch n.Op {
 231                 case ODCLFUNC, ODCLCONST, ODCLTYPE:
 232                         continue
 233                 }
 234
 235                 initreorder(n.Ninit.Slice(), out)
 236                 n.Ninit.Set(nil)
 237                 init1(n, out)
 238         }
 239 }
 240
 241 // initfix computes initialization order for a list l of top-level
 242 // declarations and outputs the corresponding list of statements
 243 // to include in the init() function body.
 244 func initfix(l []*Node) []*Node {
 245         var lout []*Node
 246         initplans = make(map[*Node]*InitPlan)
 247         lno := lineno
 248         initreorder(l, &lout)
 249         lineno = lno
 250         initplans = nil
 251         return lout
 252 }
 253
 254 // compilation of top-level (static) assignments
 255 // into DATA statements if at all possible.
 256 func staticinit(n *Node, out *[]*Node) bool {
 257         if n.Op != ONAME || n.Class != PEXTERN || n.Name.Defn == nil || n.Name.Defn.Op != OAS {
 258                 Fatalf("staticinit")
 259         }
 260
 261         lineno = n.Pos
 262         l := n.Name.Defn.Left
 263         r := n.Name.Defn.Right
 264         return staticassign(l, r, out)
 265 }
 266
 267 // like staticassign but we are copying an already
 268 // initialized value r.
 269 func staticcopy(l *Node, r *Node, out *[]*Node) bool {
 270         if r.Op != ONAME {
 271                 return false
 272         }
 273         if r.Class == PFUNC {
 274                 gdata(l, r, Widthptr)
 275                 return true
 276         }
 277         if r.Class != PEXTERN || r.Sym.Pkg != localpkg {
 278                 return false
 279         }
 280         if r.Name.Defn == nil { // probably zeroed but perhaps supplied externally and of unknown value
 281                 return false
 282         }
 283         if r.Name.Defn.Op != OAS {
 284                 return false
 285         }
 286         orig := r
 287         r = r.Name.Defn.Right
 288
 289         for r.Op == OCONVNOP && !eqtype(r.Type, l.Type) {
 290                 r = r.Left
 291         }
 292
 293         switch r.Op {
 294         case ONAME:
 295                 if staticcopy(l, r, out) {
 296                         return true
 297                 }
 298                 // We may have skipped past one or more OCONVNOPs, so
 299                 // use conv to ensure r is assignable to l (#13263).
 300                 *out = append(*out, nod(OAS, l, conv(r, l.Type)))
 301                 return true
 302
 303         case OLITERAL:
 304                 if iszero(r) {
 305                         return true
 306                 }
 307                 gdata(l, r, int(l.Type.Width))
 308                 return true
 309
 310         case OADDR:
 311                 switch r.Left.Op {
 312                 case ONAME:
 313                         gdata(l, r, int(l.Type.Width))
 314                         return true
 315                 }
 316
 317         case OPTRLIT:
 318                 switch r.Left.Op {
 319                 case OARRAYLIT, OSLICELIT, OSTRUCTLIT, OMAPLIT:
 320                         // copy pointer
 321                         gdata(l, nod(OADDR, inittemps[r], nil), int(l.Type.Width))
 322                         return true
 323                 }
 324
 325         case OSLICELIT:
 326                 // copy slice
 327                 a := inittemps[r]
 328
 329                 n := *l
 330                 n.Xoffset = l.Xoffset + int64(array_array)
 331                 gdata(&n, nod(OADDR, a, nil), Widthptr)
 332                 n.Xoffset = l.Xoffset + int64(array_nel)
 333                 gdata(&n, r.Right, Widthint)
 334                 n.Xoffset = l.Xoffset + int64(array_cap)
 335                 gdata(&n, r.Right, Widthint)
 336                 return true
 337
 338         case OARRAYLIT, OSTRUCTLIT:
 339                 p := initplans[r]
 340
 341                 n := *l
 342                 for i := range p.E {
 343                         e := &p.E[i]
 344                         n.Xoffset = l.Xoffset + e.Xoffset
 345                         n.Type = e.Expr.Type
 346                         if e.Expr.Op == OLITERAL {
 347                                 gdata(&n, e.Expr, int(n.Type.Width))
 348                         } else {
 349                                 ll := nod(OXXX, nil, nil)
 350                                 *ll = n
 351                                 ll.Orig = ll // completely separate copy
 352                                 if !staticassign(ll, e.Expr, out) {
 353                                         // Requires computation, but we're
 354                                         // copying someone else's computation.
 355                                         rr := nod(OXXX, nil, nil)
 356
 357                                         *rr = *orig
 358                                         rr.Orig = rr // completely separate copy
 359                                         rr.Type = ll.Type
 360                                         rr.Xoffset += e.Xoffset
 361                                         setlineno(rr)
 362                                         *out = append(*out, nod(OAS, ll, rr))
 363                                 }
 364                         }
 365                 }
 366
 367                 return true
 368         }
 369
 370         return false
 371 }
 372
 373 func staticassign(l *Node, r *Node, out *[]*Node) bool {
 374         for r.Op == OCONVNOP {
 375                 r = r.Left
 376         }
 377
 378         switch r.Op {
 379         case ONAME:
 380                 return staticcopy(l, r, out)
 381
 382         case OLITERAL:
 383                 if iszero(r) {
 384                         return true
 385                 }
 386                 gdata(l, r, int(l.Type.Width))
 387                 return true
 388
 389         case OADDR:
 390                 var nam Node
 391                 if stataddr(&nam, r.Left) {
 392                         n := *r
 393                         n.Left = &nam
 394                         gdata(l, &n, int(l.Type.Width))
 395                         return true
 396                 }
 397                 fallthrough
 398
 399         case OPTRLIT:
 400                 switch r.Left.Op {
 401                 case OARRAYLIT, OSLICELIT, OMAPLIT, OSTRUCTLIT:
 402                         // Init pointer.
 403                         a := staticname(r.Left.Type)
 404
 405                         inittemps[r] = a
 406                         gdata(l, nod(OADDR, a, nil), int(l.Type.Width))
 407
 408                         // Init underlying literal.
 409                         if !staticassign(a, r.Left, out) {
 410                                 *out = append(*out, nod(OAS, a, r.Left))
 411                         }
 412                         return true
 413                 }
 414                 //dump("not static ptrlit", r);
 415
 416         case OSTRARRAYBYTE:
 417                 if l.Class == PEXTERN && r.Left.Op == OLITERAL {
 418                         sval := r.Left.Val().U.(string)
 419                         slicebytes(l, sval, len(sval))
 420                         return true
 421                 }
 422
 423         case OSLICELIT:
 424                 initplan(r)
 425                 // Init slice.
 426                 bound := r.Right.Int64()
 427                 ta := typArray(r.Type.Elem(), bound)
 428                 a := staticname(ta)
 429                 inittemps[r] = a
 430                 n := *l
 431                 n.Xoffset = l.Xoffset + int64(array_array)
 432                 gdata(&n, nod(OADDR, a, nil), Widthptr)
 433                 n.Xoffset = l.Xoffset + int64(array_nel)
 434                 gdata(&n, r.Right, Widthint)
 435                 n.Xoffset = l.Xoffset + int64(array_cap)
 436                 gdata(&n, r.Right, Widthint)
 437
 438                 // Fall through to init underlying array.
 439                 l = a
 440                 fallthrough
 441
 442         case OARRAYLIT, OSTRUCTLIT:
 443                 initplan(r)
 444
 445                 p := initplans[r]
 446                 n := *l
 447                 for i := range p.E {
 448                         e := &p.E[i]
 449                         n.Xoffset = l.Xoffset + e.Xoffset
 450                         n.Type = e.Expr.Type
 451                         if e.Expr.Op == OLITERAL {
 452                                 gdata(&n, e.Expr, int(n.Type.Width))
 453                         } else {
 454                                 setlineno(e.Expr)
 455                                 a := nod(OXXX, nil, nil)
 456                                 *a = n
 457                                 a.Orig = a // completely separate copy
 458                                 if !staticassign(a, e.Expr, out) {
 459                                         *out = append(*out, nod(OAS, a, e.Expr))
 460                                 }
 461                         }
 462                 }
 463
 464                 return true
 465
 466         case OMAPLIT:
 467                 break
 468
 469         case OCLOSURE:
 470                 if hasemptycvars(r) {
 471                         if Debug_closure > 0 {
 472                                 Warnl(r.Pos, "closure converted to global")
 473                         }
 474                         // Closures with no captured variables are globals,
 475                         // so the assignment can be done at link time.
 476                         n := *l
 477                         gdata(&n, r.Func.Closure.Func.Nname, Widthptr)
 478                         return true
 479                 } else {
 480                         closuredebugruntimecheck(r)
 481                 }
 482
 483         case OCONVIFACE:
 484                 // This logic is mirrored in isStaticCompositeLiteral.
 485                 // If you change something here, change it there, and vice versa.
 486
 487                 // Determine the underlying concrete type and value we are converting from.
 488                 val := r
 489                 for val.Op == OCONVIFACE {
 490                         val = val.Left
 491                 }
 492                 if val.Type.IsInterface() {
 493                         // val is an interface type.
 494                         // If val is nil, we can statically initialize l;
 495                         // both words are zero and so there no work to do, so report success.
 496                         // If val is non-nil, we have no concrete type to record,
 497                         // and we won't be able to statically initialize its value, so report failure.
 498                         return Isconst(val, CTNIL)
 499                 }
 500
 501                 var itab *Node
 502                 if l.Type.IsEmptyInterface() {
 503                         itab = typename(val.Type)
 504                 } else {
 505                         itab = itabname(val.Type, l.Type)
 506                 }
 507
 508                 // Create a copy of l to modify while we emit data.
 509                 n := *l
 510
 511                 // Emit itab, advance offset.
 512                 gdata(&n, itab, Widthptr)
 513                 n.Xoffset += int64(Widthptr)
 514
 515                 // Emit data.
 516                 if isdirectiface(val.Type) {
 517                         if Isconst(val, CTNIL) {
 518                                 // Nil is zero, nothing to do.
 519                                 return true
 520                         }
 521                         // Copy val directly into n.
 522                         n.Type = val.Type
 523                         setlineno(val)
 524                         a := nod(OXXX, nil, nil)
 525                         *a = n
 526                         a.Orig = a
 527                         if !staticassign(a, val, out) {
 528                                 *out = append(*out, nod(OAS, a, val))
 529                         }
 530                 } else {
 531                         // Construct temp to hold val, write pointer to temp into n.
 532                         a := staticname(val.Type)
 533                         inittemps[val] = a
 534                         if !staticassign(a, val, out) {
 535                                 *out = append(*out, nod(OAS, a, val))
 536                         }
 537                         ptr := nod(OADDR, a, nil)
 538                         n.Type = ptrto(val.Type)
 539                         gdata(&n, ptr, Widthptr)
 540                 }
 541
 542                 return true
 543         }
 544
 545         //dump("not static", r);
 546         return false
 547 }
 548
 549 // initContext is the context in which static data is populated.
 550 // It is either in an init function or in any other function.
 551 // Static data populated in an init function will be written either
 552 // zero times (as a readonly, static data symbol) or
 553 // one time (during init function execution).
 554 // Either way, there is no opportunity for races or further modification,
 555 // so the data can be written to a (possibly readonly) data symbol.
 556 // Static data populated in any other function needs to be local to
 557 // that function to allow multiple instances of that function
 558 // to execute concurrently without clobbering each others' data.
 559 type initContext uint8
 560
 561 const (
 562         inInitFunction initContext = iota
 563         inNonInitFunction
 564 )
 565
 566 // from here down is the walk analysis
 567 // of composite literals.
 568 // most of the work is to generate
 569 // data statements for the constant
 570 // part of the composite literal.
 571
 572 // staticname returns a name backed by a static data symbol.
 573 // Callers should set n.Name.Readonly = true on the
 574 // returned node for readonly nodes.
 575 func staticname(t *Type) *Node {
 576         n := newname(lookupN("statictmp_", statuniqgen))
 577         statuniqgen++
 578         addvar(n, t, PEXTERN)
 579         return n
 580 }
 581
 582 func isliteral(n *Node) bool {
 583         // Treat nils as zeros rather than literals.
 584         return n.Op == OLITERAL && n.Val().Ctype() != CTNIL
 585 }
 586
 587 func (n *Node) isSimpleName() bool {
 588         return n.Op == ONAME && n.Addable && n.Class != PAUTOHEAP
 589 }
 590
 591 func litas(l *Node, r *Node, init *Nodes) {
 592         a := nod(OAS, l, r)
 593         a = typecheck(a, Etop)
 594         a = walkexpr(a, init)
 595         init.Append(a)
 596 }
 597
 598 // initGenType is a bitmap indicating the types of generation that will occur for a static value.
 599 type initGenType uint8
 600
 601 const (
 602         initDynamic initGenType = 1 << iota // contains some dynamic values, for which init code will be generated
 603         initConst                           // contains some constant values, which may be written into data symbols
 604 )
 605
 606 // getdyn calculates the initGenType for n.
 607 // If top is false, getdyn is recursing.
 608 func getdyn(n *Node, top bool) initGenType {
 609         switch n.Op {
 610         default:
 611                 if isliteral(n) {
 612                         return initConst
 613                 }
 614                 return initDynamic
 615
 616         case OSLICELIT:
 617                 if !top {
 618                         return initDynamic
 619                 }
 620
 621         case OARRAYLIT, OSTRUCTLIT:
 622         }
 623
 624         var mode initGenType
 625         for _, n1 := range n.List.Slice() {
 626                 switch n1.Op {
 627                 case OKEY:
 628                         n1 = n1.Right
 629                 case OSTRUCTKEY:
 630                         n1 = n1.Left
 631                 }
 632                 mode |= getdyn(n1, false)
 633                 if mode == initDynamic|initConst {
 634                         break
 635                 }
 636         }
 637         return mode
 638 }
 639
 640 // isStaticCompositeLiteral reports whether n is a compile-time constant.
 641 func isStaticCompositeLiteral(n *Node) bool {
 642         switch n.Op {
 643         case OSLICELIT:
 644                 return false
 645         case OARRAYLIT:
 646                 for _, r := range n.List.Slice() {
 647                         if r.Op == OKEY {
 648                                 r = r.Right
 649                         }
 650                         if !isStaticCompositeLiteral(r) {
 651                                 return false
 652                         }
 653                 }
 654                 return true
 655         case OSTRUCTLIT:
 656                 for _, r := range n.List.Slice() {
 657                         if r.Op != OSTRUCTKEY {
 658                                 Fatalf("isStaticCompositeLiteral: rhs not OSTRUCTKEY: %v", r)
 659                         }
 660                         if !isStaticCompositeLiteral(r.Left) {
 661                                 return false
 662                         }
 663                 }
 664                 return true
 665         case OLITERAL:
 666                 return true
 667         case OCONVIFACE:
 668                 // See staticassign's OCONVIFACE case for comments.
 669                 val := n
 670                 for val.Op == OCONVIFACE {
 671                         val = val.Left
 672                 }
 673                 if val.Type.IsInterface() {
 674                         return Isconst(val, CTNIL)
 675                 }
 676                 if isdirectiface(val.Type) && Isconst(val, CTNIL) {
 677                         return true
 678                 }
 679                 return isStaticCompositeLiteral(val)
 680         }
 681         return false
 682 }
 683
 684 // initKind is a kind of static initialization: static, dynamic, or local.
 685 // Static initialization represents literals and
 686 // literal components of composite literals.
 687 // Dynamic initialization represents non-literals and
 688 // non-literal components of composite literals.
 689 // LocalCode initializion represents initialization
 690 // that occurs purely in generated code local to the function of use.
 691 // Initialization code is sometimes generated in passes,
 692 // first static then dynamic.
 693 type initKind uint8
 694
 695 const (
 696         initKindStatic initKind = iota + 1
 697         initKindDynamic
 698         initKindLocalCode
 699 )
 700
 701 // fixedlit handles struct, array, and slice literals.
 702 // TODO: expand documentation.
 703 func fixedlit(ctxt initContext, kind initKind, n *Node, var_ *Node, init *Nodes) {
 704         var splitnode func(*Node) (a *Node, value *Node)
 705         switch n.Op {
 706         case OARRAYLIT, OSLICELIT:
 707                 var k int64
 708                 splitnode = func(r *Node) (*Node, *Node) {
 709                         if r.Op == OKEY {
 710                                 k = nonnegintconst(r.Left)
 711                                 r = r.Right
 712                         }
 713                         a := nod(OINDEX, var_, nodintconst(k))
 714                         k++
 715                         return a, r
 716                 }
 717         case OSTRUCTLIT:
 718                 splitnode = func(r *Node) (*Node, *Node) {
 719                         if r.Op != OSTRUCTKEY {
 720                                 Fatalf("fixedlit: rhs not OSTRUCTKEY: %v", r)
 721                         }
 722                         return nodSym(ODOT, var_, r.Sym), r.Left
 723                 }
 724         default:
 725                 Fatalf("fixedlit bad op: %v", n.Op)
 726         }
 727
 728         for _, r := range n.List.Slice() {
 729                 a, value := splitnode(r)
 730
 731                 switch value.Op {
 732                 case OSLICELIT:
 733                         if (kind == initKindStatic && ctxt == inNonInitFunction) || (kind == initKindDynamic && ctxt == inInitFunction) {
 734                                 slicelit(ctxt, value, a, init)
 735                                 continue
 736                         }
 737
 738                 case OARRAYLIT, OSTRUCTLIT:
 739                         fixedlit(ctxt, kind, value, a, init)
 740                         continue
 741                 }
 742
 743                 islit := isliteral(value)
 744                 if (kind == initKindStatic && !islit) || (kind == initKindDynamic && islit) {
 745                         continue
 746                 }
 747
 748                 // build list of assignments: var[index] = expr
 749                 setlineno(value)
 750                 a = nod(OAS, a, value)
 751                 a = typecheck(a, Etop)
 752                 switch kind {
 753                 case initKindStatic:
 754                         a = walkexpr(a, init) // add any assignments in r to top
 755                         if a.Op == OASWB {
 756                                 // Static initialization never needs
 757                                 // write barriers.
 758                                 a.Op = OAS
 759                         }
 760                         if a.Op != OAS {
 761                                 Fatalf("fixedlit: not as, is %v", a)
 762                         }
 763                         a.IsStatic = true
 764                 case initKindDynamic, initKindLocalCode:
 765                         a = orderstmtinplace(a)
 766                         a = walkstmt(a)
 767                 default:
 768                         Fatalf("fixedlit: bad kind %d", kind)
 769                 }
 770
 771                 init.Append(a)
 772         }
 773 }
 774
 775 func slicelit(ctxt initContext, n *Node, var_ *Node, init *Nodes) {
 776         // make an array type corresponding the number of elements we have
 777         t := typArray(n.Type.Elem(), n.Right.Int64())
 778         dowidth(t)
 779
 780         if ctxt == inNonInitFunction {
 781                 // put everything into static array
 782                 vstat := staticname(t)
 783
 784                 fixedlit(ctxt, initKindStatic, n, vstat, init)
 785                 fixedlit(ctxt, initKindDynamic, n, vstat, init)
 786
 787                 // copy static to slice
 788                 a := nod(OSLICE, vstat, nil)
 789
 790                 a = nod(OAS, var_, a)
 791                 a = typecheck(a, Etop)
 792                 a.IsStatic = true
 793                 init.Append(a)
 794                 return
 795         }
 796
 797         // recipe for var = []t{...}
 798         // 1. make a static array
 799         //      var vstat [...]t
 800         // 2. assign (data statements) the constant part
 801         //      vstat = constpart{}
 802         // 3. make an auto pointer to array and allocate heap to it
 803         //      var vauto *[...]t = new([...]t)
 804         // 4. copy the static array to the auto array
 805         //      *vauto = vstat
 806         // 5. for each dynamic part assign to the array
 807         //      vauto[i] = dynamic part
 808         // 6. assign slice of allocated heap to var
 809         //      var = vauto[:]
 810         //
 811         // an optimization is done if there is no constant part
 812         //      3. var vauto *[...]t = new([...]t)
 813         //      5. vauto[i] = dynamic part
 814         //      6. var = vauto[:]
 815
 816         // if the literal contains constants,
 817         // make static initialized array (1),(2)
 818         var vstat *Node
 819
 820         mode := getdyn(n, true)
 821         if mode&initConst != 0 {
 822                 vstat = staticname(t)
 823                 if ctxt == inInitFunction {
 824                         vstat.Name.Readonly = true
 825                 }
 826                 fixedlit(ctxt, initKindStatic, n, vstat, init)
 827         }
 828
 829         // make new auto *array (3 declare)
 830         vauto := temp(ptrto(t))
 831
 832         // set auto to point at new temp or heap (3 assign)
 833         var a *Node
 834         if x := prealloc[n]; x != nil {
 835                 // temp allocated during order.go for dddarg
 836                 x.Type = t
 837
 838                 if vstat == nil {
 839                         a = nod(OAS, x, nil)
 840                         a = typecheck(a, Etop)
 841                         init.Append(a) // zero new temp
 842                 }
 843
 844                 a = nod(OADDR, x, nil)
 845         } else if n.Esc == EscNone {
 846                 a = temp(t)
 847                 if vstat == nil {
 848                         a = nod(OAS, temp(t), nil)
 849                         a = typecheck(a, Etop)
 850                         init.Append(a) // zero new temp
 851                         a = a.Left
 852                 }
 853
 854                 a = nod(OADDR, a, nil)
 855         } else {
 856                 a = nod(ONEW, nil, nil)
 857                 a.List.Set1(typenod(t))
 858         }
 859
 860         a = nod(OAS, vauto, a)
 861         a = typecheck(a, Etop)
 862         a = walkexpr(a, init)
 863         init.Append(a)
 864
 865         if vstat != nil {
 866                 // copy static to heap (4)
 867                 a = nod(OIND, vauto, nil)
 868
 869                 a = nod(OAS, a, vstat)
 870                 a = typecheck(a, Etop)
 871                 a = walkexpr(a, init)
 872                 init.Append(a)
 873         }
 874
 875         // put dynamics into array (5)
 876         var index int64
 877         for _, r := range n.List.Slice() {
 878                 value := r
 879                 if r.Op == OKEY {
 880                         index = nonnegintconst(r.Left)
 881                         value = r.Right
 882                 }
 883                 a := nod(OINDEX, vauto, nodintconst(index))
 884                 a.Bounded = true
 885                 index++
 886
 887                 // TODO need to check bounds?
 888
 889                 switch value.Op {
 890                 case OSLICELIT:
 891                         break
 892
 893                 case OARRAYLIT, OSTRUCTLIT:
 894                         fixedlit(ctxt, initKindDynamic, value, a, init)
 895                         continue
 896                 }
 897
 898                 if isliteral(value) {
 899                         continue
 900                 }
 901
 902                 // build list of vauto[c] = expr
 903                 setlineno(value)
 904                 a = nod(OAS, a, value)
 905
 906                 a = typecheck(a, Etop)
 907                 a = orderstmtinplace(a)
 908                 a = walkstmt(a)
 909                 init.Append(a)
 910         }
 911
 912         // make slice out of heap (6)
 913         a = nod(OAS, var_, nod(OSLICE, vauto, nil))
 914
 915         a = typecheck(a, Etop)
 916         a = orderstmtinplace(a)
 917         a = walkstmt(a)
 918         init.Append(a)
 919 }
 920
 921 func maplit(n *Node, m *Node, init *Nodes) {
 922         // make the map var
 923         nerr := nerrors
 924
 925         a := nod(OMAKE, nil, nil)
 926         a.List.Set2(typenod(n.Type), nodintconst(int64(len(n.List.Slice()))))
 927         litas(m, a, init)
 928
 929         // count the initializers
 930         b := 0
 931         for _, r := range n.List.Slice() {
 932                 if r.Op != OKEY {
 933                         Fatalf("maplit: rhs not OKEY: %v", r)
 934                 }
 935                 index := r.Left
 936                 value := r.Right
 937
 938                 if isliteral(index) && isliteral(value) {
 939                         b++
 940                 }
 941         }
 942
 943         if b != 0 {
 944                 // build types [count]Tindex and [count]Tvalue
 945                 tk := typArray(n.Type.Key(), int64(b))
 946                 tv := typArray(n.Type.Val(), int64(b))
 947
 948                 // TODO(josharian): suppress alg generation for these types?
 949                 dowidth(tk)
 950                 dowidth(tv)
 951
 952                 // make and initialize static arrays
 953                 vstatk := staticname(tk)
 954                 vstatk.Name.Readonly = true
 955                 vstatv := staticname(tv)
 956                 vstatv.Name.Readonly = true
 957
 958                 b := int64(0)
 959                 for _, r := range n.List.Slice() {
 960                         if r.Op != OKEY {
 961                                 Fatalf("maplit: rhs not OKEY: %v", r)
 962                         }
 963                         index := r.Left
 964                         value := r.Right
 965
 966                         if isliteral(index) && isliteral(value) {
 967                                 // build vstatk[b] = index
 968                                 setlineno(index)
 969                                 lhs := nod(OINDEX, vstatk, nodintconst(b))
 970                                 as := nod(OAS, lhs, index)
 971                                 as = typecheck(as, Etop)
 972                                 as = walkexpr(as, init)
 973                                 as.IsStatic = true
 974                                 init.Append(as)
 975
 976                                 // build vstatv[b] = value
 977                                 setlineno(value)
 978                                 lhs = nod(OINDEX, vstatv, nodintconst(b))
 979                                 as = nod(OAS, lhs, value)
 980                                 as = typecheck(as, Etop)
 981                                 as = walkexpr(as, init)
 982                                 as.IsStatic = true
 983                                 init.Append(as)
 984
 985                                 b++
 986                         }
 987                 }
 988
 989                 // loop adding structure elements to map
 990                 // for i = 0; i < len(vstatk); i++ {
 991                 //      map[vstatk[i]] = vstatv[i]
 992                 // }
 993                 i := temp(Types[TINT])
 994                 rhs := nod(OINDEX, vstatv, i)
 995                 rhs.Bounded = true
 996
 997                 kidx := nod(OINDEX, vstatk, i)
 998                 kidx.Bounded = true
 999                 lhs := nod(OINDEX, m, kidx)
1000
1001                 zero := nod(OAS, i, nodintconst(0))
1002                 cond := nod(OLT, i, nodintconst(tk.NumElem()))
1003                 incr := nod(OAS, i, nod(OADD, i, nodintconst(1)))
1004                 body := nod(OAS, lhs, rhs)
1005
1006                 loop := nod(OFOR, cond, incr)
1007                 loop.Nbody.Set1(body)
1008                 loop.Ninit.Set1(zero)
1009
1010                 loop = typecheck(loop, Etop)
1011                 loop = walkstmt(loop)
1012                 init.Append(loop)
1013         }
1014
1015         // put in dynamic entries one-at-a-time
1016         var key, val *Node
1017         for _, r := range n.List.Slice() {
1018                 if r.Op != OKEY {
1019                         Fatalf("maplit: rhs not OKEY: %v", r)
1020                 }
1021                 index := r.Left
1022                 value := r.Right
1023
1024                 if isliteral(index) && isliteral(value) {
1025                         continue
1026                 }
1027
1028                 // build list of var[c] = expr.
1029                 // use temporary so that mapassign1 can have addressable key, val.
1030                 if key == nil {
1031                         key = temp(m.Type.Key())
1032                         val = temp(m.Type.Val())
1033                 }
1034
1035                 setlineno(index)
1036                 a = nod(OAS, key, index)
1037                 a = typecheck(a, Etop)
1038                 a = walkstmt(a)
1039                 init.Append(a)
1040
1041                 setlineno(value)
1042                 a = nod(OAS, val, value)
1043                 a = typecheck(a, Etop)
1044                 a = walkstmt(a)
1045                 init.Append(a)
1046
1047                 setlineno(val)
1048                 a = nod(OAS, nod(OINDEX, m, key), val)
1049                 a = typecheck(a, Etop)
1050                 a = walkstmt(a)
1051                 init.Append(a)
1052
1053                 if nerr != nerrors {
1054                         break
1055                 }
1056         }
1057
1058         if key != nil {
1059                 a = nod(OVARKILL, key, nil)
1060                 a = typecheck(a, Etop)
1061                 init.Append(a)
1062                 a = nod(OVARKILL, val, nil)
1063                 a = typecheck(a, Etop)
1064                 init.Append(a)
1065         }
1066 }
1067
1068 func anylit(n *Node, var_ *Node, init *Nodes) {
1069         t := n.Type
1070         switch n.Op {
1071         default:
1072                 Fatalf("anylit: not lit, op=%v node=%v", n.Op, n)
1073
1074         case OPTRLIT:
1075                 if !t.IsPtr() {
1076                         Fatalf("anylit: not ptr")
1077                 }
1078
1079                 var r *Node
1080                 if n.Right != nil {
1081                         // n.Right is stack temporary used as backing store.
1082                         init.Append(nod(OAS, n.Right, nil)) // zero backing store, just in case (#18410)
1083                         r = nod(OADDR, n.Right, nil)
1084                         r = typecheck(r, Erv)
1085                 } else {
1086                         r = nod(ONEW, nil, nil)
1087                         r.Typecheck = 1
1088                         r.Type = t
1089                         r.Esc = n.Esc
1090                 }
1091
1092                 r = walkexpr(r, init)
1093                 a := nod(OAS, var_, r)
1094
1095                 a = typecheck(a, Etop)
1096                 init.Append(a)
1097
1098                 var_ = nod(OIND, var_, nil)
1099                 var_ = typecheck(var_, Erv|Easgn)
1100                 anylit(n.Left, var_, init)
1101
1102         case OSTRUCTLIT, OARRAYLIT:
1103                 if !t.IsStruct() && !t.IsArray() {
1104                         Fatalf("anylit: not struct/array")
1105                 }
1106
1107                 if var_.isSimpleName() && n.List.Len() > 4 {
1108                         // lay out static data
1109                         vstat := staticname(t)
1110                         vstat.Name.Readonly = true
1111
1112                         ctxt := inInitFunction
1113                         if n.Op == OARRAYLIT {
1114                                 ctxt = inNonInitFunction
1115                         }
1116                         fixedlit(ctxt, initKindStatic, n, vstat, init)
1117
1118                         // copy static to var
1119                         a := nod(OAS, var_, vstat)
1120
1121                         a = typecheck(a, Etop)
1122                         a = walkexpr(a, init)
1123                         init.Append(a)
1124
1125                         // add expressions to automatic
1126                         fixedlit(inInitFunction, initKindDynamic, n, var_, init)
1127                         break
1128                 }
1129
1130                 var components int64
1131                 if n.Op == OARRAYLIT {
1132                         components = t.NumElem()
1133                 } else {
1134                         components = int64(t.NumFields())
1135                 }
1136                 // initialization of an array or struct with unspecified components (missing fields or arrays)
1137                 if var_.isSimpleName() || int64(n.List.Len()) < components {
1138                         a := nod(OAS, var_, nil)
1139                         a = typecheck(a, Etop)
1140                         a = walkexpr(a, init)
1141                         init.Append(a)
1142                 }
1143
1144                 fixedlit(inInitFunction, initKindLocalCode, n, var_, init)
1145
1146         case OSLICELIT:
1147                 slicelit(inInitFunction, n, var_, init)
1148
1149         case OMAPLIT:
1150                 if !t.IsMap() {
1151                         Fatalf("anylit: not map")
1152                 }
1153                 maplit(n, var_, init)
1154         }
1155 }
1156
1157 func oaslit(n *Node, init *Nodes) bool {
1158         if n.Left == nil || n.Right == nil {
1159                 // not a special composite literal assignment
1160                 return false
1161         }
1162         if n.Left.Type == nil || n.Right.Type == nil {
1163                 // not a special composite literal assignment
1164                 return false
1165         }
1166         if !n.Left.isSimpleName() {
1167                 // not a special composite literal assignment
1168                 return false
1169         }
1170         if !eqtype(n.Left.Type, n.Right.Type) {
1171                 // not a special composite literal assignment
1172                 return false
1173         }
1174
1175         switch n.Right.Op {
1176         default:
1177                 // not a special composite literal assignment
1178                 return false
1179
1180         case OSTRUCTLIT, OARRAYLIT, OSLICELIT, OMAPLIT:
1181                 if vmatch1(n.Left, n.Right) {
1182                         // not a special composite literal assignment
1183                         return false
1184                 }
1185                 anylit(n.Right, n.Left, init)
1186         }
1187
1188         n.Op = OEMPTY
1189         n.Right = nil
1190         return true
1191 }
1192
1193 func getlit(lit *Node) int {
1194         if smallintconst(lit) {
1195                 return int(lit.Int64())
1196         }
1197         return -1
1198 }
1199
1200 // stataddr sets nam to the static address of n and reports whether it succeeded.
1201 func stataddr(nam *Node, n *Node) bool {
1202         if n == nil {
1203                 return false
1204         }
1205
1206         switch n.Op {
1207         case ONAME:
1208                 *nam = *n
1209                 return n.Addable
1210
1211         case ODOT:
1212                 if !stataddr(nam, n.Left) {
1213                         break
1214                 }
1215                 nam.Xoffset += n.Xoffset
1216                 nam.Type = n.Type
1217                 return true
1218
1219         case OINDEX:
1220                 if n.Left.Type.IsSlice() {
1221                         break
1222                 }
1223                 if !stataddr(nam, n.Left) {
1224                         break
1225                 }
1226                 l := getlit(n.Right)
1227                 if l < 0 {
1228                         break
1229                 }
1230
1231                 // Check for overflow.
1232                 if n.Type.Width != 0 && Thearch.MAXWIDTH/n.Type.Width <= int64(l) {
1233                         break
1234                 }
1235                 nam.Xoffset += int64(l) * n.Type.Width
1236                 nam.Type = n.Type
1237                 return true
1238         }
1239
1240         return false
1241 }
1242
1243 func initplan(n *Node) {
1244         if initplans[n] != nil {
1245                 return
1246         }
1247         p := new(InitPlan)
1248         initplans[n] = p
1249         switch n.Op {
1250         default:
1251                 Fatalf("initplan")
1252
1253         case OARRAYLIT, OSLICELIT:
1254                 var k int64
1255                 for _, a := range n.List.Slice() {
1256                         if a.Op == OKEY {
1257                                 k = nonnegintconst(a.Left)
1258                                 a = a.Right
1259                         }
1260                         addvalue(p, k*n.Type.Elem().Width, a)
1261                         k++
1262                 }
1263
1264         case OSTRUCTLIT:
1265                 for _, a := range n.List.Slice() {
1266                         if a.Op != OSTRUCTKEY {
1267                                 Fatalf("initplan fixedlit")
1268                         }
1269                         addvalue(p, a.Xoffset, a.Left)
1270                 }
1271
1272         case OMAPLIT:
1273                 for _, a := range n.List.Slice() {
1274                         if a.Op != OKEY {
1275                                 Fatalf("initplan maplit")
1276                         }
1277                         addvalue(p, -1, a.Right)
1278                 }
1279         }
1280 }
1281
1282 func addvalue(p *InitPlan, xoffset int64, n *Node) {
1283         // special case: zero can be dropped entirely
1284         if iszero(n) {
1285                 return
1286         }
1287
1288         // special case: inline struct and array (not slice) literals
1289         if isvaluelit(n) {
1290                 initplan(n)
1291                 q := initplans[n]
1292                 for _, qe := range q.E {
1293                         // qe is a copy; we are not modifying entries in q.E
1294                         qe.Xoffset += xoffset
1295                         p.E = append(p.E, qe)
1296                 }
1297                 return
1298         }
1299
1300         // add to plan
1301         p.E = append(p.E, InitEntry{Xoffset: xoffset, Expr: n})
1302 }
1303
1304 func iszero(n *Node) bool {
1305         switch n.Op {
1306         case OLITERAL:
1307                 switch u := n.Val().U.(type) {
1308                 default:
1309                         Dump("unexpected literal", n)
1310                         Fatalf("iszero")
1311                 case *NilVal:
1312                         return true
1313                 case string:
1314                         return u == ""
1315                 case bool:
1316                         return !u
1317                 case *Mpint:
1318                         return u.CmpInt64(0) == 0
1319                 case *Mpflt:
1320                         return u.CmpFloat64(0) == 0
1321                 case *Mpcplx:
1322                         return u.Real.CmpFloat64(0) == 0 && u.Imag.CmpFloat64(0) == 0
1323                 }
1324
1325         case OARRAYLIT:
1326                 for _, n1 := range n.List.Slice() {
1327                         if n1.Op == OKEY {
1328                                 n1 = n1.Right
1329                         }
1330                         if !iszero(n1) {
1331                                 return false
1332                         }
1333                 }
1334                 return true
1335
1336         case OSTRUCTLIT:
1337                 for _, n1 := range n.List.Slice() {
1338                         if !iszero(n1.Left) {
1339                                 return false
1340                         }
1341                 }
1342                 return true
1343         }
1344
1345         return false
1346 }
1347
1348 func isvaluelit(n *Node) bool {
1349         return n.Op == OARRAYLIT || n.Op == OSTRUCTLIT
1350 }
1351
1352 // gen_as_init attempts to emit static data for n and reports whether it succeeded.
1353 // If reportOnly is true, it does not emit static data and does not modify the AST.
1354 func gen_as_init(n *Node, reportOnly bool) bool {
1355         success := genAsInitNoCheck(n, reportOnly)
1356         if !success && n.IsStatic {
1357                 Dump("\ngen_as_init", n)
1358                 Fatalf("gen_as_init couldn't generate static data")
1359         }
1360         return success
1361 }
1362
1363 func genAsInitNoCheck(n *Node, reportOnly bool) bool {
1364         if !n.IsStatic {
1365                 return false
1366         }
1367
1368         nr := n.Right
1369         nl := n.Left
1370         if nr == nil {
1371                 var nam Node
1372                 return stataddr(&nam, nl) && nam.Class == PEXTERN
1373         }
1374
1375         if nr.Type == nil || !eqtype(nl.Type, nr.Type) {
1376                 return false
1377         }
1378
1379         var nam Node
1380         if !stataddr(&nam, nl) || nam.Class != PEXTERN {
1381                 return false
1382         }
1383
1384         switch nr.Op {
1385         default:
1386                 return false
1387
1388         case OCONVNOP:
1389                 nr = nr.Left
1390                 if nr == nil || nr.Op != OSLICEARR {
1391                         return false
1392                 }
1393                 fallthrough
1394
1395         case OSLICEARR:
1396                 low, high, _ := nr.SliceBounds()
1397                 if low != nil || high != nil {
1398                         return false
1399                 }
1400                 nr = nr.Left
1401                 if nr == nil || nr.Op != OADDR {
1402                         return false
1403                 }
1404                 ptr := nr
1405                 nr = nr.Left
1406                 if nr == nil || nr.Op != ONAME {
1407                         return false
1408                 }
1409
1410                 // nr is the array being converted to a slice
1411                 if nr.Type == nil || !nr.Type.IsArray() {
1412                         return false
1413                 }
1414
1415                 if !reportOnly {
1416                         nam.Xoffset += int64(array_array)
1417                         gdata(&nam, ptr, Widthptr)
1418
1419                         nam.Xoffset += int64(array_nel) - int64(array_array)
1420                         var nod1 Node
1421                         Nodconst(&nod1, Types[TINT], nr.Type.NumElem())
1422                         gdata(&nam, &nod1, Widthint)
1423
1424                         nam.Xoffset += int64(array_cap) - int64(array_nel)
1425                         gdata(&nam, &nod1, Widthint)
1426                 }
1427
1428                 return true
1429
1430         case OLITERAL:
1431                 if !reportOnly {
1432                         gdata(&nam, nr, int(nr.Type.Width))
1433                 }
1434                 return true
1435         }
1436 }