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