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  	"sort"
    13  
    14  	"cmd/compile/internal/base"
    15  	"cmd/compile/internal/types"
    16  	"cmd/internal/src"
    17  )
    18  
    19  // A Node is the abstract interface to an IR node.
    20  type Node interface {
    21  	// Formatting
    22  	Format(s fmt.State, verb rune)
    23  
    24  	// Source position.
    25  	Pos() src.XPos
    26  	SetPos(x src.XPos)
    27  
    28  	// For making copies. For Copy and SepCopy.
    29  	copy() Node
    30  
    31  	doChildren(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  	OGETCALLERPC // runtime.getcallerpc() (continuation PC in caller frame)
   307  	OGETCALLERSP // runtime.getcallersp() (stack pointer in caller frame)
   308  
   309  	OEND
   310  )
   311  
   312  // IsCmp reports whether op is a comparison operation (==, !=, <, <=,
   313  // >, or >=).
   314  func (op Op) IsCmp() bool {
   315  	switch op {
   316  	case OEQ, ONE, OLT, OLE, OGT, OGE:
   317  		return true
   318  	}
   319  	return false
   320  }
   321  
   322  // Nodes is a slice of Node.
   323  type Nodes []Node
   324  
   325  // ToNodes returns s as a slice of Nodes.
   326  func ToNodes[T Node](s []T) Nodes {
   327  	res := make(Nodes, len(s))
   328  	for i, n := range s {
   329  		res[i] = n
   330  	}
   331  	return res
   332  }
   333  
   334  // Append appends entries to Nodes.
   335  func (n *Nodes) Append(a ...Node) {
   336  	if len(a) == 0 {
   337  		return
   338  	}
   339  	*n = append(*n, a...)
   340  }
   341  
   342  // Prepend prepends entries to Nodes.
   343  // If a slice is passed in, this will take ownership of it.
   344  func (n *Nodes) Prepend(a ...Node) {
   345  	if len(a) == 0 {
   346  		return
   347  	}
   348  	*n = append(a, *n...)
   349  }
   350  
   351  // Take clears n, returning its former contents.
   352  func (n *Nodes) Take() []Node {
   353  	ret := *n
   354  	*n = nil
   355  	return ret
   356  }
   357  
   358  // Copy returns a copy of the content of the slice.
   359  func (n Nodes) Copy() Nodes {
   360  	if n == nil {
   361  		return nil
   362  	}
   363  	c := make(Nodes, len(n))
   364  	copy(c, n)
   365  	return c
   366  }
   367  
   368  // NameQueue is a FIFO queue of *Name. The zero value of NameQueue is
   369  // a ready-to-use empty queue.
   370  type NameQueue struct {
   371  	ring       []*Name
   372  	head, tail int
   373  }
   374  
   375  // Empty reports whether q contains no Names.
   376  func (q *NameQueue) Empty() bool {
   377  	return q.head == q.tail
   378  }
   379  
   380  // PushRight appends n to the right of the queue.
   381  func (q *NameQueue) PushRight(n *Name) {
   382  	if len(q.ring) == 0 {
   383  		q.ring = make([]*Name, 16)
   384  	} else if q.head+len(q.ring) == q.tail {
   385  		// Grow the ring.
   386  		nring := make([]*Name, len(q.ring)*2)
   387  		// Copy the old elements.
   388  		part := q.ring[q.head%len(q.ring):]
   389  		if q.tail-q.head <= len(part) {
   390  			part = part[:q.tail-q.head]
   391  			copy(nring, part)
   392  		} else {
   393  			pos := copy(nring, part)
   394  			copy(nring[pos:], q.ring[:q.tail%len(q.ring)])
   395  		}
   396  		q.ring, q.head, q.tail = nring, 0, q.tail-q.head
   397  	}
   398  
   399  	q.ring[q.tail%len(q.ring)] = n
   400  	q.tail++
   401  }
   402  
   403  // PopLeft pops a Name from the left of the queue. It panics if q is
   404  // empty.
   405  func (q *NameQueue) PopLeft() *Name {
   406  	if q.Empty() {
   407  		panic("dequeue empty")
   408  	}
   409  	n := q.ring[q.head%len(q.ring)]
   410  	q.head++
   411  	return n
   412  }
   413  
   414  // NameSet is a set of Names.
   415  type NameSet map[*Name]struct{}
   416  
   417  // Has reports whether s contains n.
   418  func (s NameSet) Has(n *Name) bool {
   419  	_, isPresent := s[n]
   420  	return isPresent
   421  }
   422  
   423  // Add adds n to s.
   424  func (s *NameSet) Add(n *Name) {
   425  	if *s == nil {
   426  		*s = make(map[*Name]struct{})
   427  	}
   428  	(*s)[n] = struct{}{}
   429  }
   430  
   431  // Sorted returns s sorted according to less.
   432  func (s NameSet) Sorted(less func(*Name, *Name) bool) []*Name {
   433  	var res []*Name
   434  	for n := range s {
   435  		res = append(res, n)
   436  	}
   437  	sort.Slice(res, func(i, j int) bool { return less(res[i], res[j]) })
   438  	return res
   439  }
   440  
   441  type PragmaFlag uint16
   442  
   443  const (
   444  	// Func pragmas.
   445  	Nointerface      PragmaFlag = 1 << iota
   446  	Noescape                    // func parameters don't escape
   447  	Norace                      // func must not have race detector annotations
   448  	Nosplit                     // func should not execute on separate stack
   449  	Noinline                    // func should not be inlined
   450  	NoCheckPtr                  // func should not be instrumented by checkptr
   451  	CgoUnsafeArgs               // treat a pointer to one arg as a pointer to them all
   452  	UintptrKeepAlive            // pointers converted to uintptr must be kept alive
   453  	UintptrEscapes              // pointers converted to uintptr escape
   454  
   455  	// Runtime-only func pragmas.
   456  	// See ../../../../runtime/HACKING.md for detailed descriptions.
   457  	Systemstack        // func must run on system stack
   458  	Nowritebarrier     // emit compiler error instead of write barrier
   459  	Nowritebarrierrec  // error on write barrier in this or recursive callees
   460  	Yeswritebarrierrec // cancels Nowritebarrierrec in this function and callees
   461  
   462  	// Go command pragmas
   463  	GoBuildPragma
   464  
   465  	RegisterParams // TODO(register args) remove after register abi is working
   466  
   467  )
   468  
   469  var BlankNode *Name
   470  
   471  func IsConst(n Node, ct constant.Kind) bool {
   472  	return ConstType(n) == ct
   473  }
   474  
   475  // IsNil reports whether n represents the universal untyped zero value "nil".
   476  func IsNil(n Node) bool {
   477  	return n != nil && n.Op() == ONIL
   478  }
   479  
   480  func IsBlank(n Node) bool {
   481  	if n == nil {
   482  		return false
   483  	}
   484  	return n.Sym().IsBlank()
   485  }
   486  
   487  // IsMethod reports whether n is a method.
   488  // n must be a function or a method.
   489  func IsMethod(n Node) bool {
   490  	return n.Type().Recv() != nil
   491  }
   492  
   493  // HasUniquePos reports whether n has a unique position that can be
   494  // used for reporting error messages.
   495  //
   496  // It's primarily used to distinguish references to named objects,
   497  // whose Pos will point back to their declaration position rather than
   498  // their usage position.
   499  func HasUniquePos(n Node) bool {
   500  	switch n.Op() {
   501  	case ONAME:
   502  		return false
   503  	case OLITERAL, ONIL, OTYPE:
   504  		if n.Sym() != nil {
   505  			return false
   506  		}
   507  	}
   508  
   509  	if !n.Pos().IsKnown() {
   510  		if base.Flag.K != 0 {
   511  			base.Warn("setlineno: unknown position (line 0)")
   512  		}
   513  		return false
   514  	}
   515  
   516  	return true
   517  }
   518  
   519  func SetPos(n Node) src.XPos {
   520  	lno := base.Pos
   521  	if n != nil && HasUniquePos(n) {
   522  		base.Pos = n.Pos()
   523  	}
   524  	return lno
   525  }
   526  
   527  // The result of InitExpr MUST be assigned back to n, e.g.
   528  //
   529  //	n.X = InitExpr(init, n.X)
   530  func InitExpr(init []Node, expr Node) Node {
   531  	if len(init) == 0 {
   532  		return expr
   533  	}
   534  
   535  	n, ok := expr.(InitNode)
   536  	if !ok || MayBeShared(n) {
   537  		// Introduce OCONVNOP to hold init list.
   538  		n = NewConvExpr(base.Pos, OCONVNOP, nil, expr)
   539  		n.SetType(expr.Type())
   540  		n.SetTypecheck(1)
   541  	}
   542  
   543  	n.PtrInit().Prepend(init...)
   544  	return n
   545  }
   546  
   547  // what's the outer value that a write to n affects?
   548  // outer value means containing struct or array.
   549  func OuterValue(n Node) Node {
   550  	for {
   551  		switch nn := n; nn.Op() {
   552  		case OXDOT:
   553  			base.FatalfAt(n.Pos(), "OXDOT in OuterValue: %v", n)
   554  		case ODOT:
   555  			nn := nn.(*SelectorExpr)
   556  			n = nn.X
   557  			continue
   558  		case OPAREN:
   559  			nn := nn.(*ParenExpr)
   560  			n = nn.X
   561  			continue
   562  		case OCONVNOP:
   563  			nn := nn.(*ConvExpr)
   564  			n = nn.X
   565  			continue
   566  		case OINDEX:
   567  			nn := nn.(*IndexExpr)
   568  			if nn.X.Type() == nil {
   569  				base.Fatalf("OuterValue needs type for %v", nn.X)
   570  			}
   571  			if nn.X.Type().IsArray() {
   572  				n = nn.X
   573  				continue
   574  			}
   575  		}
   576  
   577  		return n
   578  	}
   579  }
   580  
   581  const (
   582  	EscUnknown = iota
   583  	EscNone    // Does not escape to heap, result, or parameters.
   584  	EscHeap    // Reachable from the heap
   585  	EscNever   // By construction will not escape.
   586  )
   587
View as plain text