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