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

   1 // Copyright 2011 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         "cmd/compile/internal/ssa"
   9         "cmd/internal/obj"
  10         "crypto/md5"
  11         "fmt"
  12         "sort"
  13         "strings"
  14 )
  15
  16 // "Portable" code generation.
  17
  18 var makefuncdatasym_nsym int32
  19
  20 func makefuncdatasym(namefmt string, funcdatakind int64) *Sym {
  21         var nod Node
  22
  23         sym := Lookupf(namefmt, makefuncdatasym_nsym)
  24         makefuncdatasym_nsym++
  25         pnod := newname(sym)
  26         pnod.Class = PEXTERN
  27         Nodconst(&nod, Types[TINT32], funcdatakind)
  28         Thearch.Gins(obj.AFUNCDATA, &nod, pnod)
  29         return sym
  30 }
  31
  32 // gvardef inserts a VARDEF for n into the instruction stream.
  33 // VARDEF is an annotation for the liveness analysis, marking a place
  34 // where a complete initialization (definition) of a variable begins.
  35 // Since the liveness analysis can see initialization of single-word
  36 // variables quite easy, gvardef is usually only called for multi-word
  37 // or 'fat' variables, those satisfying isfat(n->type).
  38 // However, gvardef is also called when a non-fat variable is initialized
  39 // via a block move; the only time this happens is when you have
  40 //      return f()
  41 // for a function with multiple return values exactly matching the return
  42 // types of the current function.
  43 //
  44 // A 'VARDEF x' annotation in the instruction stream tells the liveness
  45 // analysis to behave as though the variable x is being initialized at that
  46 // point in the instruction stream. The VARDEF must appear before the
  47 // actual (multi-instruction) initialization, and it must also appear after
  48 // any uses of the previous value, if any. For example, if compiling:
  49 //
  50 //      x = x[1:]
  51 //
  52 // it is important to generate code like:
  53 //
  54 //      base, len, cap = pieces of x[1:]
  55 //      VARDEF x
  56 //      x = {base, len, cap}
  57 //
  58 // If instead the generated code looked like:
  59 //
  60 //      VARDEF x
  61 //      base, len, cap = pieces of x[1:]
  62 //      x = {base, len, cap}
  63 //
  64 // then the liveness analysis would decide the previous value of x was
  65 // unnecessary even though it is about to be used by the x[1:] computation.
  66 // Similarly, if the generated code looked like:
  67 //
  68 //      base, len, cap = pieces of x[1:]
  69 //      x = {base, len, cap}
  70 //      VARDEF x
  71 //
  72 // then the liveness analysis will not preserve the new value of x, because
  73 // the VARDEF appears to have "overwritten" it.
  74 //
  75 // VARDEF is a bit of a kludge to work around the fact that the instruction
  76 // stream is working on single-word values but the liveness analysis
  77 // wants to work on individual variables, which might be multi-word
  78 // aggregates. It might make sense at some point to look into letting
  79 // the liveness analysis work on single-word values as well, although
  80 // there are complications around interface values, slices, and strings,
  81 // all of which cannot be treated as individual words.
  82 //
  83 // VARKILL is the opposite of VARDEF: it marks a value as no longer needed,
  84 // even if its address has been taken. That is, a VARKILL annotation asserts
  85 // that its argument is certainly dead, for use when the liveness analysis
  86 // would not otherwise be able to deduce that fact.
  87
  88 func gvardefx(n *Node, as int) {
  89         if n == nil {
  90                 Fatalf("gvardef nil")
  91         }
  92         if n.Op != ONAME {
  93                 Yyerror("gvardef %v; %v", Oconv(int(n.Op), obj.FmtSharp), n)
  94                 return
  95         }
  96
  97         switch n.Class {
  98         case PAUTO, PPARAM, PPARAMOUT:
  99                 if as == obj.AVARLIVE {
 100                         Thearch.Gins(as, n, nil)
 101                 } else {
 102                         Thearch.Gins(as, nil, n)
 103                 }
 104         }
 105 }
 106
 107 func Gvardef(n *Node) {
 108         gvardefx(n, obj.AVARDEF)
 109 }
 110
 111 func gvarkill(n *Node) {
 112         gvardefx(n, obj.AVARKILL)
 113 }
 114
 115 func gvarlive(n *Node) {
 116         gvardefx(n, obj.AVARLIVE)
 117 }
 118
 119 func removevardef(firstp *obj.Prog) {
 120         for p := firstp; p != nil; p = p.Link {
 121                 for p.Link != nil && (p.Link.As == obj.AVARDEF || p.Link.As == obj.AVARKILL || p.Link.As == obj.AVARLIVE) {
 122                         p.Link = p.Link.Link
 123                 }
 124                 if p.To.Type == obj.TYPE_BRANCH {
 125                         for p.To.Val.(*obj.Prog) != nil && (p.To.Val.(*obj.Prog).As == obj.AVARDEF || p.To.Val.(*obj.Prog).As == obj.AVARKILL || p.To.Val.(*obj.Prog).As == obj.AVARLIVE) {
 126                                 p.To.Val = p.To.Val.(*obj.Prog).Link
 127                         }
 128                 }
 129         }
 130 }
 131
 132 func gcsymdup(s *Sym) {
 133         ls := Linksym(s)
 134         if len(ls.R) > 0 {
 135                 Fatalf("cannot rosymdup %s with relocations", ls.Name)
 136         }
 137         ls.Name = fmt.Sprintf("gclocals·%x", md5.Sum(ls.P))
 138         ls.Dupok = 1
 139 }
 140
 141 func emitptrargsmap() {
 142         if Curfn.Func.Nname.Sym.Name == "_" {
 143                 return
 144         }
 145         sym := Lookup(fmt.Sprintf("%s.args_stackmap", Curfn.Func.Nname.Sym.Name))
 146
 147         nptr := int(Curfn.Type.Argwid / int64(Widthptr))
 148         bv := bvalloc(int32(nptr) * 2)
 149         nbitmap := 1
 150         if Curfn.Type.Outtuple > 0 {
 151                 nbitmap = 2
 152         }
 153         off := duint32(sym, 0, uint32(nbitmap))
 154         off = duint32(sym, off, uint32(bv.n))
 155         var xoffset int64
 156         if Curfn.Type.Thistuple > 0 {
 157                 xoffset = 0
 158                 onebitwalktype1(getthisx(Curfn.Type), &xoffset, bv)
 159         }
 160
 161         if Curfn.Type.Intuple > 0 {
 162                 xoffset = 0
 163                 onebitwalktype1(getinargx(Curfn.Type), &xoffset, bv)
 164         }
 165
 166         for j := 0; int32(j) < bv.n; j += 32 {
 167                 off = duint32(sym, off, bv.b[j/32])
 168         }
 169         if Curfn.Type.Outtuple > 0 {
 170                 xoffset = 0
 171                 onebitwalktype1(getoutargx(Curfn.Type), &xoffset, bv)
 172                 for j := 0; int32(j) < bv.n; j += 32 {
 173                         off = duint32(sym, off, bv.b[j/32])
 174                 }
 175         }
 176
 177         ggloblsym(sym, int32(off), obj.RODATA|obj.LOCAL)
 178 }
 179
 180 // cmpstackvarlt reports whether the stack variable a sorts before b.
 181 //
 182 // Sort the list of stack variables. Autos after anything else,
 183 // within autos, unused after used, within used, things with
 184 // pointers first, zeroed things first, and then decreasing size.
 185 // Because autos are laid out in decreasing addresses
 186 // on the stack, pointers first, zeroed things first and decreasing size
 187 // really means, in memory, things with pointers needing zeroing at
 188 // the top of the stack and increasing in size.
 189 // Non-autos sort on offset.
 190 func cmpstackvarlt(a, b *Node) bool {
 191         if (a.Class == PAUTO) != (b.Class == PAUTO) {
 192                 return b.Class == PAUTO
 193         }
 194
 195         if a.Class != PAUTO {
 196                 return a.Xoffset < b.Xoffset
 197         }
 198
 199         if a.Used != b.Used {
 200                 return a.Used
 201         }
 202
 203         ap := haspointers(a.Type)
 204         bp := haspointers(b.Type)
 205         if ap != bp {
 206                 return ap
 207         }
 208
 209         ap = a.Name.Needzero
 210         bp = b.Name.Needzero
 211         if ap != bp {
 212                 return ap
 213         }
 214
 215         if a.Type.Width != b.Type.Width {
 216                 return a.Type.Width > b.Type.Width
 217         }
 218
 219         return a.Sym.Name < b.Sym.Name
 220 }
 221
 222 // byStackvar implements sort.Interface for []*Node using cmpstackvarlt.
 223 type byStackVar []*Node
 224
 225 func (s byStackVar) Len() int           { return len(s) }
 226 func (s byStackVar) Less(i, j int) bool { return cmpstackvarlt(s[i], s[j]) }
 227 func (s byStackVar) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
 228
 229 // stkdelta records the stack offset delta for a node
 230 // during the compaction of the stack frame to remove
 231 // unused stack slots.
 232 var stkdelta = map[*Node]int64{}
 233
 234 // TODO(lvd) find out where the PAUTO/OLITERAL nodes come from.
 235 func allocauto(ptxt *obj.Prog) {
 236         Stksize = 0
 237         stkptrsize = 0
 238
 239         if len(Curfn.Func.Dcl) == 0 {
 240                 return
 241         }
 242
 243         // Mark the PAUTO's unused.
 244         for _, ln := range Curfn.Func.Dcl {
 245                 if ln.Class == PAUTO {
 246                         ln.Used = false
 247                 }
 248         }
 249
 250         markautoused(ptxt)
 251
 252         sort.Sort(byStackVar(Curfn.Func.Dcl))
 253
 254         // Unused autos are at the end, chop 'em off.
 255         n := Curfn.Func.Dcl[0]
 256         if n.Class == PAUTO && n.Op == ONAME && !n.Used {
 257                 // No locals used at all
 258                 Curfn.Func.Dcl = nil
 259
 260                 fixautoused(ptxt)
 261                 return
 262         }
 263
 264         for i := 1; i < len(Curfn.Func.Dcl); i++ {
 265                 n = Curfn.Func.Dcl[i]
 266                 if n.Class == PAUTO && n.Op == ONAME && !n.Used {
 267                         Curfn.Func.Dcl = Curfn.Func.Dcl[:i]
 268                         break
 269                 }
 270         }
 271
 272         // Reassign stack offsets of the locals that are still there.
 273         var w int64
 274         for _, n := range Curfn.Func.Dcl {
 275                 if n.Class != PAUTO || n.Op != ONAME {
 276                         continue
 277                 }
 278
 279                 dowidth(n.Type)
 280                 w = n.Type.Width
 281                 if w >= Thearch.MAXWIDTH || w < 0 {
 282                         Fatalf("bad width")
 283                 }
 284                 Stksize += w
 285                 Stksize = Rnd(Stksize, int64(n.Type.Align))
 286                 if haspointers(n.Type) {
 287                         stkptrsize = Stksize
 288                 }
 289                 if Thearch.Thechar == '0' || Thearch.Thechar == '5' || Thearch.Thechar == '7' || Thearch.Thechar == '9' {
 290                         Stksize = Rnd(Stksize, int64(Widthptr))
 291                 }
 292                 if Stksize >= 1<<31 {
 293                         setlineno(Curfn)
 294                         Yyerror("stack frame too large (>2GB)")
 295                 }
 296
 297                 stkdelta[n] = -Stksize - n.Xoffset
 298         }
 299
 300         Stksize = Rnd(Stksize, int64(Widthreg))
 301         stkptrsize = Rnd(stkptrsize, int64(Widthreg))
 302
 303         fixautoused(ptxt)
 304
 305         // The debug information needs accurate offsets on the symbols.
 306         for _, ln := range Curfn.Func.Dcl {
 307                 if ln.Class != PAUTO || ln.Op != ONAME {
 308                         continue
 309                 }
 310                 ln.Xoffset += stkdelta[ln]
 311                 delete(stkdelta, ln)
 312         }
 313 }
 314
 315 func Cgen_checknil(n *Node) {
 316         if Disable_checknil != 0 {
 317                 return
 318         }
 319
 320         // Ideally we wouldn't see any integer types here, but we do.
 321         if n.Type == nil || (!Isptr[n.Type.Etype] && !Isint[n.Type.Etype] && n.Type.Etype != TUNSAFEPTR) {
 322                 Dump("checknil", n)
 323                 Fatalf("bad checknil")
 324         }
 325
 326         if ((Thearch.Thechar == '0' || Thearch.Thechar == '5' || Thearch.Thechar == '7' || Thearch.Thechar == '9') && n.Op != OREGISTER) || !n.Addable || n.Op == OLITERAL {
 327                 var reg Node
 328                 Regalloc(&reg, Types[Tptr], n)
 329                 Cgen(n, &reg)
 330                 Thearch.Gins(obj.ACHECKNIL, &reg, nil)
 331                 Regfree(&reg)
 332                 return
 333         }
 334
 335         Thearch.Gins(obj.ACHECKNIL, n, nil)
 336 }
 337
 338 func compile(fn *Node) {
 339         if Newproc == nil {
 340                 Newproc = Sysfunc("newproc")
 341                 Deferproc = Sysfunc("deferproc")
 342                 Deferreturn = Sysfunc("deferreturn")
 343                 Panicindex = Sysfunc("panicindex")
 344                 panicslice = Sysfunc("panicslice")
 345                 panicdivide = Sysfunc("panicdivide")
 346                 throwreturn = Sysfunc("throwreturn")
 347                 growslice = Sysfunc("growslice")
 348                 writebarrierptr = Sysfunc("writebarrierptr")
 349                 typedmemmove = Sysfunc("typedmemmove")
 350                 panicdottype = Sysfunc("panicdottype")
 351         }
 352
 353         lno := setlineno(fn)
 354
 355         Curfn = fn
 356         dowidth(Curfn.Type)
 357
 358         var oldstksize int64
 359         var nod1 Node
 360         var ptxt *obj.Prog
 361         var pl *obj.Plist
 362         var p *obj.Prog
 363         var n *Node
 364         var nam *Node
 365         var gcargs *Sym
 366         var gclocals *Sym
 367         var ssafn *ssa.Func
 368         if fn.Nbody == nil {
 369                 if pure_go != 0 || strings.HasPrefix(fn.Func.Nname.Sym.Name, "init.") {
 370                         Yyerror("missing function body for %q", fn.Func.Nname.Sym.Name)
 371                         goto ret
 372                 }
 373
 374                 if Debug['A'] != 0 {
 375                         goto ret
 376                 }
 377                 emitptrargsmap()
 378                 goto ret
 379         }
 380
 381         saveerrors()
 382
 383         // set up domain for labels
 384         clearlabels()
 385
 386         if Curfn.Type.Outnamed {
 387                 // add clearing of the output parameters
 388                 var save Iter
 389                 t := Structfirst(&save, Getoutarg(Curfn.Type))
 390
 391                 for t != nil {
 392                         if t.Nname != nil {
 393                                 n = Nod(OAS, t.Nname, nil)
 394                                 typecheck(&n, Etop)
 395                                 Curfn.Nbody = concat(list1(n), Curfn.Nbody)
 396                         }
 397
 398                         t = structnext(&save)
 399                 }
 400         }
 401
 402         order(Curfn)
 403         if nerrors != 0 {
 404                 goto ret
 405         }
 406
 407         hasdefer = false
 408         walk(Curfn)
 409         if nerrors != 0 {
 410                 goto ret
 411         }
 412         if instrumenting {
 413                 instrument(Curfn)
 414         }
 415         if nerrors != 0 {
 416                 goto ret
 417         }
 418
 419         // Build an SSA backend function.
 420         if shouldssa(Curfn) {
 421                 ssafn = buildssa(Curfn)
 422         }
 423
 424         continpc = nil
 425         breakpc = nil
 426
 427         pl = newplist()
 428         pl.Name = Linksym(Curfn.Func.Nname.Sym)
 429
 430         setlineno(Curfn)
 431
 432         Nodconst(&nod1, Types[TINT32], 0)
 433         nam = Curfn.Func.Nname
 434         if isblank(nam) {
 435                 nam = nil
 436         }
 437         ptxt = Thearch.Gins(obj.ATEXT, nam, &nod1)
 438         Afunclit(&ptxt.From, Curfn.Func.Nname)
 439         ptxt.From3 = new(obj.Addr)
 440         if fn.Func.Dupok {
 441                 ptxt.From3.Offset |= obj.DUPOK
 442         }
 443         if fn.Func.Wrapper {
 444                 ptxt.From3.Offset |= obj.WRAPPER
 445         }
 446         if fn.Func.Needctxt {
 447                 ptxt.From3.Offset |= obj.NEEDCTXT
 448         }
 449         if fn.Func.Pragma&Nosplit != 0 {
 450                 ptxt.From3.Offset |= obj.NOSPLIT
 451         }
 452         if fn.Func.Pragma&Systemstack != 0 {
 453                 ptxt.From.Sym.Cfunc = 1
 454         }
 455
 456         // Clumsy but important.
 457         // See test/recover.go for test cases and src/reflect/value.go
 458         // for the actual functions being considered.
 459         if myimportpath != "" && myimportpath == "reflect" {
 460                 if Curfn.Func.Nname.Sym.Name == "callReflect" || Curfn.Func.Nname.Sym.Name == "callMethod" {
 461                         ptxt.From3.Offset |= obj.WRAPPER
 462                 }
 463         }
 464
 465         ginit()
 466
 467         gcargs = makefuncdatasym("gcargs·%d", obj.FUNCDATA_ArgsPointerMaps)
 468         gclocals = makefuncdatasym("gclocals·%d", obj.FUNCDATA_LocalsPointerMaps)
 469
 470         for _, t := range Curfn.Func.Fieldtrack {
 471                 gtrack(tracksym(t))
 472         }
 473
 474         for _, n := range fn.Func.Dcl {
 475                 if n.Op != ONAME { // might be OTYPE or OLITERAL
 476                         continue
 477                 }
 478                 switch n.Class {
 479                 case PAUTO, PPARAM, PPARAMOUT:
 480                         Nodconst(&nod1, Types[TUINTPTR], n.Type.Width)
 481                         p = Thearch.Gins(obj.ATYPE, n, &nod1)
 482                         p.From.Gotype = Linksym(ngotype(n))
 483                 }
 484         }
 485
 486         if ssafn != nil {
 487                 genssa(ssafn, ptxt, gcargs, gclocals)
 488                 if Curfn.Func.Endlineno != 0 {
 489                         lineno = Curfn.Func.Endlineno
 490                 }
 491                 ssafn.Free()
 492                 return
 493         }
 494         Genslice(Curfn.Func.Enter.Slice())
 495         Genlist(Curfn.Nbody)
 496         gclean()
 497         checklabels()
 498         if nerrors != 0 {
 499                 goto ret
 500         }
 501         if Curfn.Func.Endlineno != 0 {
 502                 lineno = Curfn.Func.Endlineno
 503         }
 504
 505         if Curfn.Type.Outtuple != 0 {
 506                 Ginscall(throwreturn, 0)
 507         }
 508
 509         ginit()
 510
 511         // TODO: Determine when the final cgen_ret can be omitted. Perhaps always?
 512         cgen_ret(nil)
 513
 514         if hasdefer {
 515                 // deferreturn pretends to have one uintptr argument.
 516                 // Reserve space for it so stack scanner is happy.
 517                 if Maxarg < int64(Widthptr) {
 518                         Maxarg = int64(Widthptr)
 519                 }
 520         }
 521
 522         gclean()
 523         if nerrors != 0 {
 524                 goto ret
 525         }
 526
 527         Pc.As = obj.ARET // overwrite AEND
 528         Pc.Lineno = lineno
 529
 530         fixjmp(ptxt)
 531         if Debug['N'] == 0 || Debug['R'] != 0 || Debug['P'] != 0 {
 532                 regopt(ptxt)
 533                 nilopt(ptxt)
 534         }
 535
 536         Thearch.Expandchecks(ptxt)
 537
 538         oldstksize = Stksize
 539         allocauto(ptxt)
 540
 541         if false {
 542                 fmt.Printf("allocauto: %d to %d\n", oldstksize, int64(Stksize))
 543         }
 544
 545         setlineno(Curfn)
 546         if int64(Stksize)+Maxarg > 1<<31 {
 547                 Yyerror("stack frame too large (>2GB)")
 548                 goto ret
 549         }
 550
 551         // Emit garbage collection symbols.
 552         liveness(Curfn, ptxt, gcargs, gclocals)
 553
 554         gcsymdup(gcargs)
 555         gcsymdup(gclocals)
 556
 557         Thearch.Defframe(ptxt)
 558
 559         if Debug['f'] != 0 {
 560                 frame(0)
 561         }
 562
 563         // Remove leftover instrumentation from the instruction stream.
 564         removevardef(ptxt)
 565
 566 ret:
 567         lineno = lno
 568 }