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          uint8
  46         Nointerface bool
  47         Ullman      uint8 // sethi/ullman number
  48         Addable     bool  // addressable
  49         Etype       uint8 // op for OASOP, etype for OTYPE, exclam for export, 6g saved reg
  50         Bounded     bool  // bounds check unnecessary
  51         Class       uint8 // 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 }
 132
 133 type Param struct {
 134         Ntype *Node
 135
 136         // ONAME func param with PHEAP
 137         Outerexpr  *Node // expression copied into closure for variable
 138         Stackparam *Node // OPARAM node referring to stack copy of param
 139
 140         // ONAME PPARAM
 141         Field *Type // TFIELD in arg struct
 142
 143         // ONAME closure param with PPARAMREF
 144         Outer   *Node // outer PPARAMREF in nested closure
 145         Closure *Node // ONAME/PHEAP <-> ONAME/PPARAMREF
 146 }
 147
 148 // Func holds Node fields used only with function-like nodes.
 149 type Func struct {
 150         Shortname  *Node
 151         Enter      *NodeList // for example, allocate and initialize memory for escaping parameters
 152         Exit       *NodeList
 153         Cvars      *NodeList // closure params
 154         Dcl        *NodeList // autodcl for this func/closure
 155         Inldcl     *NodeList // copy of dcl for use in inlining
 156         Closgen    int
 157         Outerfunc  *Node
 158         Fieldtrack []*Type
 159         Outer      *Node // outer func for closure
 160         Ntype      *Node // signature
 161         Top        int   // top context (Ecall, Eproc, etc)
 162         Closure    *Node // OCLOSURE <-> ODCLFUNC
 163         FCurfn     *Node
 164         Nname      *Node
 165
 166         Inl     *NodeList // copy of the body for use in inlining
 167         InlCost int32
 168         Depth   int32
 169
 170         Endlineno int32
 171
 172         Norace         bool // func must not have race detector annotations
 173         Nosplit        bool // func should not execute on separate stack
 174         Nowritebarrier bool // emit compiler error instead of write barrier
 175         Dupok          bool // duplicate definitions ok
 176         Wrapper        bool // is method wrapper
 177         Needctxt       bool // function uses context register (has closure variables)
 178         Systemstack    bool // must run on system stack
 179 }
 180
 181 // Node ops.
 182 const (
 183         OXXX = iota
 184
 185         // names
 186         ONAME    // var, const or func name
 187         ONONAME  // unnamed arg or return value: f(int, string) (int, error) { etc }
 188         OTYPE    // type name
 189         OPACK    // import
 190         OLITERAL // literal
 191
 192         // expressions
 193         OADD             // Left + Right
 194         OSUB             // Left - Right
 195         OOR              // Left | Right
 196         OXOR             // Left ^ Right
 197         OADDSTR          // Left + Right (string addition)
 198         OADDR            // &Left
 199         OANDAND          // Left && Right
 200         OAPPEND          // append(List)
 201         OARRAYBYTESTR    // Type(Left) (Type is string, Left is a []byte)
 202         OARRAYBYTESTRTMP // Type(Left) (Type is string, Left is a []byte, ephemeral)
 203         OARRAYRUNESTR    // Type(Left) (Type is string, Left is a []rune)
 204         OSTRARRAYBYTE    // Type(Left) (Type is []byte, Left is a string)
 205         OSTRARRAYBYTETMP // Type(Left) (Type is []byte, Left is a string, ephemeral)
 206         OSTRARRAYRUNE    // Type(Left) (Type is []rune, Left is a string)
 207         OAS              // Left = Right or (if Colas=true) Left := Right
 208         OAS2             // List = Rlist (x, y, z = a, b, c)
 209         OAS2FUNC         // List = Rlist (x, y = f())
 210         OAS2RECV         // List = Rlist (x, ok = <-c)
 211         OAS2MAPR         // List = Rlist (x, ok = m["foo"])
 212         OAS2DOTTYPE      // List = Rlist (x, ok = I.(int))
 213         OASOP            // Left Etype= Right (x += y)
 214         OASWB            // Left = Right (with write barrier)
 215         OCALL            // Left(List) (function call, method call or type conversion)
 216         OCALLFUNC        // Left(List) (function call f(args))
 217         OCALLMETH        // Left(List) (direct method call x.Method(args))
 218         OCALLINTER       // Left(List) (interface method call x.Method(args))
 219         OCALLPART        // Left.Right (method expression x.Method, not called)
 220         OCAP             // cap(Left)
 221         OCLOSE           // close(Left)
 222         OCLOSURE         // func Type { Body } (func literal)
 223         OCMPIFACE        // Left Etype Right (interface comparison, x == y or x != y)
 224         OCMPSTR          // Left Etype Right (string comparison, x == y, x < y, etc)
 225         OCOMPLIT         // Right{List} (composite literal, not yet lowered to specific form)
 226         OMAPLIT          // Type{List} (composite literal, Type is map)
 227         OSTRUCTLIT       // Type{List} (composite literal, Type is struct)
 228         OARRAYLIT        // Type{List} (composite literal, Type is array or slice)
 229         OPTRLIT          // &Left (left is composite literal)
 230         OCONV            // Type(Left) (type conversion)
 231         OCONVIFACE       // Type(Left) (type conversion, to interface)
 232         OCONVNOP         // Type(Left) (type conversion, no effect)
 233         OCOPY            // copy(Left, Right)
 234         ODCL             // var Left (declares Left of type Left.Type)
 235
 236         // Used during parsing but don't last.
 237         ODCLFUNC  // func f() or func (r) f()
 238         ODCLFIELD // struct field, interface field, or func/method argument/return value.
 239         ODCLCONST // const pi = 3.14
 240         ODCLTYPE  // type Int int
 241
 242         ODELETE    // delete(Left, Right)
 243         ODOT       // Left.Right (Left is of struct type)
 244         ODOTPTR    // Left.Right (Left is of pointer to struct type)
 245         ODOTMETH   // Left.Right (Left is non-interface, Right is method name)
 246         ODOTINTER  // Left.Right (Left is interface, Right is method name)
 247         OXDOT      // Left.Right (before rewrite to one of the preceding)
 248         ODOTTYPE   // Left.Right or Left.Type (.Right during parsing, .Type once resolved)
 249         ODOTTYPE2  // Left.Right or Left.Type (.Right during parsing, .Type once resolved; on rhs of OAS2DOTTYPE)
 250         OEQ        // Left == Right
 251         ONE        // Left != Right
 252         OLT        // Left < Right
 253         OLE        // Left <= Right
 254         OGE        // Left >= Right
 255         OGT        // Left > Right
 256         OIND       // *Left
 257         OINDEX     // Left[Right] (index of array or slice)
 258         OINDEXMAP  // Left[Right] (index of map)
 259         OKEY       // Left:Right (key:value in struct/array/map literal, or slice index pair)
 260         OPARAM     // variant of ONAME for on-stack copy of a parameter or return value that escapes.
 261         OLEN       // len(Left)
 262         OMAKE      // make(List) (before type checking converts to one of the following)
 263         OMAKECHAN  // make(Type, Left) (type is chan)
 264         OMAKEMAP   // make(Type, Left) (type is map)
 265         OMAKESLICE // make(Type, Left, Right) (type is slice)
 266         OMUL       // Left * Right
 267         ODIV       // Left / Right
 268         OMOD       // Left % Right
 269         OLSH       // Left << Right
 270         ORSH       // Left >> Right
 271         OAND       // Left & Right
 272         OANDNOT    // Left &^ Right
 273         ONEW       // new(Left)
 274         ONOT       // !Left
 275         OCOM       // ^Left
 276         OPLUS      // +Left
 277         OMINUS     // -Left
 278         OOROR      // Left || Right
 279         OPANIC     // panic(Left)
 280         OPRINT     // print(List)
 281         OPRINTN    // println(List)
 282         OPAREN     // (Left)
 283         OSEND      // Left <- Right
 284         OSLICE     // Left[Right.Left : Right.Right] (Left is untypechecked or slice; Right.Op==OKEY)
 285         OSLICEARR  // Left[Right.Left : Right.Right] (Left is array)
 286         OSLICESTR  // Left[Right.Left : Right.Right] (Left is string)
 287         OSLICE3    // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is untypedchecked or slice; R.Op and R.R.Op==OKEY)
 288         OSLICE3ARR // Left[R.Left : R.R.Left : R.R.R] (R=Right; Left is array; R.Op and R.R.Op==OKEY)
 289         ORECOVER   // recover()
 290         ORECV      // <-Left
 291         ORUNESTR   // Type(Left) (Type is string, Left is rune)
 292         OSELRECV   // Left = <-Right.Left: (appears as .Left of OCASE; Right.Op == ORECV)
 293         OSELRECV2  // List = <-Right.Left: (apperas as .Left of OCASE; count(List) == 2, Right.Op == ORECV)
 294         OIOTA      // iota
 295         OREAL      // real(Left)
 296         OIMAG      // imag(Left)
 297         OCOMPLEX   // complex(Left, Right)
 298
 299         // statements
 300         OBLOCK    // { List } (block of code)
 301         OBREAK    // break
 302         OCASE     // case List: Nbody (select case after processing; List==nil means default)
 303         OXCASE    // case List: Nbody (select case before processing; List==nil means default)
 304         OCONTINUE // continue
 305         ODEFER    // defer Left (Left must be call)
 306         OEMPTY    // no-op (empty statement)
 307         OFALL     // fallthrough (after processing)
 308         OXFALL    // fallthrough (before processing)
 309         OFOR      // for Ninit; Left; Right { Nbody }
 310         OGOTO     // goto Left
 311         OIF       // if Ninit; Left { Nbody } else { Rlist }
 312         OLABEL    // Left:
 313         OPROC     // go Left (Left must be call)
 314         ORANGE    // for List = range Right { Nbody }
 315         ORETURN   // return List
 316         OSELECT   // select { List } (List is list of OXCASE or OCASE)
 317         OSWITCH   // switch Ninit; Left { List } (List is a list of OXCASE or OCASE)
 318         OTYPESW   // List = Left.(type) (appears as .Left of OSWITCH)
 319
 320         // types
 321         OTCHAN   // chan int
 322         OTMAP    // map[string]int
 323         OTSTRUCT // struct{}
 324         OTINTER  // interface{}
 325         OTFUNC   // func()
 326         OTARRAY  // []int, [8]int, [N]int or [...]int
 327
 328         // misc
 329         ODDD        // func f(args ...int) or f(l...) or var a = [...]int{0, 1, 2}.
 330         ODDDARG     // func f(args ...int), introduced by escape analysis.
 331         OINLCALL    // intermediary representation of an inlined call.
 332         OEFACE      // itable and data words of an empty-interface value.
 333         OITAB       // itable word of an interface value.
 334         OSPTR       // base pointer of a slice or string.
 335         OCLOSUREVAR // variable reference at beginning of closure function
 336         OCFUNC      // reference to c function pointer (not go func value)
 337         OCHECKNIL   // emit code to ensure pointer/interface not nil
 338         OVARKILL    // variable is dead
 339
 340         // thearch-specific registers
 341         OREGISTER // a register, such as AX.
 342         OINDREG   // offset plus indirect of a register, such as 8(SP).
 343
 344         // arch-specific opcodes
 345         OCMP    // compare: ACMP.
 346         ODEC    // decrement: ADEC.
 347         OINC    // increment: AINC.
 348         OEXTEND // extend: ACWD/ACDQ/ACQO.
 349         OHMUL   // high mul: AMUL/AIMUL for unsigned/signed (OMUL uses AIMUL for both).
 350         OLROT   // left rotate: AROL.
 351         ORROTC  // right rotate-carry: ARCR.
 352         ORETJMP // return to other function
 353         OPS     // compare parity set (for x86 NaN check)
 354         OPC     // compare parity clear (for x86 NaN check)
 355         OSQRT   // sqrt(float64), on systems that have hw support
 356         OGETG   // runtime.getg() (read g pointer)
 357
 358         OEND
 359 )
 360
 361 // A NodeList is a linked list of nodes.
 362 // TODO(rsc): Some uses of NodeList should be made into slices.
 363 // The remaining ones probably just need a simple linked list,
 364 // not one with concatenation support.
 365 type NodeList struct {
 366         N    *Node
 367         Next *NodeList
 368         End  *NodeList
 369 }
 370
 371 // concat returns the concatenation of the lists a and b.
 372 // The storage taken by both is reused for the result.
 373 func concat(a *NodeList, b *NodeList) *NodeList {
 374         if a == nil {
 375                 return b
 376         }
 377         if b == nil {
 378                 return a
 379         }
 380
 381         a.End.Next = b
 382         a.End = b.End
 383         b.End = nil
 384         return a
 385 }
 386
 387 // list1 returns a one-element list containing n.
 388 func list1(n *Node) *NodeList {
 389         if n == nil {
 390                 return nil
 391         }
 392         if n.Op == OBLOCK && n.Ninit == nil {
 393                 // Flatten list and steal storage.
 394                 // Poison pointer to catch errant uses.
 395                 l := n.List
 396
 397                 n.List = nil
 398                 return l
 399         }
 400
 401         l := new(NodeList)
 402         l.N = n
 403         l.End = l
 404         return l
 405 }
 406
 407 // list returns the result of appending n to l.
 408 func list(l *NodeList, n *Node) *NodeList {
 409         return concat(l, list1(n))
 410 }
 411
 412 // listsort sorts *l in place according to the comparison function lt.
 413 // The algorithm expects lt(a, b) to be equivalent to a < b.
 414 // The algorithm is mergesort, so it is guaranteed to be O(n log n).
 415 func listsort(l **NodeList, lt func(*Node, *Node) bool) {
 416         if *l == nil || (*l).Next == nil {
 417                 return
 418         }
 419
 420         l1 := *l
 421         l2 := *l
 422         for {
 423                 l2 = l2.Next
 424                 if l2 == nil {
 425                         break
 426                 }
 427                 l2 = l2.Next
 428                 if l2 == nil {
 429                         break
 430                 }
 431                 l1 = l1.Next
 432         }
 433
 434         l2 = l1.Next
 435         l1.Next = nil
 436         l2.End = (*l).End
 437         (*l).End = l1
 438
 439         l1 = *l
 440         listsort(&l1, lt)
 441         listsort(&l2, lt)
 442
 443         if lt(l1.N, l2.N) {
 444                 *l = l1
 445         } else {
 446                 *l = l2
 447                 l2 = l1
 448                 l1 = *l
 449         }
 450
 451         // now l1 == *l; and l1 < l2
 452
 453         var le *NodeList
 454         for (l1 != nil) && (l2 != nil) {
 455                 for (l1.Next != nil) && lt(l1.Next.N, l2.N) {
 456                         l1 = l1.Next
 457                 }
 458
 459                 // l1 is last one from l1 that is < l2
 460                 le = l1.Next // le is the rest of l1, first one that is >= l2
 461                 if le != nil {
 462                         le.End = (*l).End
 463                 }
 464
 465                 (*l).End = l1       // cut *l at l1
 466                 *l = concat(*l, l2) // glue l2 to *l's tail
 467
 468                 l1 = l2 // l1 is the first element of *l that is < the new l2
 469                 l2 = le // ... because l2 now is the old tail of l1
 470         }
 471
 472         *l = concat(*l, l2) // any remainder
 473 }
 474
 475 // count returns the length of the list l.
 476 func count(l *NodeList) int {
 477         n := int64(0)
 478         for ; l != nil; l = l.Next {
 479                 n++
 480         }
 481         if int64(int(n)) != n { // Overflow.
 482                 Yyerror("too many elements in list")
 483         }
 484         return int(n)
 485 }