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  	ORECOVERFP        // recover(Args) w/ explicit FP argument
   238  	ORECV             // <-X
   239  	ORUNESTR          // Type(X) (Type is string, X is rune)
   240  	OSELRECV2         // like OAS2: Lhs = Rhs where len(Lhs)=2, len(Rhs)=1, Rhs[0].Op = ORECV (appears as .Var of OCASE)
   241  	OMIN              // min(List)
   242  	OMAX              // max(List)
   243  	OREAL             // real(X)
   244  	OIMAG             // imag(X)
   245  	OCOMPLEX          // complex(X, Y)
   246  	OUNSAFEADD        // unsafe.Add(X, Y)
   247  	OUNSAFESLICE      // unsafe.Slice(X, Y)
   248  	OUNSAFESLICEDATA  // unsafe.SliceData(X)
   249  	OUNSAFESTRING     // unsafe.String(X, Y)
   250  	OUNSAFESTRINGDATA // unsafe.StringData(X)
   251  	OMETHEXPR         // X(Args) (method expression T.Method(args), first argument is the method receiver)
   252  	OMETHVALUE        // X.Sel   (method expression t.Method, not called)
   253  
   254  	// statements
   255  	OBLOCK // { List } (block of code)
   256  	OBREAK // break [Label]
   257  	// OCASE:  case List: Body (List==nil means default)
   258  	//   For OTYPESW, List is a OTYPE node for the specified type (or OLITERAL
   259  	//   for nil) or an ODYNAMICTYPE indicating a runtime type for generics.
   260  	//   If a type-switch variable is specified, Var is an
   261  	//   ONAME for the version of the type-switch variable with the specified
   262  	//   type.
   263  	OCASE
   264  	OCONTINUE // continue [Label]
   265  	ODEFER    // defer Call
   266  	OFALL     // fallthrough
   267  	OFOR      // for Init; Cond; Post { Body }
   268  	OGOTO     // goto Label
   269  	OIF       // if Init; Cond { Then } else { Else }
   270  	OLABEL    // Label:
   271  	OGO       // go Call
   272  	ORANGE    // for Key, Value = range X { Body }
   273  	ORETURN   // return Results
   274  	OSELECT   // select { Cases }
   275  	OSWITCH   // switch Init; Expr { Cases }
   276  	// OTYPESW:  X := Y.(type) (appears as .Tag of OSWITCH)
   277  	//   X is nil if there is no type-switch variable
   278  	OTYPESW
   279  
   280  	// misc
   281  	// intermediate representation of an inlined call.  Uses Init (assignments
   282  	// for the captured variables, parameters, retvars, & INLMARK op),
   283  	// Body (body of the inlined function), and ReturnVars (list of
   284  	// return values)
   285  	OINLCALL         // intermediary representation of an inlined call.
   286  	OMAKEFACE        // construct an interface value from rtype/itab and data pointers
   287  	OITAB            // rtype/itab pointer of an interface value
   288  	OIDATA           // data pointer of an interface value
   289  	OSPTR            // base pointer of a slice or string. Bounded==1 means known non-nil.
   290  	OCFUNC           // reference to c function pointer (not go func value)
   291  	OCHECKNIL        // emit code to ensure pointer/interface not nil
   292  	ORESULT          // result of a function call; Xoffset is stack offset
   293  	OINLMARK         // start of an inlined body, with file/line of caller. Xoffset is an index into the inline tree.
   294  	OLINKSYMOFFSET   // offset within a name
   295  	OJUMPTABLE       // A jump table structure for implementing dense expression switches
   296  	OINTERFACESWITCH // A type switch with interface cases
   297  
   298  	// opcodes for generics
   299  	ODYNAMICDOTTYPE  // x = i.(T) where T is a type parameter (or derived from a type parameter)
   300  	ODYNAMICDOTTYPE2 // x, ok = i.(T) where T is a type parameter (or derived from a type parameter)
   301  	ODYNAMICTYPE     // a type node for type switches (represents a dynamic target type for a type switch)
   302  
   303  	// arch-specific opcodes
   304  	OTAILCALL    // tail call to another function
   305  	OGETG        // runtime.getg() (read g pointer)
   306  	OGETCALLERSP // internal/runtime/sys.GetCallerSP() (stack pointer in caller frame)
   307  
   308  	OEND
   309  )
   310  
   311  // IsCmp reports whether op is a comparison operation (==, !=, <, <=,
   312  // >, or >=).
   313  func (op Op) IsCmp() bool {
   314  	switch op {
   315  	case OEQ, ONE, OLT, OLE, OGT, OGE:
   316  		return true
   317  	}
   318  	return false
   319  }
   320  
   321  // Nodes is a slice of Node.
   322  type Nodes []Node
   323  
   324  // ToNodes returns s as a slice of Nodes.
   325  func ToNodes[T Node](s []T) Nodes {
   326  	res := make(Nodes, len(s))
   327  	for i, n := range s {
   328  		res[i] = n
   329  	}
   330  	return res
   331  }
   332  
   333  // Append appends entries to Nodes.
   334  func (n *Nodes) Append(a ...Node) {
   335  	if len(a) == 0 {
   336  		return
   337  	}
   338  	*n = append(*n, a...)
   339  }
   340  
   341  // Prepend prepends entries to Nodes.
   342  // If a slice is passed in, this will take ownership of it.
   343  func (n *Nodes) Prepend(a ...Node) {
   344  	if len(a) == 0 {
   345  		return
   346  	}
   347  	*n = append(a, *n...)
   348  }
   349  
   350  // Take clears n, returning its former contents.
   351  func (n *Nodes) Take() []Node {
   352  	ret := *n
   353  	*n = nil
   354  	return ret
   355  }
   356  
   357  // Copy returns a copy of the content of the slice.
   358  func (n Nodes) Copy() Nodes {
   359  	if n == nil {
   360  		return nil
   361  	}
   362  	c := make(Nodes, len(n))
   363  	copy(c, n)
   364  	return c
   365  }
   366  
   367  // NameQueue is a FIFO queue of *Name. The zero value of NameQueue is
   368  // a ready-to-use empty queue.
   369  type NameQueue struct {
   370  	ring       []*Name
   371  	head, tail int
   372  }
   373  
   374  // Empty reports whether q contains no Names.
   375  func (q *NameQueue) Empty() bool {
   376  	return q.head == q.tail
   377  }
   378  
   379  // PushRight appends n to the right of the queue.
   380  func (q *NameQueue) PushRight(n *Name) {
   381  	if len(q.ring) == 0 {
   382  		q.ring = make([]*Name, 16)
   383  	} else if q.head+len(q.ring) == q.tail {
   384  		// Grow the ring.
   385  		nring := make([]*Name, len(q.ring)*2)
   386  		// Copy the old elements.
   387  		part := q.ring[q.head%len(q.ring):]
   388  		if q.tail-q.head <= len(part) {
   389  			part = part[:q.tail-q.head]
   390  			copy(nring, part)
   391  		} else {
   392  			pos := copy(nring, part)
   393  			copy(nring[pos:], q.ring[:q.tail%len(q.ring)])
   394  		}
   395  		q.ring, q.head, q.tail = nring, 0, q.tail-q.head
   396  	}
   397  
   398  	q.ring[q.tail%len(q.ring)] = n
   399  	q.tail++
   400  }
   401  
   402  // PopLeft pops a Name from the left of the queue. It panics if q is
   403  // empty.
   404  func (q *NameQueue) PopLeft() *Name {
   405  	if q.Empty() {
   406  		panic("dequeue empty")
   407  	}
   408  	n := q.ring[q.head%len(q.ring)]
   409  	q.head++
   410  	return n
   411  }
   412  
   413  // NameSet is a set of Names.
   414  type NameSet map[*Name]struct{}
   415  
   416  // Has reports whether s contains n.
   417  func (s NameSet) Has(n *Name) bool {
   418  	_, isPresent := s[n]
   419  	return isPresent
   420  }
   421  
   422  // Add adds n to s.
   423  func (s *NameSet) Add(n *Name) {
   424  	if *s == nil {
   425  		*s = make(map[*Name]struct{})
   426  	}
   427  	(*s)[n] = struct{}{}
   428  }
   429  
   430  type PragmaFlag uint16
   431  
   432  const (
   433  	// Func pragmas.
   434  	Nointerface      PragmaFlag = 1 << iota
   435  	Noescape                    // func parameters don't escape
   436  	Norace                      // func must not have race detector annotations
   437  	Nosplit                     // func should not execute on separate stack
   438  	Noinline                    // func should not be inlined
   439  	NoCheckPtr                  // func should not be instrumented by checkptr
   440  	CgoUnsafeArgs               // treat a pointer to one arg as a pointer to them all
   441  	UintptrKeepAlive            // pointers converted to uintptr must be kept alive
   442  	UintptrEscapes              // pointers converted to uintptr escape
   443  
   444  	// Runtime-only func pragmas.
   445  	// See ../../../../runtime/HACKING.md for detailed descriptions.
   446  	Systemstack        // func must run on system stack
   447  	Nowritebarrier     // emit compiler error instead of write barrier
   448  	Nowritebarrierrec  // error on write barrier in this or recursive callees
   449  	Yeswritebarrierrec // cancels Nowritebarrierrec in this function and callees
   450  
   451  	// Go command pragmas
   452  	GoBuildPragma
   453  
   454  	RegisterParams // TODO(register args) remove after register abi is working
   455  
   456  )
   457  
   458  var BlankNode *Name
   459  
   460  func IsConst(n Node, ct constant.Kind) bool {
   461  	return ConstType(n) == ct
   462  }
   463  
   464  // IsNil reports whether n represents the universal untyped zero value "nil".
   465  func IsNil(n Node) bool {
   466  	return n != nil && n.Op() == ONIL
   467  }
   468  
   469  func IsBlank(n Node) bool {
   470  	if n == nil {
   471  		return false
   472  	}
   473  	return n.Sym().IsBlank()
   474  }
   475  
   476  // IsMethod reports whether n is a method.
   477  // n must be a function or a method.
   478  func IsMethod(n Node) bool {
   479  	return n.Type().Recv() != nil
   480  }
   481  
   482  // HasUniquePos reports whether n has a unique position that can be
   483  // used for reporting error messages.
   484  //
   485  // It's primarily used to distinguish references to named objects,
   486  // whose Pos will point back to their declaration position rather than
   487  // their usage position.
   488  func HasUniquePos(n Node) bool {
   489  	switch n.Op() {
   490  	case ONAME:
   491  		return false
   492  	case OLITERAL, ONIL, OTYPE:
   493  		if n.Sym() != nil {
   494  			return false
   495  		}
   496  	}
   497  
   498  	if !n.Pos().IsKnown() {
   499  		if base.Flag.K != 0 {
   500  			base.Warn("setlineno: unknown position (line 0)")
   501  		}
   502  		return false
   503  	}
   504  
   505  	return true
   506  }
   507  
   508  func SetPos(n Node) src.XPos {
   509  	lno := base.Pos
   510  	if n != nil && HasUniquePos(n) {
   511  		base.Pos = n.Pos()
   512  	}
   513  	return lno
   514  }
   515  
   516  // The result of InitExpr MUST be assigned back to n, e.g.
   517  //
   518  //	n.X = InitExpr(init, n.X)
   519  func InitExpr(init []Node, expr Node) Node {
   520  	if len(init) == 0 {
   521  		return expr
   522  	}
   523  
   524  	n, ok := expr.(InitNode)
   525  	if !ok || MayBeShared(n) {
   526  		// Introduce OCONVNOP to hold init list.
   527  		n = NewConvExpr(base.Pos, OCONVNOP, nil, expr)
   528  		n.SetType(expr.Type())
   529  		n.SetTypecheck(1)
   530  	}
   531  
   532  	n.PtrInit().Prepend(init...)
   533  	return n
   534  }
   535  
   536  // what's the outer value that a write to n affects?
   537  // outer value means containing struct or array.
   538  func OuterValue(n Node) Node {
   539  	for {
   540  		switch nn := n; nn.Op() {
   541  		case OXDOT:
   542  			base.FatalfAt(n.Pos(), "OXDOT in OuterValue: %v", n)
   543  		case ODOT:
   544  			nn := nn.(*SelectorExpr)
   545  			n = nn.X
   546  			continue
   547  		case OPAREN:
   548  			nn := nn.(*ParenExpr)
   549  			n = nn.X
   550  			continue
   551  		case OCONVNOP:
   552  			nn := nn.(*ConvExpr)
   553  			n = nn.X
   554  			continue
   555  		case OINDEX:
   556  			nn := nn.(*IndexExpr)
   557  			if nn.X.Type() == nil {
   558  				base.Fatalf("OuterValue needs type for %v", nn.X)
   559  			}
   560  			if nn.X.Type().IsArray() {
   561  				n = nn.X
   562  				continue
   563  			}
   564  		}
   565  
   566  		return n
   567  	}
   568  }
   569  
   570  const (
   571  	EscUnknown = iota
   572  	EscNone    // Does not escape to heap, result, or parameters.
   573  	EscHeap    // Reachable from the heap
   574  	EscNever   // By construction will not escape.
   575  )
   576
View as plain text