src/cmd/compile/internal/gc/syntax.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 // “Abstract” syntax representation.
   6
   7 package gc
   8
   9 // A Node is a single node in the syntax tree.
  10 // Actually the syntax tree is a syntax DAG, because there is only one
  11 // node with Op=ONAME for a given instance of a variable x.
  12 // The same is true for Op=OTYPE and Op=OLITERAL.
  13 type Node struct {
  14         // Tree structure.
  15         // Generic recursive walks should follow these fields.
  16         Left  *Node
  17         Right *Node
  18         Ninit *NodeList
  19         Nbody *NodeList
  20         List  *NodeList
  21         Rlist *NodeList
  22
  23         // most nodes
  24         Type *Type
  25         Orig *Node // original form, for printing, and tracking copies of ONAMEs
  26
  27         // func
  28         Func *Func
  29
  30         // ONAME
  31         Name *Name
  32
  33         Sym *Sym        // various
  34         E   interface{} // Opt or Val, see methods below
  35
  36         Xoffset int64
  37
  38         Lineno int32
  39
  40         // OREGISTER, OINDREG
  41         Reg int16
  42
  43         Esc uint16 // EscXXX
  44
  45         Op          Op
  46         Nointerface bool
  47         Ullman      uint8 // sethi/ullman number
  48         Addable     bool  // addressable
  49         Etype       EType // op for OASOP, etype for OTYPE, exclam for export, 6g saved reg
  50         Bounded     bool  // bounds check unnecessary
  51         Class       Class // PPARAM, PAUTO, PEXTERN, etc
  52         Embedded    uint8 // ODCLFIELD embedded type
  53         Colas       bool  // OAS resulting from :=
  54         Diag        uint8 // already printed error about this
  55         Noescape    bool  // func arguments do not escape; TODO(rsc): move Noescape to Func struct (see CL 7360)
  56         Walkdef     uint8
  57         Typecheck   uint8
  58         Local       bool
  59         Dodata      uint8
  60         Initorder   uint8
  61         Used        bool
  62         Isddd       bool // is the argument variadic
  63         Implicit    bool
  64         Addrtaken   bool // address taken, even if not moved to heap
  65         Assigned    bool // is the variable ever assigned to
  66         Likely      int8 // likeliness of if statement
  67         Hasbreak    bool // has break statement
  68         hasVal      int8 // +1 for Val, -1 for Opt, 0 for not yet set
  69 }
  70
  71 // Val returns the Val for the node.
  72 func (n *Node) Val() Val {
  73         if n.hasVal != +1 {
  74                 return Val{}
  75         }
  76         return Val{n.E}
  77 }
  78
  79 // SetVal sets the Val for the node, which must not have been used with SetOpt.
  80 func (n *Node) SetVal(v Val) {
  81         if n.hasVal == -1 {
  82                 Debug['h'] = 1
  83                 Dump("have Opt", n)
  84                 Fatalf("have Opt")
  85         }
  86         n.hasVal = +1
  87         n.E = v.U
  88 }
  89
  90 // Opt returns the optimizer data for the node.
  91 func (n *Node) Opt() interface{} {
  92         if n.hasVal != -1 {
  93                 return nil
  94         }
  95         return n.E
  96 }
  97
  98 // SetOpt sets the optimizer data for the node, which must not have been used with SetVal.
  99 // SetOpt(nil) is ignored for Vals to simplify call sites that are clearing Opts.
 100 func (n *Node) SetOpt(x interface{}) {
 101         if x == nil && n.hasVal >= 0 {
 102                 return
 103         }
 104         if n.hasVal == +1 {
 105                 Debug['h'] = 1
 106                 Dump("have Val", n)
 107                 Fatalf("have Val")
 108         }
 109         n.hasVal = -1
 110         n.E = x
 111 }
 112
 113 // Name holds Node fields used only by named nodes (ONAME, OPACK, some OLITERAL).
 114 type Name struct {
 115         Pack      *Node // real package for import . names
 116         Pkg       *Pkg  // pkg for OPACK nodes
 117         Heapaddr  *Node // temp holding heap address of param
 118         Inlvar    *Node // ONAME substitute while inlining
 119         Defn      *Node // initializing assignment
 120         Curfn     *Node // function for local variables
 121         Param     *Param
 122         Decldepth int32 // declaration loop depth, increased for every loop or label
 123         Vargen    int32 // unique name for ONAME within a function.  Function outputs are numbered starting at one.
 124         Iota      int32 // value if this name is iota
 125         Funcdepth int32
 126         Method    bool // OCALLMETH name
 127         Readonly  bool
 128         Captured  bool // is the variable captured by a closure
 129         Byval     bool // is the variable captured by value or by reference
 130         Needzero  bool // if it contains pointers, needs to be zeroed on function entry
 131         Keepalive bool // mark value live across unknown assembly call
 132 }
 133
 134 type Param struct {
 135         Ntype *Node
 136
 137         // ONAME func param with PHEAP
 138         Outerexpr  *Node // expression copied into closure for variable
 139         Stackparam *Node // OPARAM node referring to stack copy of param
 140
 141         // ONAME PPARAM
 142         Field *Type // TFIELD in arg struct
 143
 144         // ONAME closure param with PPARAMREF
 145         Outer   *Node // outer PPARAMREF in nested closure
 146         Closure *Node // ONAME/PHEAP <-> ONAME/PPARAMREF
 147 }
 148
 149 // Func holds Node fields used only with function-like nodes.
 150 type Func struct {
 151         Shortname  *Node
 152         Enter      Nodes
 153         Exit       Nodes
 154         Cvars      Nodes    // closure params
 155         Dcl        []*Node  // autodcl for this func/closure
 156         Inldcl     *[]*Node // copy of dcl for use in inlining
 157         Closgen    int
 158         Outerfunc  *Node
 159         Fieldtrack []*Type
 160         Outer      *Node // outer func for closure
 161         Ntype      *Node // signature
 162         Top        int   // top context (Ecall, Eproc, etc)
 163         Closure    *Node // OCLOSURE <-> ODCLFUNC
 164         FCurfn     *Node
 165         Nname      *Node
 166
 167         Inl     *NodeList // copy of the body for use in inlining
 168         InlCost int32
 169         Depth   int32
 170
 171         Endlineno int32
 172         WBLineno  int32 // line number of first write barrier
 173
 174         Pragma   Pragma // go:xxx function annotations
 175         Dupok    bool   // duplicate definitions ok
 176         Wrapper  bool   // is method wrapper
 177         Needctxt bool   // function uses context register (has closure variables)
 178 }
 179
 180 type Op uint8
 181
 182 // Node ops.
 183 const (
 184         OXXX = Op(iota)
 185
 186         // names
 187         ONAME    // var, const or func name
 188         ONONAME  // unnamed arg or return value: f(int, string) (int, error) { etc }
 189         OTYPE    // type name
 190         OPACK    // import
 191         OLITERAL // literal
 192
 193         // expressions
 194         OADD             // Left + Right
 195         OSUB             // Left - Right
 196         OOR              // Left | Right
 197         OXOR             // Left ^ Right
 198         OADDSTR          // Left + Right (string addition)
 199         OADDR            // &Left
 200         OANDAND          // Left && Right
 201         OAPPEND          // append(List)
 202         OARRAYBYTESTR    // Type(Left) (Type is string, Left is a []byte)
 203         OARRAYBYTESTRTMP // Type(Left) (Type is string, Left is a []byte, ephemeral)
 204         OARRAYRUNESTR    // Type(Left) (Type is string, Left is a []rune)
 205         OSTRARRAYBYTE    // Type(Left) (Type is []byte, Left is a string)
 206         OSTRARRAYBYTETMP // Type(Left) (Type is []byte, Left is a string, ephemeral)
 207         OSTRARRAYRUNE    // Type(Left) (Type is []rune, Left is a string)
 208         OAS              // Left = Right or (if Colas=true) Left := Right
 209         OAS2             // List = Rlist (x, y, z = a, b, c)
 210         OAS2FUNC         // List = Rlist (x, y = f())
 211         OAS2RECV         // List = Rlist (x, ok = <-c)
 212         OAS2MAPR         // List = Rlist (x, ok = m["foo"])
 213         OAS2DOTTYPE      // List = Rlist (x, ok = I.(int))
 214         OASOP            // Left Etype= Right (x += y)
 215         OASWB            // Left = Right (with write barrier)
 216         OCALL            // Left(List) (function call, method call or type conversion)
 217         OCALLFUNC        // Left(List) (function call f(args))
 218         OCALLMETH        // Left(List) (direct method call x.Method(args))
 219         OCALLINTER       // Left(List) (interface method call x.Method(args))
 220         OCALLPART        // Left.Right (method expression x.Method, not called)
 221         OCAP             // cap(Left)
 222         OCLOSE           // close(Left)
 223         OCLOSURE         // func Type { Body } (func literal)
 224         OCMPIFACE        // Left Etype Right (interface comparison, x == y or x != y)
 225         OCMPSTR          // Left Etype Right (string comparison, x == y, x < y, etc)
 226         OCOMPLIT         // Right{List} (composite literal, not yet lowered to specific form)
 227         OMAPLIT          // Type{List} (composite literal, Type is map)
 228         OSTRUCTLIT       // Type{List} (composite literal, Type is struct)
 229         OARRAYLIT        // Type{List} (composite literal, Type is array or slice)
 230         OPTRLIT          // &Left (left is composite literal)
 231         OCONV            // Type(Left) (type conversion)
 232         OCONVIFACE       // Type(Left) (type conversion, to interface)
 233         OCONVNOP         // Type(Left) (type conversion, no effect)
 234         OCOPY            // copy(Left, Right)
 235         ODCL             // var Left (declares Left of type Left.Type)
 236
 237         // Used during parsing but don't last.
 238         ODCLFUNC  // func f() or func (r) f()
 239         ODCLFIELD // struct field, interface field, or func/method argument/return value.
 240         ODCLCONST // const pi = 3.14
 241         ODCLTYPE  // type Int int
 242
 243         ODELETE    // delete(Left, Right)
 244         ODOT       // Left.Right (Left is of struct type)
 245         ODOTPTR    // Left.Right (Left is of pointer to struct type)
 246         ODOTMETH   // Left.Right (Left is non-interface, Right is method name)
 247         ODOTINTER  // Left.Right (Left is interface, Right is method name)
 248         OXDOT      // Left.Right (before rewrite to one of the preceding)
 249         ODOTTYPE   // Left.Right or Left.Type (.Right during parsing, .Type once resolved)
 250         ODOTTYPE2  // Left.Right or Left.Type (.Right during parsing, .Type once resolved; on rhs of OAS2DOTTYPE)
 251         OEQ        // Left == Right
 252         ONE        // Left != Right
 253         OLT        // Left < Right
 254         OLE        // Left <= Right
 255         OGE        // Left >= Right
 256         OGT        // Left > Right
 257         OIND       // *Left
 258         OINDEX     // Left[Right] (index of array or slice)
 259         OINDEXMAP  // Left[Right] (index of map)
 260         OKEY       // Left:Right (key:value in struct/array/map literal, or slice index pair)
 261         OPARAM     // variant of ONAME for on-stack copy of a parameter or return value that escapes.
 262         OLEN       // len(Left)
 263         OMAKE      // make(List) (before type checking converts to one of the following)
 264         OMAKECHAN  // make(Type, Left) (type is chan)
 265         OMAKEMAP   // make(Type, Left) (type is map)
 266         OMAKESLICE // make(Type, Left, Right) (type is slice)
 267         OMUL       // Left * Right
 268         ODIV       // Left / Right
 269         OMOD       // Left % Right
 270         OLSH       // Left << Right
 271         ORSH       // Left >> Right
 272         OAND       // Left & Right
 273         OANDNOT    // Left &^ Right
 274         ONEW       // new(Left)
 275         ONOT       // !Left
 276         OCOM       // ^Left
 277         OPLUS      // +Left
 278         OMINUS     // -Left
 279         OOROR      // Left || Right
 280         OPANIC     // panic(Left)
 281         OPRINT     // print(List)
 282         OPRINTN    // println(List)
 283         OPAREN     // (Left)
 284         OSEND      // Left <- Right
 285         OSLICE     // Left[Right.Left : Right.Right] (Left is untypechecked or slice; Right.Op==OKEY)
 286         OSLICEARR  // Left[Right.Left : Right.Right] (Left is array)
 287         OSLICESTR  // Left[Right.Left : Right.Right] (Left is string)
 288         OSLICE3    // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is untypedchecked or slice; R.Op and R.R.Op==OKEY)
 289         OSLICE3ARR // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is array; R.Op and R.R.Op==OKEY)
 290         ORECOVER   // recover()
 291         ORECV      // <-Left
 292         ORUNESTR   // Type(Left) (Type is string, Left is rune)
 293         OSELRECV   // Left = <-Right.Left: (appears as .Left of OCASE; Right.Op == ORECV)
 294         OSELRECV2  // List = <-Right.Left: (apperas as .Left of OCASE; count(List) == 2, Right.Op == ORECV)
 295         OIOTA      // iota
 296         OREAL      // real(Left)
 297         OIMAG      // imag(Left)
 298         OCOMPLEX   // complex(Left, Right)
 299
 300         // statements
 301         OBLOCK    // { List } (block of code)
 302         OBREAK    // break
 303         OCASE     // case List: Nbody (select case after processing; List==nil means default)
 304         OXCASE    // case List: Nbody (select case before processing; List==nil means default)
 305         OCONTINUE // continue
 306         ODEFER    // defer Left (Left must be call)
 307         OEMPTY    // no-op (empty statement)
 308         OFALL     // fallthrough (after processing)
 309         OXFALL    // fallthrough (before processing)
 310         OFOR      // for Ninit; Left; Right { Nbody }
 311         OGOTO     // goto Left
 312         OIF       // if Ninit; Left { Nbody } else { Rlist }
 313         OLABEL    // Left:
 314         OPROC     // go Left (Left must be call)
 315         ORANGE    // for List = range Right { Nbody }
 316         ORETURN   // return List
 317         OSELECT   // select { List } (List is list of OXCASE or OCASE)
 318         OSWITCH   // switch Ninit; Left { List } (List is a list of OXCASE or OCASE)
 319         OTYPESW   // List = Left.(type) (appears as .Left of OSWITCH)
 320
 321         // types
 322         OTCHAN   // chan int
 323         OTMAP    // map[string]int
 324         OTSTRUCT // struct{}
 325         OTINTER  // interface{}
 326         OTFUNC   // func()
 327         OTARRAY  // []int, [8]int, [N]int or [...]int
 328
 329         // misc
 330         ODDD        // func f(args ...int) or f(l...) or var a = [...]int{0, 1, 2}.
 331         ODDDARG     // func f(args ...int), introduced by escape analysis.
 332         OINLCALL    // intermediary representation of an inlined call.
 333         OEFACE      // itable and data words of an empty-interface value.
 334         OITAB       // itable word of an interface value.
 335         OSPTR       // base pointer of a slice or string.
 336         OCLOSUREVAR // variable reference at beginning of closure function
 337         OCFUNC      // reference to c function pointer (not go func value)
 338         OCHECKNIL   // emit code to ensure pointer/interface not nil
 339         OVARKILL    // variable is dead
 340         OVARLIVE    // variable is alive
 341
 342         // thearch-specific registers
 343         OREGISTER // a register, such as AX.
 344         OINDREG   // offset plus indirect of a register, such as 8(SP).
 345
 346         // arch-specific opcodes
 347         OCMP    // compare: ACMP.
 348         ODEC    // decrement: ADEC.
 349         OINC    // increment: AINC.
 350         OEXTEND // extend: ACWD/ACDQ/ACQO.
 351         OHMUL   // high mul: AMUL/AIMUL for unsigned/signed (OMUL uses AIMUL for both).
 352         OLROT   // left rotate: AROL.
 353         ORROTC  // right rotate-carry: ARCR.
 354         ORETJMP // return to other function
 355         OPS     // compare parity set (for x86 NaN check)
 356         OPC     // compare parity clear (for x86 NaN check)
 357         OSQRT   // sqrt(float64), on systems that have hw support
 358         OGETG   // runtime.getg() (read g pointer)
 359
 360         OEND
 361 )
 362
 363 // A NodeList is a linked list of nodes.
 364 // TODO(rsc): Some uses of NodeList should be made into slices.
 365 // The remaining ones probably just need a simple linked list,
 366 // not one with concatenation support.
 367 type NodeList struct {
 368         N    *Node
 369         Next *NodeList
 370         End  *NodeList
 371 }
 372
 373 // concat returns the concatenation of the lists a and b.
 374 // The storage taken by both is reused for the result.
 375 func concat(a *NodeList, b *NodeList) *NodeList {
 376         if a == nil {
 377                 return b
 378         }
 379         if b == nil {
 380                 return a
 381         }
 382
 383         a.End.Next = b
 384         a.End = b.End
 385         b.End = nil
 386         return a
 387 }
 388
 389 // list1 returns a one-element list containing n.
 390 func list1(n *Node) *NodeList {
 391         if n == nil {
 392                 return nil
 393         }
 394         if n.Op == OBLOCK && n.Ninit == nil {
 395                 // Flatten list and steal storage.
 396                 // Poison pointer to catch errant uses.
 397                 l := n.List
 398
 399                 n.List = nil
 400                 return l
 401         }
 402
 403         l := new(NodeList)
 404         l.N = n
 405         l.End = l
 406         return l
 407 }
 408
 409 // list returns the result of appending n to l.
 410 func list(l *NodeList, n *Node) *NodeList {
 411         return concat(l, list1(n))
 412 }
 413
 414 // listsort sorts *l in place according to the comparison function lt.
 415 // The algorithm expects lt(a, b) to be equivalent to a < b.
 416 // The algorithm is mergesort, so it is guaranteed to be O(n log n).
 417 func listsort(l **NodeList, lt func(*Node, *Node) bool) {
 418         if *l == nil || (*l).Next == nil {
 419                 return
 420         }
 421
 422         l1 := *l
 423         l2 := *l
 424         for {
 425                 l2 = l2.Next
 426                 if l2 == nil {
 427                         break
 428                 }
 429                 l2 = l2.Next
 430                 if l2 == nil {
 431                         break
 432                 }
 433                 l1 = l1.Next
 434         }
 435
 436         l2 = l1.Next
 437         l1.Next = nil
 438         l2.End = (*l).End
 439         (*l).End = l1
 440
 441         l1 = *l
 442         listsort(&l1, lt)
 443         listsort(&l2, lt)
 444
 445         if lt(l1.N, l2.N) {
 446                 *l = l1
 447         } else {
 448                 *l = l2
 449                 l2 = l1
 450                 l1 = *l
 451         }
 452
 453         // now l1 == *l; and l1 < l2
 454
 455         var le *NodeList
 456         for (l1 != nil) && (l2 != nil) {
 457                 for (l1.Next != nil) && lt(l1.Next.N, l2.N) {
 458                         l1 = l1.Next
 459                 }
 460
 461                 // l1 is last one from l1 that is < l2
 462                 le = l1.Next // le is the rest of l1, first one that is >= l2
 463                 if le != nil {
 464                         le.End = (*l).End
 465                 }
 466
 467                 (*l).End = l1       // cut *l at l1
 468                 *l = concat(*l, l2) // glue l2 to *l's tail
 469
 470                 l1 = l2 // l1 is the first element of *l that is < the new l2
 471                 l2 = le // ... because l2 now is the old tail of l1
 472         }
 473
 474         *l = concat(*l, l2) // any remainder
 475 }
 476
 477 // count returns the length of the list l.
 478 func count(l *NodeList) int {
 479         n := int64(0)
 480         for ; l != nil; l = l.Next {
 481                 n++
 482         }
 483         if int64(int(n)) != n { // Overflow.
 484                 Yyerror("too many elements in list")
 485         }
 486         return int(n)
 487 }
 488
 489 // Nodes is a pointer to a slice of *Node.
 490 // For fields that are not used in most nodes, this is used instead of
 491 // a slice to save space.
 492 type Nodes struct{ slice *[]*Node }
 493
 494 // Slice returns the entries in Nodes as a slice.
 495 // Changes to the slice entries (as in s[i] = n) will be reflected in
 496 // the Nodes.
 497 func (n *Nodes) Slice() []*Node {
 498         if n.slice == nil {
 499                 return nil
 500         }
 501         return *n.slice
 502 }
 503
 504 // NodeList returns the entries in Nodes as a NodeList.
 505 // Changes to the NodeList entries (as in l.N = n) will *not* be
 506 // reflect in the Nodes.
 507 // This wastes memory and should be used as little as possible.
 508 func (n *Nodes) NodeList() *NodeList {
 509         if n.slice == nil {
 510                 return nil
 511         }
 512         var ret *NodeList
 513         for _, n := range *n.slice {
 514                 ret = list(ret, n)
 515         }
 516         return ret
 517 }
 518
 519 // Set sets Nodes to a slice.
 520 // This takes ownership of the slice.
 521 func (n *Nodes) Set(s []*Node) {
 522         if len(s) == 0 {
 523                 n.slice = nil
 524         } else {
 525                 n.slice = &s
 526         }
 527 }
 528
 529 // Append appends entries to Nodes.
 530 // If a slice is passed in, this will take ownership of it.
 531 func (n *Nodes) Append(a ...*Node) {
 532         if n.slice == nil {
 533                 if len(a) > 0 {
 534                         n.slice = &a
 535                 }
 536         } else {
 537                 *n.slice = append(*n.slice, a...)
 538         }
 539 }