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 7package ir 8 9import ( 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. 20type 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 34 // Abstract graph structure, for generic traversals. 35 Op() Op 36 Init() Nodes 37 38 // Fields specific to certain Ops only. 39 Type() *types.Type 40 SetType(t *types.Type) 41 Name() *Name 42 Sym() *types.Sym 43 Val() constant.Value 44 SetVal(v constant.Value) 45 46 // Storage for analysis passes. 47 Esc() uint16 48 SetEsc(x uint16) 49 Diag() bool 50 SetDiag(x bool) 51 52 // Typecheck values: 53 // 0 means the node is not typechecked 54 // 1 means the node is completely typechecked 55 // 2 means typechecking of the node is in progress 56 // 3 means the node has its type from types2, but may need transformation 57 Typecheck() uint8 58 SetTypecheck(x uint8) 59 NonNil() bool 60 MarkNonNil() 61} 62 63// Line returns n's position as a string. If n has been inlined, 64// it uses the outermost position where n has been inlined. 65func Line(n Node) string { 66 return base.FmtPos(n.Pos()) 67} 68 69func IsSynthetic(n Node) bool { 70 name := n.Sym().Name 71 return name[0] == '.' || name[0] == '~' 72} 73 74// IsAutoTmp indicates if n was created by the compiler as a temporary, 75// based on the setting of the .AutoTemp flag in n's Name. 76func IsAutoTmp(n Node) bool { 77 if n == nil || n.Op() != ONAME { 78 return false 79 } 80 return n.Name().AutoTemp() 81} 82 83// MayBeShared reports whether n may occur in multiple places in the AST. 84// Extra care must be taken when mutating such a node. 85func MayBeShared(n Node) bool { 86 switch n.Op() { 87 case ONAME, OLITERAL, ONIL, OTYPE: 88 return true 89 } 90 return false 91} 92 93type InitNode interface { 94 Node 95 PtrInit() *Nodes 96 SetInit(x Nodes) 97} 98 99func TakeInit(n Node) Nodes { 100 init := n.Init() 101 if len(init) != 0 { 102 n.(InitNode).SetInit(nil) 103 } 104 return init 105} 106 107//go:generate stringer -type=Op -trimprefix=O node.go 108 109type Op uint8 110 111// Node ops. 112const ( 113 OXXX Op = iota 114 115 // names 116 ONAME // var or func name 117 // Unnamed arg or return value: f(int, string) (int, error) { etc } 118 // Also used for a qualified package identifier that hasn't been resolved yet. 119 ONONAME 120 OTYPE // type name 121 OPACK // import 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 OSLICE2ARRPTR // Type(X) (Type is *[N]T, X is a []T) 141 // X = Y or (if Def=true) X := Y 142 // If Def, then Init includes a DCL node for X. 143 OAS 144 // Lhs = Rhs (x, y, z = a, b, c) or (if Def=true) Lhs := Rhs 145 // If Def, then Init includes DCL nodes for Lhs 146 OAS2 147 OAS2DOTTYPE // Lhs = Rhs (x, ok = I.(int)) 148 OAS2FUNC // Lhs = Rhs (x, y = f()) 149 OAS2MAPR // Lhs = Rhs (x, ok = m["foo"]) 150 OAS2RECV // Lhs = Rhs (x, ok = <-c) 151 OASOP // X AsOp= Y (x += y) 152 OCALL // X(Args) (function call, method call or type conversion) 153 154 // OCALLFUNC, OCALLMETH, and OCALLINTER have the same structure. 155 // Prior to walk, they are: X(Args), where Args is all regular arguments. 156 // After walk, if any argument whose evaluation might requires temporary variable, 157 // that temporary variable will be pushed to Init, Args will contains an updated 158 // set of arguments. KeepAlive is all OVARLIVE nodes that are attached to OCALLxxx. 159 OCALLFUNC // X(Args) (function call f(args)) 160 OCALLMETH // X(Args) (direct method call x.Method(args)) 161 OCALLINTER // X(Args) (interface method call x.Method(args)) 162 OCAP // cap(X) 163 OCLOSE // close(X) 164 OCLOSURE // func Type { Func.Closure.Body } (func literal) 165 OCOMPLIT // Type{List} (composite literal, not yet lowered to specific form) 166 OMAPLIT // Type{List} (composite literal, Type is map) 167 OSTRUCTLIT // Type{List} (composite literal, Type is struct) 168 OARRAYLIT // Type{List} (composite literal, Type is array) 169 OSLICELIT // Type{List} (composite literal, Type is slice), Len is slice length. 170 OPTRLIT // &X (X is composite literal) 171 OCONV // Type(X) (type conversion) 172 OCONVIFACE // Type(X) (type conversion, to interface) 173 OCONVIDATA // Builds a data word to store X in an interface. Equivalent to IDATA(CONVIFACE(X)). Is an ir.ConvExpr. 174 OCONVNOP // Type(X) (type conversion, no effect) 175 OCOPY // copy(X, Y) 176 ODCL // var X (declares X of type X.Type) 177 178 // Used during parsing but don't last. 179 ODCLFUNC // func f() or func (r) f() 180 ODCLCONST // const pi = 3.14 181 ODCLTYPE // type Int int or type Int = int 182 183 ODELETE // delete(Args) 184 ODOT // X.Sel (X is of struct type) 185 ODOTPTR // X.Sel (X is of pointer to struct type) 186 ODOTMETH // X.Sel (X is non-interface, Sel is method name) 187 ODOTINTER // X.Sel (X is interface, Sel is method name) 188 OXDOT // X.Sel (before rewrite to one of the preceding) 189 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 190 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 191 OEQ // X == Y 192 ONE // X != Y 193 OLT // X < Y 194 OLE // X <= Y 195 OGE // X >= Y 196 OGT // X > Y 197 ODEREF // *X 198 OINDEX // X[Index] (index of array or slice) 199 OINDEXMAP // X[Index] (index of map) 200 OKEY // Key:Value (key:value in struct/array/map literal) 201 OSTRUCTKEY // Field:Value (key:value in struct literal, after type checking) 202 OLEN // len(X) 203 OMAKE // make(Args) (before type checking converts to one of the following) 204 OMAKECHAN // make(Type[, Len]) (type is chan) 205 OMAKEMAP // make(Type[, Len]) (type is map) 206 OMAKESLICE // make(Type[, Len[, Cap]]) (type is slice) 207 OMAKESLICECOPY // makeslicecopy(Type, Len, Cap) (type is slice; Len is length and Cap is the copied from slice) 208 // OMAKESLICECOPY is created by the order pass and corresponds to: 209 // s = make(Type, Len); copy(s, Cap) 210 // 211 // Bounded can be set on the node when Len == len(Cap) is known at compile time. 212 // 213 // This node is created so the walk pass can optimize this pattern which would 214 // otherwise be hard to detect after the order pass. 215 OMUL // X * Y 216 ODIV // X / Y 217 OMOD // X % Y 218 OLSH // X << Y 219 ORSH // X >> Y 220 OAND // X & Y 221 OANDNOT // X &^ Y 222 ONEW // new(X); corresponds to calls to new in source code 223 ONOT // !X 224 OBITNOT // ^X 225 OPLUS // +X 226 ONEG // -X 227 OOROR // X || Y 228 OPANIC // panic(X) 229 OPRINT // print(List) 230 OPRINTN // println(List) 231 OPAREN // (X) 232 OSEND // Chan <- Value 233 OSLICE // X[Low : High] (X is untypechecked or slice) 234 OSLICEARR // X[Low : High] (X is pointer to array) 235 OSLICESTR // X[Low : High] (X is string) 236 OSLICE3 // X[Low : High : Max] (X is untypedchecked or slice) 237 OSLICE3ARR // X[Low : High : Max] (X is pointer to array) 238 OSLICEHEADER // sliceheader{Ptr, Len, Cap} (Ptr is unsafe.Pointer, Len is length, Cap is capacity) 239 ORECOVER // recover() 240 ORECOVERFP // recover(Args) w/ explicit FP argument 241 ORECV // <-X 242 ORUNESTR // Type(X) (Type is string, X is rune) 243 OSELRECV2 // like OAS2: Lhs = Rhs where len(Lhs)=2, len(Rhs)=1, Rhs[0].Op = ORECV (appears as .Var of OCASE) 244 OIOTA // iota 245 OREAL // real(X) 246 OIMAG // imag(X) 247 OCOMPLEX // complex(X, Y) 248 OALIGNOF // unsafe.Alignof(X) 249 OOFFSETOF // unsafe.Offsetof(X) 250 OSIZEOF // unsafe.Sizeof(X) 251 OUNSAFEADD // unsafe.Add(X, Y) 252 OUNSAFESLICE // unsafe.Slice(X, Y) 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 // OFORUNTIL is like OFOR, but the test (Cond) is applied after the body: 271 // Init 272 // top: { Body } // Execute the body at least once 273 // cont: Post 274 // if Cond { // And then test the loop condition 275 // List // Before looping to top, execute List 276 // goto top 277 // } 278 // OFORUNTIL is created by walk. There's no way to write this in Go code. 279 OFORUNTIL 280 OGOTO // goto Label 281 OIF // if Init; Cond { Then } else { Else } 282 OLABEL // Label: 283 OGO // go Call 284 ORANGE // for Key, Value = range X { Body } 285 ORETURN // return Results 286 OSELECT // select { Cases } 287 OSWITCH // switch Init; Expr { Cases } 288 // OTYPESW: X := Y.(type) (appears as .Tag of OSWITCH) 289 // X is nil if there is no type-switch variable 290 OTYPESW 291 OFUNCINST // instantiation of a generic function 292 293 // types 294 OTCHAN // chan int 295 OTMAP // map[string]int 296 OTSTRUCT // struct{} 297 OTINTER // interface{} 298 // OTFUNC: func() - Recv is receiver field, Params is list of param fields, Results is 299 // list of result fields. 300 OTFUNC 301 OTARRAY // [8]int or [...]int 302 OTSLICE // []int 303 304 // misc 305 // intermediate representation of an inlined call. Uses Init (assignments 306 // for the captured variables, parameters, retvars, & INLMARK op), 307 // Body (body of the inlined function), and ReturnVars (list of 308 // return values) 309 OINLCALL // intermediary representation of an inlined call. 310 OEFACE // itable and data words of an empty-interface value. 311 OITAB // itable word of an interface value. 312 OIDATA // data word of an interface value in X 313 OSPTR // base pointer of a slice or string. 314 OCFUNC // reference to c function pointer (not go func value) 315 OCHECKNIL // emit code to ensure pointer/interface not nil 316 OVARDEF // variable is about to be fully initialized 317 OVARKILL // variable is dead 318 OVARLIVE // variable is alive 319 ORESULT // result of a function call; Xoffset is stack offset 320 OINLMARK // start of an inlined body, with file/line of caller. Xoffset is an index into the inline tree. 321 OLINKSYMOFFSET // offset within a name 322 323 // opcodes for generics 324 ODYNAMICDOTTYPE // x = i.(T) where T is a type parameter (or derived from a type parameter) 325 ODYNAMICDOTTYPE2 // x, ok = i.(T) where T is a type parameter (or derived from a type parameter) 326 ODYNAMICTYPE // a type node for type switches (represents a dynamic target type for a type switch) 327 328 // arch-specific opcodes 329 OTAILCALL // tail call to another function 330 OGETG // runtime.getg() (read g pointer) 331 OGETCALLERPC // runtime.getcallerpc() (continuation PC in caller frame) 332 OGETCALLERSP // runtime.getcallersp() (stack pointer in caller frame) 333 334 OEND 335) 336 337// IsCmp reports whether op is a comparison operation (==, !=, <, <=, 338// >, or >=). 339func (op Op) IsCmp() bool { 340 switch op { 341 case OEQ, ONE, OLT, OLE, OGT, OGE: 342 return true 343 } 344 return false 345} 346 347// Nodes is a pointer to a slice of *Node. 348// For fields that are not used in most nodes, this is used instead of 349// a slice to save space. 350type Nodes []Node 351 352// Append appends entries to Nodes. 353func (n *Nodes) Append(a ...Node) { 354 if len(a) == 0 { 355 return 356 } 357 *n = append(*n, a...) 358} 359 360// Prepend prepends entries to Nodes. 361// If a slice is passed in, this will take ownership of it. 362func (n *Nodes) Prepend(a ...Node) { 363 if len(a) == 0 { 364 return 365 } 366 *n = append(a, *n...) 367} 368 369// Take clears n, returning its former contents. 370func (n *Nodes) Take() []Node { 371 ret := *n 372 *n = nil 373 return ret 374} 375 376// Copy returns a copy of the content of the slice. 377func (n Nodes) Copy() Nodes { 378 if n == nil { 379 return nil 380 } 381 c := make(Nodes, len(n)) 382 copy(c, n) 383 return c 384} 385 386// NameQueue is a FIFO queue of *Name. The zero value of NameQueue is 387// a ready-to-use empty queue. 388type NameQueue struct { 389 ring []*Name 390 head, tail int 391} 392 393// Empty reports whether q contains no Names. 394func (q *NameQueue) Empty() bool { 395 return q.head == q.tail 396} 397 398// PushRight appends n to the right of the queue. 399func (q *NameQueue) PushRight(n *Name) { 400 if len(q.ring) == 0 { 401 q.ring = make([]*Name, 16) 402 } else if q.head+len(q.ring) == q.tail { 403 // Grow the ring. 404 nring := make([]*Name, len(q.ring)*2) 405 // Copy the old elements. 406 part := q.ring[q.head%len(q.ring):] 407 if q.tail-q.head <= len(part) { 408 part = part[:q.tail-q.head] 409 copy(nring, part) 410 } else { 411 pos := copy(nring, part) 412 copy(nring[pos:], q.ring[:q.tail%len(q.ring)]) 413 } 414 q.ring, q.head, q.tail = nring, 0, q.tail-q.head 415 } 416 417 q.ring[q.tail%len(q.ring)] = n 418 q.tail++ 419} 420 421// PopLeft pops a Name from the left of the queue. It panics if q is 422// empty. 423func (q *NameQueue) PopLeft() *Name { 424 if q.Empty() { 425 panic("dequeue empty") 426 } 427 n := q.ring[q.head%len(q.ring)] 428 q.head++ 429 return n 430} 431 432// NameSet is a set of Names. 433type NameSet map[*Name]struct{} 434 435// Has reports whether s contains n. 436func (s NameSet) Has(n *Name) bool { 437 _, isPresent := s[n] 438 return isPresent 439} 440 441// Add adds n to s. 442func (s *NameSet) Add(n *Name) { 443 if *s == nil { 444 *s = make(map[*Name]struct{}) 445 } 446 (*s)[n] = struct{}{} 447} 448 449// Sorted returns s sorted according to less. 450func (s NameSet) Sorted(less func(*Name, *Name) bool) []*Name { 451 var res []*Name 452 for n := range s { 453 res = append(res, n) 454 } 455 sort.Slice(res, func(i, j int) bool { return less(res[i], res[j]) }) 456 return res 457} 458 459type PragmaFlag uint16 460 461const ( 462 // Func pragmas. 463 Nointerface PragmaFlag = 1 << iota 464 Noescape // func parameters don't escape 465 Norace // func must not have race detector annotations 466 Nosplit // func should not execute on separate stack 467 Noinline // func should not be inlined 468 NoCheckPtr // func should not be instrumented by checkptr 469 CgoUnsafeArgs // treat a pointer to one arg as a pointer to them all 470 UintptrKeepAlive // pointers converted to uintptr must be kept alive (compiler internal only) 471 UintptrEscapes // pointers converted to uintptr escape 472 473 // Runtime-only func pragmas. 474 // See ../../../../runtime/README.md for detailed descriptions. 475 Systemstack // func must run on system stack 476 Nowritebarrier // emit compiler error instead of write barrier 477 Nowritebarrierrec // error on write barrier in this or recursive callees 478 Yeswritebarrierrec // cancels Nowritebarrierrec in this function and callees 479 480 // Runtime and cgo type pragmas 481 NotInHeap // values of this type must not be heap allocated 482 483 // Go command pragmas 484 GoBuildPragma 485 486 RegisterParams // TODO(register args) remove after register abi is working 487 488) 489 490func AsNode(n types.Object) Node { 491 if n == nil { 492 return nil 493 } 494 return n.(Node) 495} 496 497var BlankNode Node 498 499func IsConst(n Node, ct constant.Kind) bool { 500 return ConstType(n) == ct 501} 502 503// IsNil reports whether n represents the universal untyped zero value "nil". 504func IsNil(n Node) bool { 505 // Check n.Orig because constant propagation may produce typed nil constants, 506 // which don't exist in the Go spec. 507 return n != nil && Orig(n).Op() == ONIL 508} 509 510func IsBlank(n Node) bool { 511 if n == nil { 512 return false 513 } 514 return n.Sym().IsBlank() 515} 516 517// IsMethod reports whether n is a method. 518// n must be a function or a method. 519func IsMethod(n Node) bool { 520 return n.Type().Recv() != nil 521} 522 523func HasNamedResults(fn *Func) bool { 524 typ := fn.Type() 525 return typ.NumResults() > 0 && types.OrigSym(typ.Results().Field(0).Sym) != nil 526} 527 528// HasUniquePos reports whether n has a unique position that can be 529// used for reporting error messages. 530// 531// It's primarily used to distinguish references to named objects, 532// whose Pos will point back to their declaration position rather than 533// their usage position. 534func HasUniquePos(n Node) bool { 535 switch n.Op() { 536 case ONAME, OPACK: 537 return false 538 case OLITERAL, ONIL, OTYPE: 539 if n.Sym() != nil { 540 return false 541 } 542 } 543 544 if !n.Pos().IsKnown() { 545 if base.Flag.K != 0 { 546 base.Warn("setlineno: unknown position (line 0)") 547 } 548 return false 549 } 550 551 return true 552} 553 554func SetPos(n Node) src.XPos { 555 lno := base.Pos 556 if n != nil && HasUniquePos(n) { 557 base.Pos = n.Pos() 558 } 559 return lno 560} 561 562// The result of InitExpr MUST be assigned back to n, e.g. 563// n.X = InitExpr(init, n.X) 564func InitExpr(init []Node, expr Node) Node { 565 if len(init) == 0 { 566 return expr 567 } 568 569 n, ok := expr.(InitNode) 570 if !ok || MayBeShared(n) { 571 // Introduce OCONVNOP to hold init list. 572 n = NewConvExpr(base.Pos, OCONVNOP, nil, expr) 573 n.SetType(expr.Type()) 574 n.SetTypecheck(1) 575 } 576 577 n.PtrInit().Prepend(init...) 578 return n 579} 580 581// what's the outer value that a write to n affects? 582// outer value means containing struct or array. 583func OuterValue(n Node) Node { 584 for { 585 switch nn := n; nn.Op() { 586 case OXDOT: 587 base.FatalfAt(n.Pos(), "OXDOT in OuterValue: %v", n) 588 case ODOT: 589 nn := nn.(*SelectorExpr) 590 n = nn.X 591 continue 592 case OPAREN: 593 nn := nn.(*ParenExpr) 594 n = nn.X 595 continue 596 case OCONVNOP: 597 nn := nn.(*ConvExpr) 598 n = nn.X 599 continue 600 case OINDEX: 601 nn := nn.(*IndexExpr) 602 if nn.X.Type() == nil { 603 base.Fatalf("OuterValue needs type for %v", nn.X) 604 } 605 if nn.X.Type().IsArray() { 606 n = nn.X 607 continue 608 } 609 } 610 611 return n 612 } 613} 614 615const ( 616 EscUnknown = iota 617 EscNone // Does not escape to heap, result, or parameters. 618 EscHeap // Reachable from the heap 619 EscNever // By construction will not escape. 620) 621