diff options
Diffstat (limited to 'src/cmd/compile/internal/ir/node.go')
| -rw-r--r-- | src/cmd/compile/internal/ir/node.go | 591 |
1 files changed, 591 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ir/node.go b/src/cmd/compile/internal/ir/node.go new file mode 100644 index 0000000000..ffa7daf6b2 --- /dev/null +++ b/src/cmd/compile/internal/ir/node.go @@ -0,0 +1,591 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// “Abstract” syntax representation. + +package ir + +import ( + "fmt" + "go/constant" + "sort" + + "cmd/compile/internal/base" + "cmd/compile/internal/types" + "cmd/internal/src" +) + +// A Node is the abstract interface to an IR node. +type Node interface { + // Formatting + Format(s fmt.State, verb rune) + + // Source position. + Pos() src.XPos + SetPos(x src.XPos) + + // For making copies. For Copy and SepCopy. + copy() Node + + doChildren(func(Node) bool) bool + editChildren(func(Node) Node) + + // Abstract graph structure, for generic traversals. + Op() Op + Init() Nodes + + // Fields specific to certain Ops only. + Type() *types.Type + SetType(t *types.Type) + Name() *Name + Sym() *types.Sym + Val() constant.Value + SetVal(v constant.Value) + + // Storage for analysis passes. + Esc() uint16 + SetEsc(x uint16) + Diag() bool + SetDiag(x bool) + Typecheck() uint8 + SetTypecheck(x uint8) + NonNil() bool + MarkNonNil() +} + +// Line returns n's position as a string. If n has been inlined, +// it uses the outermost position where n has been inlined. +func Line(n Node) string { + return base.FmtPos(n.Pos()) +} + +func IsSynthetic(n Node) bool { + name := n.Sym().Name + return name[0] == '.' || name[0] == '~' +} + +// IsAutoTmp indicates if n was created by the compiler as a temporary, +// based on the setting of the .AutoTemp flag in n's Name. +func IsAutoTmp(n Node) bool { + if n == nil || n.Op() != ONAME { + return false + } + return n.Name().AutoTemp() +} + +// mayBeShared reports whether n may occur in multiple places in the AST. +// Extra care must be taken when mutating such a node. +func MayBeShared(n Node) bool { + switch n.Op() { + case ONAME, OLITERAL, ONIL, OTYPE: + return true + } + return false +} + +type InitNode interface { + Node + PtrInit() *Nodes + SetInit(x Nodes) +} + +func TakeInit(n Node) Nodes { + init := n.Init() + if len(init) != 0 { + n.(InitNode).SetInit(nil) + } + return init +} + +//go:generate stringer -type=Op -trimprefix=O node.go + +type Op uint8 + +// Node ops. +const ( + OXXX Op = iota + + // names + ONAME // var or func name + // Unnamed arg or return value: f(int, string) (int, error) { etc } + // Also used for a qualified package identifier that hasn't been resolved yet. + ONONAME + OTYPE // type name + OPACK // import + OLITERAL // literal + ONIL // nil + + // expressions + OADD // Left + Right + OSUB // Left - Right + OOR // Left | Right + OXOR // Left ^ Right + OADDSTR // +{List} (string addition, list elements are strings) + OADDR // &Left + OANDAND // Left && Right + OAPPEND // append(List); after walk, Left may contain elem type descriptor + OBYTES2STR // Type(Left) (Type is string, Left is a []byte) + OBYTES2STRTMP // Type(Left) (Type is string, Left is a []byte, ephemeral) + ORUNES2STR // Type(Left) (Type is string, Left is a []rune) + OSTR2BYTES // Type(Left) (Type is []byte, Left is a string) + OSTR2BYTESTMP // Type(Left) (Type is []byte, Left is a string, ephemeral) + OSTR2RUNES // Type(Left) (Type is []rune, Left is a string) + // Left = Right or (if Colas=true) Left := Right + // If Colas, then Ninit includes a DCL node for Left. + OAS + // List = Rlist (x, y, z = a, b, c) or (if Colas=true) List := Rlist + // If Colas, then Ninit includes DCL nodes for List + OAS2 + OAS2DOTTYPE // List = Right (x, ok = I.(int)) + OAS2FUNC // List = Right (x, y = f()) + OAS2MAPR // List = Right (x, ok = m["foo"]) + OAS2RECV // List = Right (x, ok = <-c) + OASOP // Left Etype= Right (x += y) + OCALL // Left(List) (function call, method call or type conversion) + + // OCALLFUNC, OCALLMETH, and OCALLINTER have the same structure. + // Prior to walk, they are: Left(List), where List is all regular arguments. + // After walk, List is a series of assignments to temporaries, + // and Rlist is an updated set of arguments. + // Nbody is all OVARLIVE nodes that are attached to OCALLxxx. + // TODO(josharian/khr): Use Ninit instead of List for the assignments to temporaries. See CL 114797. + OCALLFUNC // Left(List/Rlist) (function call f(args)) + OCALLMETH // Left(List/Rlist) (direct method call x.Method(args)) + OCALLINTER // Left(List/Rlist) (interface method call x.Method(args)) + OCALLPART // Left.Right (method expression x.Method, not called) + OCAP // cap(Left) + OCLOSE // close(Left) + OCLOSURE // func Type { Func.Closure.Nbody } (func literal) + OCOMPLIT // Right{List} (composite literal, not yet lowered to specific form) + OMAPLIT // Type{List} (composite literal, Type is map) + OSTRUCTLIT // Type{List} (composite literal, Type is struct) + OARRAYLIT // Type{List} (composite literal, Type is array) + OSLICELIT // Type{List} (composite literal, Type is slice) Right.Int64() = slice length. + OPTRLIT // &Left (left is composite literal) + OCONV // Type(Left) (type conversion) + OCONVIFACE // Type(Left) (type conversion, to interface) + OCONVNOP // Type(Left) (type conversion, no effect) + OCOPY // copy(Left, Right) + ODCL // var Left (declares Left of type Left.Type) + + // Used during parsing but don't last. + ODCLFUNC // func f() or func (r) f() + ODCLCONST // const pi = 3.14 + ODCLTYPE // type Int int or type Int = int + + ODELETE // delete(List) + ODOT // Left.Sym (Left is of struct type) + ODOTPTR // Left.Sym (Left is of pointer to struct type) + ODOTMETH // Left.Sym (Left is non-interface, Right is method name) + ODOTINTER // Left.Sym (Left is interface, Right is method name) + OXDOT // Left.Sym (before rewrite to one of the preceding) + ODOTTYPE // Left.Right or Left.Type (.Right during parsing, .Type once resolved); after walk, .Right contains address of interface type descriptor and .Right.Right contains address of concrete type descriptor + ODOTTYPE2 // Left.Right or Left.Type (.Right during parsing, .Type once resolved; on rhs of OAS2DOTTYPE); after walk, .Right contains address of interface type descriptor + OEQ // Left == Right + ONE // Left != Right + OLT // Left < Right + OLE // Left <= Right + OGE // Left >= Right + OGT // Left > Right + ODEREF // *Left + OINDEX // Left[Right] (index of array or slice) + OINDEXMAP // Left[Right] (index of map) + OKEY // Left:Right (key:value in struct/array/map literal) + OSTRUCTKEY // Sym:Left (key:value in struct literal, after type checking) + OLEN // len(Left) + OMAKE // make(List) (before type checking converts to one of the following) + OMAKECHAN // make(Type, Left) (type is chan) + OMAKEMAP // make(Type, Left) (type is map) + OMAKESLICE // make(Type, Left, Right) (type is slice) + OMAKESLICECOPY // makeslicecopy(Type, Left, Right) (type is slice; Left is length and Right is the copied from slice) + // OMAKESLICECOPY is created by the order pass and corresponds to: + // s = make(Type, Left); copy(s, Right) + // + // Bounded can be set on the node when Left == len(Right) is known at compile time. + // + // This node is created so the walk pass can optimize this pattern which would + // otherwise be hard to detect after the order pass. + OMUL // Left * Right + ODIV // Left / Right + OMOD // Left % Right + OLSH // Left << Right + ORSH // Left >> Right + OAND // Left & Right + OANDNOT // Left &^ Right + ONEW // new(Left); corresponds to calls to new in source code + ONOT // !Left + OBITNOT // ^Left + OPLUS // +Left + ONEG // -Left + OOROR // Left || Right + OPANIC // panic(Left) + OPRINT // print(List) + OPRINTN // println(List) + OPAREN // (Left) + OSEND // Left <- Right + OSLICE // Left[List[0] : List[1]] (Left is untypechecked or slice) + OSLICEARR // Left[List[0] : List[1]] (Left is pointer to array) + OSLICESTR // Left[List[0] : List[1]] (Left is string) + OSLICE3 // Left[List[0] : List[1] : List[2]] (Left is untypedchecked or slice) + OSLICE3ARR // Left[List[0] : List[1] : List[2]] (Left is pointer to array) + OSLICEHEADER // sliceheader{Left, List[0], List[1]} (Left is unsafe.Pointer, List[0] is length, List[1] is capacity) + ORECOVER // recover() + ORECV // <-Left + ORUNESTR // Type(Left) (Type is string, Left is rune) + OSELRECV2 // like OAS2: List = Rlist where len(List)=2, len(Rlist)=1, Rlist[0].Op = ORECV (appears as .Left of OCASE) + OIOTA // iota + OREAL // real(Left) + OIMAG // imag(Left) + OCOMPLEX // complex(Left, Right) or complex(List[0]) where List[0] is a 2-result function call + OALIGNOF // unsafe.Alignof(Left) + OOFFSETOF // unsafe.Offsetof(Left) + OSIZEOF // unsafe.Sizeof(Left) + OMETHEXPR // method expression + OSTMTEXPR // statement expression (Init; Left) + + // statements + OBLOCK // { List } (block of code) + OBREAK // break [Sym] + // OCASE: case List: Nbody (List==nil means default) + // For OTYPESW, List is a OTYPE node for the specified type (or OLITERAL + // for nil), and, if a type-switch variable is specified, Rlist is an + // ONAME for the version of the type-switch variable with the specified + // type. + OCASE + OCONTINUE // continue [Sym] + ODEFER // defer Left (Left must be call) + OFALL // fallthrough + OFOR // for Ninit; Left; Right { Nbody } + // OFORUNTIL is like OFOR, but the test (Left) is applied after the body: + // Ninit + // top: { Nbody } // Execute the body at least once + // cont: Right + // if Left { // And then test the loop condition + // List // Before looping to top, execute List + // goto top + // } + // OFORUNTIL is created by walk. There's no way to write this in Go code. + OFORUNTIL + OGOTO // goto Sym + OIF // if Ninit; Left { Nbody } else { Rlist } + OLABEL // Sym: + OGO // go Left (Left must be call) + ORANGE // for List = range Right { Nbody } + ORETURN // return List + OSELECT // select { List } (List is list of OCASE) + OSWITCH // switch Ninit; Left { List } (List is a list of OCASE) + // OTYPESW: Left := Right.(type) (appears as .Left of OSWITCH) + // Left is nil if there is no type-switch variable + OTYPESW + + // types + OTCHAN // chan int + OTMAP // map[string]int + OTSTRUCT // struct{} + OTINTER // interface{} + // OTFUNC: func() - Left is receiver field, List is list of param fields, Rlist is + // list of result fields. + OTFUNC + OTARRAY // [8]int or [...]int + OTSLICE // []int + + // misc + // intermediate representation of an inlined call. Uses Init (assignments + // for the captured variables, parameters, retvars, & INLMARK op), + // Body (body of the inlined function), and ReturnVars (list of + // return values) + OINLCALL // intermediary representation of an inlined call. + OEFACE // itable and data words of an empty-interface value. + OITAB // itable word of an interface value. + OIDATA // data word of an interface value in Left + OSPTR // base pointer of a slice or string. + OCFUNC // reference to c function pointer (not go func value) + OCHECKNIL // emit code to ensure pointer/interface not nil + OVARDEF // variable is about to be fully initialized + OVARKILL // variable is dead + OVARLIVE // variable is alive + ORESULT // result of a function call; Xoffset is stack offset + OINLMARK // start of an inlined body, with file/line of caller. Xoffset is an index into the inline tree. + OLINKSYMOFFSET // offset within a name + + // arch-specific opcodes + OTAILCALL // tail call to another function + OGETG // runtime.getg() (read g pointer) + + OEND +) + +// Nodes is a pointer to a slice of *Node. +// For fields that are not used in most nodes, this is used instead of +// a slice to save space. +type Nodes []Node + +// Append appends entries to Nodes. +func (n *Nodes) Append(a ...Node) { + if len(a) == 0 { + return + } + *n = append(*n, a...) +} + +// Prepend prepends entries to Nodes. +// If a slice is passed in, this will take ownership of it. +func (n *Nodes) Prepend(a ...Node) { + if len(a) == 0 { + return + } + *n = append(a, *n...) +} + +// Take clears n, returning its former contents. +func (n *Nodes) Take() []Node { + ret := *n + *n = nil + return ret +} + +// Copy returns a copy of the content of the slice. +func (n Nodes) Copy() Nodes { + if n == nil { + return nil + } + c := make(Nodes, len(n)) + copy(c, n) + return c +} + +// NameQueue is a FIFO queue of *Name. The zero value of NameQueue is +// a ready-to-use empty queue. +type NameQueue struct { + ring []*Name + head, tail int +} + +// Empty reports whether q contains no Names. +func (q *NameQueue) Empty() bool { + return q.head == q.tail +} + +// PushRight appends n to the right of the queue. +func (q *NameQueue) PushRight(n *Name) { + if len(q.ring) == 0 { + q.ring = make([]*Name, 16) + } else if q.head+len(q.ring) == q.tail { + // Grow the ring. + nring := make([]*Name, len(q.ring)*2) + // Copy the old elements. + part := q.ring[q.head%len(q.ring):] + if q.tail-q.head <= len(part) { + part = part[:q.tail-q.head] + copy(nring, part) + } else { + pos := copy(nring, part) + copy(nring[pos:], q.ring[:q.tail%len(q.ring)]) + } + q.ring, q.head, q.tail = nring, 0, q.tail-q.head + } + + q.ring[q.tail%len(q.ring)] = n + q.tail++ +} + +// PopLeft pops a Name from the left of the queue. It panics if q is +// empty. +func (q *NameQueue) PopLeft() *Name { + if q.Empty() { + panic("dequeue empty") + } + n := q.ring[q.head%len(q.ring)] + q.head++ + return n +} + +// NameSet is a set of Names. +type NameSet map[*Name]struct{} + +// Has reports whether s contains n. +func (s NameSet) Has(n *Name) bool { + _, isPresent := s[n] + return isPresent +} + +// Add adds n to s. +func (s *NameSet) Add(n *Name) { + if *s == nil { + *s = make(map[*Name]struct{}) + } + (*s)[n] = struct{}{} +} + +// Sorted returns s sorted according to less. +func (s NameSet) Sorted(less func(*Name, *Name) bool) []*Name { + var res []*Name + for n := range s { + res = append(res, n) + } + sort.Slice(res, func(i, j int) bool { return less(res[i], res[j]) }) + return res +} + +type PragmaFlag int16 + +const ( + // Func pragmas. + Nointerface PragmaFlag = 1 << iota + Noescape // func parameters don't escape + Norace // func must not have race detector annotations + Nosplit // func should not execute on separate stack + Noinline // func should not be inlined + NoCheckPtr // func should not be instrumented by checkptr + CgoUnsafeArgs // treat a pointer to one arg as a pointer to them all + UintptrEscapes // pointers converted to uintptr escape + + // Runtime-only func pragmas. + // See ../../../../runtime/README.md for detailed descriptions. + Systemstack // func must run on system stack + Nowritebarrier // emit compiler error instead of write barrier + Nowritebarrierrec // error on write barrier in this or recursive callees + Yeswritebarrierrec // cancels Nowritebarrierrec in this function and callees + + // Runtime and cgo type pragmas + NotInHeap // values of this type must not be heap allocated + + // Go command pragmas + GoBuildPragma + + RegisterParams // TODO remove after register abi is working + +) + +func AsNode(n types.Object) Node { + if n == nil { + return nil + } + return n.(Node) +} + +var BlankNode Node + +func IsConst(n Node, ct constant.Kind) bool { + return ConstType(n) == ct +} + +// isNil reports whether n represents the universal untyped zero value "nil". +func IsNil(n Node) bool { + // Check n.Orig because constant propagation may produce typed nil constants, + // which don't exist in the Go spec. + return n != nil && Orig(n).Op() == ONIL +} + +func IsBlank(n Node) bool { + if n == nil { + return false + } + return n.Sym().IsBlank() +} + +// IsMethod reports whether n is a method. +// n must be a function or a method. +func IsMethod(n Node) bool { + return n.Type().Recv() != nil +} + +func HasNamedResults(fn *Func) bool { + typ := fn.Type() + return typ.NumResults() > 0 && types.OrigSym(typ.Results().Field(0).Sym) != nil +} + +// HasUniquePos reports whether n has a unique position that can be +// used for reporting error messages. +// +// It's primarily used to distinguish references to named objects, +// whose Pos will point back to their declaration position rather than +// their usage position. +func HasUniquePos(n Node) bool { + switch n.Op() { + case ONAME, OPACK: + return false + case OLITERAL, ONIL, OTYPE: + if n.Sym() != nil { + return false + } + } + + if !n.Pos().IsKnown() { + if base.Flag.K != 0 { + base.Warn("setlineno: unknown position (line 0)") + } + return false + } + + return true +} + +func SetPos(n Node) src.XPos { + lno := base.Pos + if n != nil && HasUniquePos(n) { + base.Pos = n.Pos() + } + return lno +} + +// The result of InitExpr MUST be assigned back to n, e.g. +// n.Left = InitExpr(init, n.Left) +func InitExpr(init []Node, expr Node) Node { + if len(init) == 0 { + return expr + } + + n, ok := expr.(InitNode) + if !ok || MayBeShared(n) { + // Introduce OCONVNOP to hold init list. + n = NewConvExpr(base.Pos, OCONVNOP, nil, expr) + n.SetType(expr.Type()) + n.SetTypecheck(1) + } + + n.PtrInit().Prepend(init...) + return n +} + +// what's the outer value that a write to n affects? +// outer value means containing struct or array. +func OuterValue(n Node) Node { + for { + switch nn := n; nn.Op() { + case OXDOT: + base.Fatalf("OXDOT in walk") + case ODOT: + nn := nn.(*SelectorExpr) + n = nn.X + continue + case OPAREN: + nn := nn.(*ParenExpr) + n = nn.X + continue + case OCONVNOP: + nn := nn.(*ConvExpr) + n = nn.X + continue + case OINDEX: + nn := nn.(*IndexExpr) + if nn.X.Type() == nil { + base.Fatalf("OuterValue needs type for %v", nn.X) + } + if nn.X.Type().IsArray() { + n = nn.X + continue + } + } + + return n + } +} + +const ( + EscUnknown = iota + EscNone // Does not escape to heap, result, or parameters. + EscHeap // Reachable from the heap + EscNever // By construction will not escape. +) |