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