node.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 ir
     8  
     9  import (
    10  	"fmt"
    11  	"go/constant"
    12  
    13  	"cmd/compile/internal/base"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/src"
    16  )
    17  
    18  // A Node is the abstract interface to an IR node.
    19  type Node interface {
    20  	// Formatting
    21  	Format(s fmt.State, verb rune)
    22  
    23  	// Source position.
    24  	Pos() src.XPos
    25  	SetPos(x src.XPos)
    26  
    27  	// For making copies. For Copy and SepCopy.
    28  	copy() Node
    29  
    30  	doChildren(func(Node) bool) bool
    31  	doChildrenWithHidden(func(Node) bool) bool
    32  	editChildren(func(Node) Node)
    33  	editChildrenWithHidden(func(Node) Node)
    34  
    35  	// Abstract graph structure, for generic traversals.
    36  	Op() Op
    37  	Init() Nodes
    38  
    39  	// Fields specific to certain Ops only.
    40  	Type() *types.Type
    41  	SetType(t *types.Type)
    42  	Name() *Name
    43  	Sym() *types.Sym
    44  	Val() constant.Value
    45  	SetVal(v constant.Value)
    46  
    47  	// Storage for analysis passes.
    48  	Esc() uint16
    49  	SetEsc(x uint16)
    50  
    51  	// Typecheck values:
    52  	//  0 means the node is not typechecked
    53  	//  1 means the node is completely typechecked
    54  	//  2 means typechecking of the node is in progress
    55  	Typecheck() uint8
    56  	SetTypecheck(x uint8)
    57  	NonNil() bool
    58  	MarkNonNil()
    59  }
    60  
    61  // Line returns n's position as a string. If n has been inlined,
    62  // it uses the outermost position where n has been inlined.
    63  func Line(n Node) string {
    64  	return base.FmtPos(n.Pos())
    65  }
    66  
    67  func IsSynthetic(n Node) bool {
    68  	name := n.Sym().Name
    69  	return name[0] == '.' || name[0] == '~'
    70  }
    71  
    72  // IsAutoTmp indicates if n was created by the compiler as a temporary,
    73  // based on the setting of the .AutoTemp flag in n's Name.
    74  func IsAutoTmp(n Node) bool {
    75  	if n == nil || n.Op() != ONAME {
    76  		return false
    77  	}
    78  	return n.Name().AutoTemp()
    79  }
    80  
    81  // MayBeShared reports whether n may occur in multiple places in the AST.
    82  // Extra care must be taken when mutating such a node.
    83  func MayBeShared(n Node) bool {
    84  	switch n.Op() {
    85  	case ONAME, OLITERAL, ONIL, OTYPE:
    86  		return true
    87  	}
    88  	return false
    89  }
    90  
    91  type InitNode interface {
    92  	Node
    93  	PtrInit() *Nodes
    94  	SetInit(x Nodes)
    95  }
    96  
    97  func TakeInit(n Node) Nodes {
    98  	init := n.Init()
    99  	if len(init) != 0 {
   100  		n.(InitNode).SetInit(nil)
   101  	}
   102  	return init
   103  }
   104  
   105  //go:generate stringer -type=Op -trimprefix=O node.go
   106  
   107  type Op uint8
   108  
   109  // Node ops.
   110  const (
   111  	OXXX Op = iota
   112  
   113  	// names
   114  	ONAME // var or func name
   115  	// Unnamed arg or return value: f(int, string) (int, error) { etc }
   116  	// Also used for a qualified package identifier that hasn't been resolved yet.
   117  	ONONAME
   118  	OTYPE    // type name
   119  	OLITERAL // literal
   120  	ONIL     // nil
   121  
   122  	// expressions
   123  	OADD          // X + Y
   124  	OSUB          // X - Y
   125  	OOR           // X | Y
   126  	OXOR          // X ^ Y
   127  	OADDSTR       // +{List} (string addition, list elements are strings)
   128  	OADDR         // &X
   129  	OANDAND       // X && Y
   130  	OAPPEND       // append(Args); after walk, X may contain elem type descriptor
   131  	OBYTES2STR    // Type(X) (Type is string, X is a []byte)
   132  	OBYTES2STRTMP // Type(X) (Type is string, X is a []byte, ephemeral)
   133  	ORUNES2STR    // Type(X) (Type is string, X is a []rune)
   134  	OSTR2BYTES    // Type(X) (Type is []byte, X is a string)
   135  	OSTR2BYTESTMP // Type(X) (Type is []byte, X is a string, ephemeral)
   136  	OSTR2RUNES    // Type(X) (Type is []rune, X is a string)
   137  	OSLICE2ARR    // Type(X) (Type is [N]T, X is a []T)
   138  	OSLICE2ARRPTR // Type(X) (Type is *[N]T, X is a []T)
   139  	// X = Y or (if Def=true) X := Y
   140  	// If Def, then Init includes a DCL node for X.
   141  	OAS
   142  	// Lhs = Rhs (x, y, z = a, b, c) or (if Def=true) Lhs := Rhs
   143  	// If Def, then Init includes DCL nodes for Lhs
   144  	OAS2
   145  	OAS2DOTTYPE // Lhs = Rhs (x, ok = I.(int))
   146  	OAS2FUNC    // Lhs = Rhs (x, y = f())
   147  	OAS2MAPR    // Lhs = Rhs (x, ok = m["foo"])
   148  	OAS2RECV    // Lhs = Rhs (x, ok = <-c)
   149  	OASOP       // X AsOp= Y (x += y)
   150  	OCALL       // X(Args) (function call, method call or type conversion)
   151  
   152  	// OCALLFUNC, OCALLMETH, and OCALLINTER have the same structure.
   153  	// Prior to walk, they are: X(Args), where Args is all regular arguments.
   154  	// After walk, if any argument whose evaluation might requires temporary variable,
   155  	// that temporary variable will be pushed to Init, Args will contain an updated
   156  	// set of arguments.
   157  	OCALLFUNC  // X(Args) (function call f(args))
   158  	OCALLMETH  // X(Args) (direct method call x.Method(args))
   159  	OCALLINTER // X(Args) (interface method call x.Method(args))
   160  	OCAP       // cap(X)
   161  	OCLEAR     // clear(X)
   162  	OCLOSE     // close(X)
   163  	OCLOSURE   // func Type { Func.Closure.Body } (func literal)
   164  	OCOMPLIT   // Type{List} (composite literal, not yet lowered to specific form)
   165  	OMAPLIT    // Type{List} (composite literal, Type is map)
   166  	OSTRUCTLIT // Type{List} (composite literal, Type is struct)
   167  	OARRAYLIT  // Type{List} (composite literal, Type is array)
   168  	OSLICELIT  // Type{List} (composite literal, Type is slice), Len is slice length.
   169  	OPTRLIT    // &X (X is composite literal)
   170  	OCONV      // Type(X) (type conversion)
   171  	OCONVIFACE // Type(X) (type conversion, to interface)
   172  	OCONVNOP   // Type(X) (type conversion, no effect)
   173  	OCOPY      // copy(X, Y)
   174  	ODCL       // var X (declares X of type X.Type)
   175  
   176  	// Used during parsing but don't last.
   177  	ODCLFUNC // func f() or func (r) f()
   178  
   179  	ODELETE        // delete(Args)
   180  	ODOT           // X.Sel (X is of struct type)
   181  	ODOTPTR        // X.Sel (X is of pointer to struct type)
   182  	ODOTMETH       // X.Sel (X is non-interface, Sel is method name)
   183  	ODOTINTER      // X.Sel (X is interface, Sel is method name)
   184  	OXDOT          // X.Sel (before rewrite to one of the preceding)
   185  	ODOTTYPE       // X.Ntype or X.Type (.Ntype during parsing, .Type once resolved); after walk, Itab contains address of interface type descriptor and Itab.X contains address of concrete type descriptor
   186  	ODOTTYPE2      // X.Ntype or X.Type (.Ntype during parsing, .Type once resolved; on rhs of OAS2DOTTYPE); after walk, Itab contains address of interface type descriptor
   187  	OEQ            // X == Y
   188  	ONE            // X != Y
   189  	OLT            // X < Y
   190  	OLE            // X <= Y
   191  	OGE            // X >= Y
   192  	OGT            // X > Y
   193  	ODEREF         // *X
   194  	OINDEX         // X[Index] (index of array or slice)
   195  	OINDEXMAP      // X[Index] (index of map)
   196  	OKEY           // Key:Value (key:value in struct/array/map literal)
   197  	OSTRUCTKEY     // Field:Value (key:value in struct literal, after type checking)
   198  	OLEN           // len(X)
   199  	OMAKE          // make(Args) (before type checking converts to one of the following)
   200  	OMAKECHAN      // make(Type[, Len]) (type is chan)
   201  	OMAKEMAP       // make(Type[, Len]) (type is map)
   202  	OMAKESLICE     // make(Type[, Len[, Cap]]) (type is slice)
   203  	OMAKESLICECOPY // makeslicecopy(Type, Len, Cap) (type is slice; Len is length and Cap is the copied from slice)
   204  	// OMAKESLICECOPY is created by the order pass and corresponds to:
   205  	//  s = make(Type, Len); copy(s, Cap)
   206  	//
   207  	// Bounded can be set on the node when Len == len(Cap) is known at compile time.
   208  	//
   209  	// This node is created so the walk pass can optimize this pattern which would
   210  	// otherwise be hard to detect after the order pass.
   211  	OMUL              // X * Y
   212  	ODIV              // X / Y
   213  	OMOD              // X % Y
   214  	OLSH              // X << Y
   215  	ORSH              // X >> Y
   216  	OAND              // X & Y
   217  	OANDNOT           // X &^ Y
   218  	ONEW              // new(X); corresponds to calls to new in source code
   219  	ONOT              // !X
   220  	OBITNOT           // ^X
   221  	OPLUS             // +X
   222  	ONEG              // -X
   223  	OOROR             // X || Y
   224  	OPANIC            // panic(X)
   225  	OPRINT            // print(List)
   226  	OPRINTLN          // println(List)
   227  	OPAREN            // (X)
   228  	OSEND             // Chan <- Value
   229  	OSLICE            // X[Low : High] (X is untypechecked or slice)
   230  	OSLICEARR         // X[Low : High] (X is pointer to array)
   231  	OSLICESTR         // X[Low : High] (X is string)
   232  	OSLICE3           // X[Low : High : Max] (X is untypedchecked or slice)
   233  	OSLICE3ARR        // X[Low : High : Max] (X is pointer to array)
   234  	OSLICEHEADER      // sliceheader{Ptr, Len, Cap} (Ptr is unsafe.Pointer, Len is length, Cap is capacity)
   235  	OSTRINGHEADER     // stringheader{Ptr, Len} (Ptr is unsafe.Pointer, Len is length)
   236  	ORECOVER          // recover()
   237  	ORECV             // <-X
   238  	ORUNESTR          // Type(X) (Type is string, X is rune)
   239  	OSELRECV2         // like OAS2: Lhs = Rhs where len(Lhs)=2, len(Rhs)=1, Rhs[0].Op = ORECV (appears as .Var of OCASE)
   240  	OMIN              // min(List)
   241  	OMAX              // max(List)
   242  	OREAL             // real(X)
   243  	OIMAG             // imag(X)
   244  	OCOMPLEX          // complex(X, Y)
   245  	OUNSAFEADD        // unsafe.Add(X, Y)
   246  	OUNSAFESLICE      // unsafe.Slice(X, Y)
   247  	OUNSAFESLICEDATA  // unsafe.SliceData(X)
   248  	OUNSAFESTRING     // unsafe.String(X, Y)
   249  	OUNSAFESTRINGDATA // unsafe.StringData(X)
   250  	OMETHEXPR         // X(Args) (method expression T.Method(args), first argument is the method receiver)
   251  	OMETHVALUE        // X.Sel   (method expression t.Method, not called)
   252  
   253  	// statements
   254  	OBLOCK // { List } (block of code)
   255  	OBREAK // break [Label]
   256  	// OCASE:  case List: Body (List==nil means default)
   257  	//   For OTYPESW, List is a OTYPE node for the specified type (or OLITERAL
   258  	//   for nil) or an ODYNAMICTYPE indicating a runtime type for generics.
   259  	//   If a type-switch variable is specified, Var is an
   260  	//   ONAME for the version of the type-switch variable with the specified
   261  	//   type.
   262  	OCASE
   263  	OCONTINUE // continue [Label]
   264  	ODEFER    // defer Call
   265  	OFALL     // fallthrough
   266  	OFOR      // for Init; Cond; Post { Body }
   267  	OGOTO     // goto Label
   268  	OIF       // if Init; Cond { Then } else { Else }
   269  	OLABEL    // Label:
   270  	OGO       // go Call
   271  	ORANGE    // for Key, Value = range X { Body }
   272  	ORETURN   // return Results
   273  	OSELECT   // select { Cases }
   274  	OSWITCH   // switch Init; Expr { Cases }
   275  	// OTYPESW:  X := Y.(type) (appears as .Tag of OSWITCH)
   276  	//   X is nil if there is no type-switch variable
   277  	OTYPESW
   278  
   279  	// misc
   280  	// intermediate representation of an inlined call.  Uses Init (assignments
   281  	// for the captured variables, parameters, retvars, & INLMARK op),
   282  	// Body (body of the inlined function), and ReturnVars (list of
   283  	// return values)
   284  	OINLCALL         // intermediary representation of an inlined call.
   285  	OMAKEFACE        // construct an interface value from rtype/itab and data pointers
   286  	OITAB            // rtype/itab pointer of an interface value
   287  	OIDATA           // data pointer of an interface value
   288  	OSPTR            // base pointer of a slice or string. Bounded==1 means known non-nil.
   289  	OCFUNC           // reference to c function pointer (not go func value)
   290  	OCHECKNIL        // emit code to ensure pointer/interface not nil
   291  	ORESULT          // result of a function call; Xoffset is stack offset
   292  	OINLMARK         // start of an inlined body, with file/line of caller. Xoffset is an index into the inline tree.
   293  	OLINKSYMOFFSET   // offset within a name
   294  	OJUMPTABLE       // A jump table structure for implementing dense expression switches
   295  	OINTERFACESWITCH // A type switch with interface cases
   296  
   297  	// opcodes for generics
   298  	ODYNAMICDOTTYPE  // x = i.(T) where T is a type parameter (or derived from a type parameter)
   299  	ODYNAMICDOTTYPE2 // x, ok = i.(T) where T is a type parameter (or derived from a type parameter)
   300  	ODYNAMICTYPE     // a type node for type switches (represents a dynamic target type for a type switch)
   301  
   302  	// arch-specific opcodes
   303  	OTAILCALL    // tail call to another function
   304  	OGETG        // runtime.getg() (read g pointer)
   305  	OGETCALLERSP // internal/runtime/sys.GetCallerSP() (stack pointer in caller frame)
   306  
   307  	OEND
   308  )
   309  
   310  // IsCmp reports whether op is a comparison operation (==, !=, <, <=,
   311  // >, or >=).
   312  func (op Op) IsCmp() bool {
   313  	switch op {
   314  	case OEQ, ONE, OLT, OLE, OGT, OGE:
   315  		return true
   316  	}
   317  	return false
   318  }
   319  
   320  // Nodes is a slice of Node.
   321  type Nodes []Node
   322  
   323  // ToNodes returns s as a slice of Nodes.
   324  func ToNodes[T Node](s []T) Nodes {
   325  	res := make(Nodes, len(s))
   326  	for i, n := range s {
   327  		res[i] = n
   328  	}
   329  	return res
   330  }
   331  
   332  // Append appends entries to Nodes.
   333  func (n *Nodes) Append(a ...Node) {
   334  	if len(a) == 0 {
   335  		return
   336  	}
   337  	*n = append(*n, a...)
   338  }
   339  
   340  // Prepend prepends entries to Nodes.
   341  // If a slice is passed in, this will take ownership of it.
   342  func (n *Nodes) Prepend(a ...Node) {
   343  	if len(a) == 0 {
   344  		return
   345  	}
   346  	*n = append(a, *n...)
   347  }
   348  
   349  // Take clears n, returning its former contents.
   350  func (n *Nodes) Take() []Node {
   351  	ret := *n
   352  	*n = nil
   353  	return ret
   354  }
   355  
   356  // Copy returns a copy of the content of the slice.
   357  func (n Nodes) Copy() Nodes {
   358  	if n == nil {
   359  		return nil
   360  	}
   361  	c := make(Nodes, len(n))
   362  	copy(c, n)
   363  	return c
   364  }
   365  
   366  // NameQueue is a FIFO queue of *Name. The zero value of NameQueue is
   367  // a ready-to-use empty queue.
   368  type NameQueue struct {
   369  	ring       []*Name
   370  	head, tail int
   371  }
   372  
   373  // Empty reports whether q contains no Names.
   374  func (q *NameQueue) Empty() bool {
   375  	return q.head == q.tail
   376  }
   377  
   378  // PushRight appends n to the right of the queue.
   379  func (q *NameQueue) PushRight(n *Name) {
   380  	if len(q.ring) == 0 {
   381  		q.ring = make([]*Name, 16)
   382  	} else if q.head+len(q.ring) == q.tail {
   383  		// Grow the ring.
   384  		nring := make([]*Name, len(q.ring)*2)
   385  		// Copy the old elements.
   386  		part := q.ring[q.head%len(q.ring):]
   387  		if q.tail-q.head <= len(part) {
   388  			part = part[:q.tail-q.head]
   389  			copy(nring, part)
   390  		} else {
   391  			pos := copy(nring, part)
   392  			copy(nring[pos:], q.ring[:q.tail%len(q.ring)])
   393  		}
   394  		q.ring, q.head, q.tail = nring, 0, q.tail-q.head
   395  	}
   396  
   397  	q.ring[q.tail%len(q.ring)] = n
   398  	q.tail++
   399  }
   400  
   401  // PopLeft pops a Name from the left of the queue. It panics if q is
   402  // empty.
   403  func (q *NameQueue) PopLeft() *Name {
   404  	if q.Empty() {
   405  		panic("dequeue empty")
   406  	}
   407  	n := q.ring[q.head%len(q.ring)]
   408  	q.head++
   409  	return n
   410  }
   411  
   412  // NameSet is a set of Names.
   413  type NameSet map[*Name]struct{}
   414  
   415  // Has reports whether s contains n.
   416  func (s NameSet) Has(n *Name) bool {
   417  	_, isPresent := s[n]
   418  	return isPresent
   419  }
   420  
   421  // Add adds n to s.
   422  func (s *NameSet) Add(n *Name) {
   423  	if *s == nil {
   424  		*s = make(map[*Name]struct{})
   425  	}
   426  	(*s)[n] = struct{}{}
   427  }
   428  
   429  type PragmaFlag uint16
   430  
   431  const (
   432  	// Func pragmas.
   433  	Nointerface      PragmaFlag = 1 << iota
   434  	Noescape                    // func parameters don't escape
   435  	Norace                      // func must not have race detector annotations
   436  	Nosplit                     // func should not execute on separate stack
   437  	Noinline                    // func should not be inlined
   438  	NoCheckPtr                  // func should not be instrumented by checkptr
   439  	CgoUnsafeArgs               // treat a pointer to one arg as a pointer to them all
   440  	UintptrKeepAlive            // pointers converted to uintptr must be kept alive
   441  	UintptrEscapes              // pointers converted to uintptr escape
   442  
   443  	// Runtime-only func pragmas.
   444  	// See ../../../../runtime/HACKING.md for detailed descriptions.
   445  	Systemstack        // func must run on system stack
   446  	Nowritebarrier     // emit compiler error instead of write barrier
   447  	Nowritebarrierrec  // error on write barrier in this or recursive callees
   448  	Yeswritebarrierrec // cancels Nowritebarrierrec in this function and callees
   449  
   450  	// Go command pragmas
   451  	GoBuildPragma
   452  
   453  	RegisterParams // TODO(register args) remove after register abi is working
   454  
   455  )
   456  
   457  var BlankNode *Name
   458  
   459  func IsConst(n Node, ct constant.Kind) bool {
   460  	return ConstType(n) == ct
   461  }
   462  
   463  // IsNil reports whether n represents the universal untyped zero value "nil".
   464  func IsNil(n Node) bool {
   465  	return n != nil && n.Op() == ONIL
   466  }
   467  
   468  func IsBlank(n Node) bool {
   469  	if n == nil {
   470  		return false
   471  	}
   472  	return n.Sym().IsBlank()
   473  }
   474  
   475  // IsMethod reports whether n is a method.
   476  // n must be a function or a method.
   477  func IsMethod(n Node) bool {
   478  	return n.Type().Recv() != nil
   479  }
   480  
   481  // HasUniquePos reports whether n has a unique position that can be
   482  // used for reporting error messages.
   483  //
   484  // It's primarily used to distinguish references to named objects,
   485  // whose Pos will point back to their declaration position rather than
   486  // their usage position.
   487  func HasUniquePos(n Node) bool {
   488  	switch n.Op() {
   489  	case ONAME:
   490  		return false
   491  	case OLITERAL, ONIL, OTYPE:
   492  		if n.Sym() != nil {
   493  			return false
   494  		}
   495  	}
   496  
   497  	if !n.Pos().IsKnown() {
   498  		if base.Flag.K != 0 {
   499  			base.Warn("setlineno: unknown position (line 0)")
   500  		}
   501  		return false
   502  	}
   503  
   504  	return true
   505  }
   506  
   507  func SetPos(n Node) src.XPos {
   508  	lno := base.Pos
   509  	if n != nil && HasUniquePos(n) {
   510  		base.Pos = n.Pos()
   511  	}
   512  	return lno
   513  }
   514  
   515  // The result of InitExpr MUST be assigned back to n, e.g.
   516  //
   517  //	n.X = InitExpr(init, n.X)
   518  func InitExpr(init []Node, expr Node) Node {
   519  	if len(init) == 0 {
   520  		return expr
   521  	}
   522  
   523  	n, ok := expr.(InitNode)
   524  	if !ok || MayBeShared(n) {
   525  		// Introduce OCONVNOP to hold init list.
   526  		n = NewConvExpr(base.Pos, OCONVNOP, nil, expr)
   527  		n.SetType(expr.Type())
   528  		n.SetTypecheck(1)
   529  	}
   530  
   531  	n.PtrInit().Prepend(init...)
   532  	return n
   533  }
   534  
   535  // what's the outer value that a write to n affects?
   536  // outer value means containing struct or array.
   537  func OuterValue(n Node) Node {
   538  	for {
   539  		switch nn := n; nn.Op() {
   540  		case OXDOT:
   541  			base.FatalfAt(n.Pos(), "OXDOT in OuterValue: %v", n)
   542  		case ODOT:
   543  			nn := nn.(*SelectorExpr)
   544  			n = nn.X
   545  			continue
   546  		case OPAREN:
   547  			nn := nn.(*ParenExpr)
   548  			n = nn.X
   549  			continue
   550  		case OCONVNOP:
   551  			nn := nn.(*ConvExpr)
   552  			n = nn.X
   553  			continue
   554  		case OINDEX:
   555  			nn := nn.(*IndexExpr)
   556  			if nn.X.Type() == nil {
   557  				base.Fatalf("OuterValue needs type for %v", nn.X)
   558  			}
   559  			if nn.X.Type().IsArray() {
   560  				n = nn.X
   561  				continue
   562  			}
   563  		}
   564  
   565  		return n
   566  	}
   567  }
   568  
   569  const (
   570  	EscUnknown = iota
   571  	EscNone    // Does not escape to heap, result, or parameters.
   572  	EscHeap    // Reachable from the heap
   573  	EscNever   // By construction will not escape.
   574  )
   575
View as plain text