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 gc 8 9 import ( 10 "cmd/compile/internal/ssa" 11 "cmd/compile/internal/syntax" 12 "cmd/compile/internal/types" 13 "cmd/internal/obj" 14 "cmd/internal/src" 15 "sort" 16 ) 17 18 // A Node is a single node in the syntax tree. 19 // Actually the syntax tree is a syntax DAG, because there is only one 20 // node with Op=ONAME for a given instance of a variable x. 21 // The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared. 22 type Node struct { 23 // Tree structure. 24 // Generic recursive walks should follow these fields. 25 Left *Node 26 Right *Node 27 Ninit Nodes 28 Nbody Nodes 29 List Nodes 30 Rlist Nodes 31 32 // most nodes 33 Type *types.Type 34 Orig *Node // original form, for printing, and tracking copies of ONAMEs 35 36 // func 37 Func *Func 38 39 // ONAME, OTYPE, OPACK, OLABEL, some OLITERAL 40 Name *Name 41 42 Sym *types.Sym // various 43 E interface{} // Opt or Val, see methods below 44 45 // Various. Usually an offset into a struct. For example: 46 // - ONAME nodes that refer to local variables use it to identify their stack frame position. 47 // - ODOT, ODOTPTR, and ORESULT use it to indicate offset relative to their base address. 48 // - OSTRUCTKEY uses it to store the named field's offset. 49 // - Named OLITERALs use it to store their ambient iota value. 50 // - OINLMARK stores an index into the inlTree data structure. 51 // Possibly still more uses. If you find any, document them. 52 Xoffset int64 53 54 Pos src.XPos 55 56 flags bitset32 57 58 Esc uint16 // EscXXX 59 60 Op Op 61 aux uint8 62 } 63 64 func (n *Node) ResetAux() { 65 n.aux = 0 66 } 67 68 func (n *Node) SubOp() Op { 69 switch n.Op { 70 case OASOP, ONAME: 71 default: 72 Fatalf("unexpected op: %v", n.Op) 73 } 74 return Op(n.aux) 75 } 76 77 func (n *Node) SetSubOp(op Op) { 78 switch n.Op { 79 case OASOP, ONAME: 80 default: 81 Fatalf("unexpected op: %v", n.Op) 82 } 83 n.aux = uint8(op) 84 } 85 86 func (n *Node) IndexMapLValue() bool { 87 if n.Op != OINDEXMAP { 88 Fatalf("unexpected op: %v", n.Op) 89 } 90 return n.aux != 0 91 } 92 93 func (n *Node) SetIndexMapLValue(b bool) { 94 if n.Op != OINDEXMAP { 95 Fatalf("unexpected op: %v", n.Op) 96 } 97 if b { 98 n.aux = 1 99 } else { 100 n.aux = 0 101 } 102 } 103 104 func (n *Node) TChanDir() types.ChanDir { 105 if n.Op != OTCHAN { 106 Fatalf("unexpected op: %v", n.Op) 107 } 108 return types.ChanDir(n.aux) 109 } 110 111 func (n *Node) SetTChanDir(dir types.ChanDir) { 112 if n.Op != OTCHAN { 113 Fatalf("unexpected op: %v", n.Op) 114 } 115 n.aux = uint8(dir) 116 } 117 118 func (n *Node) IsSynthetic() bool { 119 name := n.Sym.Name 120 return name[0] == '.' || name[0] == '~' 121 } 122 123 // IsAutoTmp indicates if n was created by the compiler as a temporary, 124 // based on the setting of the .AutoTemp flag in n's Name. 125 func (n *Node) IsAutoTmp() bool { 126 if n == nil || n.Op != ONAME { 127 return false 128 } 129 return n.Name.AutoTemp() 130 } 131 132 const ( 133 nodeClass, _ = iota, 1 << iota // PPARAM, PAUTO, PEXTERN, etc; three bits; first in the list because frequently accessed 134 _, _ // second nodeClass bit 135 _, _ // third nodeClass bit 136 nodeWalkdef, _ // tracks state during typecheckdef; 2 == loop detected; two bits 137 _, _ // second nodeWalkdef bit 138 nodeTypecheck, _ // tracks state during typechecking; 2 == loop detected; two bits 139 _, _ // second nodeTypecheck bit 140 nodeInitorder, _ // tracks state during init1; two bits 141 _, _ // second nodeInitorder bit 142 _, nodeHasBreak 143 _, nodeIsClosureVar 144 _, nodeIsOutputParamHeapAddr 145 _, nodeNoInline // used internally by inliner to indicate that a function call should not be inlined; set for OCALLFUNC and OCALLMETH only 146 _, nodeAssigned // is the variable ever assigned to 147 _, nodeAddrtaken // address taken, even if not moved to heap 148 _, nodeImplicit 149 _, nodeIsDDD // is the argument variadic 150 _, nodeDiag // already printed error about this 151 _, nodeColas // OAS resulting from := 152 _, nodeNonNil // guaranteed to be non-nil 153 _, nodeNoescape // func arguments do not escape; TODO(rsc): move Noescape to Func struct (see CL 7360) 154 _, nodeBounded // bounds check unnecessary 155 _, nodeAddable // addressable 156 _, nodeHasCall // expression contains a function call 157 _, nodeLikely // if statement condition likely 158 _, nodeHasVal // node.E contains a Val 159 _, nodeHasOpt // node.E contains an Opt 160 _, nodeEmbedded // ODCLFIELD embedded type 161 _, nodeInlFormal // OPAUTO created by inliner, derived from callee formal 162 _, nodeInlLocal // OPAUTO created by inliner, derived from callee local 163 ) 164 165 func (n *Node) Class() Class { return Class(n.flags.get3(nodeClass)) } 166 func (n *Node) Walkdef() uint8 { return n.flags.get2(nodeWalkdef) } 167 func (n *Node) Typecheck() uint8 { return n.flags.get2(nodeTypecheck) } 168 func (n *Node) Initorder() uint8 { return n.flags.get2(nodeInitorder) } 169 170 func (n *Node) HasBreak() bool { return n.flags&nodeHasBreak != 0 } 171 func (n *Node) IsClosureVar() bool { return n.flags&nodeIsClosureVar != 0 } 172 func (n *Node) NoInline() bool { return n.flags&nodeNoInline != 0 } 173 func (n *Node) IsOutputParamHeapAddr() bool { return n.flags&nodeIsOutputParamHeapAddr != 0 } 174 func (n *Node) Assigned() bool { return n.flags&nodeAssigned != 0 } 175 func (n *Node) Addrtaken() bool { return n.flags&nodeAddrtaken != 0 } 176 func (n *Node) Implicit() bool { return n.flags&nodeImplicit != 0 } 177 func (n *Node) IsDDD() bool { return n.flags&nodeIsDDD != 0 } 178 func (n *Node) Diag() bool { return n.flags&nodeDiag != 0 } 179 func (n *Node) Colas() bool { return n.flags&nodeColas != 0 } 180 func (n *Node) NonNil() bool { return n.flags&nodeNonNil != 0 } 181 func (n *Node) Noescape() bool { return n.flags&nodeNoescape != 0 } 182 func (n *Node) Bounded() bool { return n.flags&nodeBounded != 0 } 183 func (n *Node) Addable() bool { return n.flags&nodeAddable != 0 } 184 func (n *Node) HasCall() bool { return n.flags&nodeHasCall != 0 } 185 func (n *Node) Likely() bool { return n.flags&nodeLikely != 0 } 186 func (n *Node) HasVal() bool { return n.flags&nodeHasVal != 0 } 187 func (n *Node) HasOpt() bool { return n.flags&nodeHasOpt != 0 } 188 func (n *Node) Embedded() bool { return n.flags&nodeEmbedded != 0 } 189 func (n *Node) InlFormal() bool { return n.flags&nodeInlFormal != 0 } 190 func (n *Node) InlLocal() bool { return n.flags&nodeInlLocal != 0 } 191 192 func (n *Node) SetClass(b Class) { n.flags.set3(nodeClass, uint8(b)) } 193 func (n *Node) SetWalkdef(b uint8) { n.flags.set2(nodeWalkdef, b) } 194 func (n *Node) SetTypecheck(b uint8) { n.flags.set2(nodeTypecheck, b) } 195 func (n *Node) SetInitorder(b uint8) { n.flags.set2(nodeInitorder, b) } 196 197 func (n *Node) SetHasBreak(b bool) { n.flags.set(nodeHasBreak, b) } 198 func (n *Node) SetIsClosureVar(b bool) { n.flags.set(nodeIsClosureVar, b) } 199 func (n *Node) SetNoInline(b bool) { n.flags.set(nodeNoInline, b) } 200 func (n *Node) SetIsOutputParamHeapAddr(b bool) { n.flags.set(nodeIsOutputParamHeapAddr, b) } 201 func (n *Node) SetAssigned(b bool) { n.flags.set(nodeAssigned, b) } 202 func (n *Node) SetAddrtaken(b bool) { n.flags.set(nodeAddrtaken, b) } 203 func (n *Node) SetImplicit(b bool) { n.flags.set(nodeImplicit, b) } 204 func (n *Node) SetIsDDD(b bool) { n.flags.set(nodeIsDDD, b) } 205 func (n *Node) SetDiag(b bool) { n.flags.set(nodeDiag, b) } 206 func (n *Node) SetColas(b bool) { n.flags.set(nodeColas, b) } 207 func (n *Node) SetNonNil(b bool) { n.flags.set(nodeNonNil, b) } 208 func (n *Node) SetNoescape(b bool) { n.flags.set(nodeNoescape, b) } 209 func (n *Node) SetBounded(b bool) { n.flags.set(nodeBounded, b) } 210 func (n *Node) SetAddable(b bool) { n.flags.set(nodeAddable, b) } 211 func (n *Node) SetHasCall(b bool) { n.flags.set(nodeHasCall, b) } 212 func (n *Node) SetLikely(b bool) { n.flags.set(nodeLikely, b) } 213 func (n *Node) SetHasVal(b bool) { n.flags.set(nodeHasVal, b) } 214 func (n *Node) SetHasOpt(b bool) { n.flags.set(nodeHasOpt, b) } 215 func (n *Node) SetEmbedded(b bool) { n.flags.set(nodeEmbedded, b) } 216 func (n *Node) SetInlFormal(b bool) { n.flags.set(nodeInlFormal, b) } 217 func (n *Node) SetInlLocal(b bool) { n.flags.set(nodeInlLocal, b) } 218 219 // Val returns the Val for the node. 220 func (n *Node) Val() Val { 221 if !n.HasVal() { 222 return Val{} 223 } 224 return Val{n.E} 225 } 226 227 // SetVal sets the Val for the node, which must not have been used with SetOpt. 228 func (n *Node) SetVal(v Val) { 229 if n.HasOpt() { 230 Debug['h'] = 1 231 Dump("have Opt", n) 232 Fatalf("have Opt") 233 } 234 n.SetHasVal(true) 235 n.E = v.U 236 } 237 238 // Opt returns the optimizer data for the node. 239 func (n *Node) Opt() interface{} { 240 if !n.HasOpt() { 241 return nil 242 } 243 return n.E 244 } 245 246 // SetOpt sets the optimizer data for the node, which must not have been used with SetVal. 247 // SetOpt(nil) is ignored for Vals to simplify call sites that are clearing Opts. 248 func (n *Node) SetOpt(x interface{}) { 249 if x == nil && n.HasVal() { 250 return 251 } 252 if n.HasVal() { 253 Debug['h'] = 1 254 Dump("have Val", n) 255 Fatalf("have Val") 256 } 257 n.SetHasOpt(true) 258 n.E = x 259 } 260 261 func (n *Node) Iota() int64 { 262 return n.Xoffset 263 } 264 265 func (n *Node) SetIota(x int64) { 266 n.Xoffset = x 267 } 268 269 // mayBeShared reports whether n may occur in multiple places in the AST. 270 // Extra care must be taken when mutating such a node. 271 func (n *Node) mayBeShared() bool { 272 switch n.Op { 273 case ONAME, OLITERAL, OTYPE: 274 return true 275 } 276 return false 277 } 278 279 // isMethodExpression reports whether n represents a method expression T.M. 280 func (n *Node) isMethodExpression() bool { 281 return n.Op == ONAME && n.Left != nil && n.Left.Op == OTYPE && n.Right != nil && n.Right.Op == ONAME 282 } 283 284 // funcname returns the name (without the package) of the function n. 285 func (n *Node) funcname() string { 286 if n == nil || n.Func == nil || n.Func.Nname == nil { 287 return "<nil>" 288 } 289 return n.Func.Nname.Sym.Name 290 } 291 292 // Name holds Node fields used only by named nodes (ONAME, OTYPE, OPACK, OLABEL, some OLITERAL). 293 type Name struct { 294 Pack *Node // real package for import . names 295 Pkg *types.Pkg // pkg for OPACK nodes 296 Defn *Node // initializing assignment 297 Curfn *Node // function for local variables 298 Param *Param // additional fields for ONAME, OTYPE 299 Decldepth int32 // declaration loop depth, increased for every loop or label 300 Vargen int32 // unique name for ONAME within a function. Function outputs are numbered starting at one. 301 flags bitset8 302 } 303 304 const ( 305 nameCaptured = 1 << iota // is the variable captured by a closure 306 nameReadonly 307 nameByval // is the variable captured by value or by reference 308 nameNeedzero // if it contains pointers, needs to be zeroed on function entry 309 nameKeepalive // mark value live across unknown assembly call 310 nameAutoTemp // is the variable a temporary (implies no dwarf info. reset if escapes to heap) 311 nameUsed // for variable declared and not used error 312 ) 313 314 func (n *Name) Captured() bool { return n.flags&nameCaptured != 0 } 315 func (n *Name) Readonly() bool { return n.flags&nameReadonly != 0 } 316 func (n *Name) Byval() bool { return n.flags&nameByval != 0 } 317 func (n *Name) Needzero() bool { return n.flags&nameNeedzero != 0 } 318 func (n *Name) Keepalive() bool { return n.flags&nameKeepalive != 0 } 319 func (n *Name) AutoTemp() bool { return n.flags&nameAutoTemp != 0 } 320 func (n *Name) Used() bool { return n.flags&nameUsed != 0 } 321 322 func (n *Name) SetCaptured(b bool) { n.flags.set(nameCaptured, b) } 323 func (n *Name) SetReadonly(b bool) { n.flags.set(nameReadonly, b) } 324 func (n *Name) SetByval(b bool) { n.flags.set(nameByval, b) } 325 func (n *Name) SetNeedzero(b bool) { n.flags.set(nameNeedzero, b) } 326 func (n *Name) SetKeepalive(b bool) { n.flags.set(nameKeepalive, b) } 327 func (n *Name) SetAutoTemp(b bool) { n.flags.set(nameAutoTemp, b) } 328 func (n *Name) SetUsed(b bool) { n.flags.set(nameUsed, b) } 329 330 type Param struct { 331 Ntype *Node 332 Heapaddr *Node // temp holding heap address of param 333 334 // ONAME PAUTOHEAP 335 Stackcopy *Node // the PPARAM/PPARAMOUT on-stack slot (moved func params only) 336 337 // ONAME closure linkage 338 // Consider: 339 // 340 // func f() { 341 // x := 1 // x1 342 // func() { 343 // use(x) // x2 344 // func() { 345 // use(x) // x3 346 // --- parser is here --- 347 // }() 348 // }() 349 // } 350 // 351 // There is an original declaration of x and then a chain of mentions of x 352 // leading into the current function. Each time x is mentioned in a new closure, 353 // we create a variable representing x for use in that specific closure, 354 // since the way you get to x is different in each closure. 355 // 356 // Let's number the specific variables as shown in the code: 357 // x1 is the original x, x2 is when mentioned in the closure, 358 // and x3 is when mentioned in the closure in the closure. 359 // 360 // We keep these linked (assume N > 1): 361 // 362 // - x1.Defn = original declaration statement for x (like most variables) 363 // - x1.Innermost = current innermost closure x (in this case x3), or nil for none 364 // - x1.IsClosureVar() = false 365 // 366 // - xN.Defn = x1, N > 1 367 // - xN.IsClosureVar() = true, N > 1 368 // - x2.Outer = nil 369 // - xN.Outer = x(N-1), N > 2 370 // 371 // 372 // When we look up x in the symbol table, we always get x1. 373 // Then we can use x1.Innermost (if not nil) to get the x 374 // for the innermost known closure function, 375 // but the first reference in a closure will find either no x1.Innermost 376 // or an x1.Innermost with .Funcdepth < Funcdepth. 377 // In that case, a new xN must be created, linked in with: 378 // 379 // xN.Defn = x1 380 // xN.Outer = x1.Innermost 381 // x1.Innermost = xN 382 // 383 // When we finish the function, we'll process its closure variables 384 // and find xN and pop it off the list using: 385 // 386 // x1 := xN.Defn 387 // x1.Innermost = xN.Outer 388 // 389 // We leave xN.Innermost set so that we can still get to the original 390 // variable quickly. Not shown here, but once we're 391 // done parsing a function and no longer need xN.Outer for the 392 // lexical x reference links as described above, closurebody 393 // recomputes xN.Outer as the semantic x reference link tree, 394 // even filling in x in intermediate closures that might not 395 // have mentioned it along the way to inner closures that did. 396 // See closurebody for details. 397 // 398 // During the eventual compilation, then, for closure variables we have: 399 // 400 // xN.Defn = original variable 401 // xN.Outer = variable captured in next outward scope 402 // to make closure where xN appears 403 // 404 // Because of the sharding of pieces of the node, x.Defn means x.Name.Defn 405 // and x.Innermost/Outer means x.Name.Param.Innermost/Outer. 406 Innermost *Node 407 Outer *Node 408 409 // OTYPE 410 // 411 // TODO: Should Func pragmas also be stored on the Name? 412 Pragma syntax.Pragma 413 Alias bool // node is alias for Ntype (only used when type-checking ODCLTYPE) 414 } 415 416 // Functions 417 // 418 // A simple function declaration is represented as an ODCLFUNC node f 419 // and an ONAME node n. They're linked to one another through 420 // f.Func.Nname == n and n.Name.Defn == f. When functions are 421 // referenced by name in an expression, the function's ONAME node is 422 // used directly. 423 // 424 // Function names have n.Class() == PFUNC. This distinguishes them 425 // from variables of function type. 426 // 427 // Confusingly, n.Func and f.Func both exist, but commonly point to 428 // different Funcs. (Exception: an OCALLPART's Func does point to its 429 // ODCLFUNC's Func.) 430 // 431 // A method declaration is represented like functions, except n.Sym 432 // will be the qualified method name (e.g., "T.m") and 433 // f.Func.Shortname is the bare method name (e.g., "m"). 434 // 435 // Method expressions are represented as ONAME/PFUNC nodes like 436 // function names, but their Left and Right fields still point to the 437 // type and method, respectively. They can be distinguished from 438 // normal functions with isMethodExpression. Also, unlike function 439 // name nodes, method expression nodes exist for each method 440 // expression. The declaration ONAME can be accessed with 441 // x.Type.Nname(), where x is the method expression ONAME node. 442 // 443 // Method values are represented by ODOTMETH/ODOTINTER when called 444 // immediately, and OCALLPART otherwise. They are like method 445 // expressions, except that for ODOTMETH/ODOTINTER the method name is 446 // stored in Sym instead of Right. 447 // 448 // Closures are represented by OCLOSURE node c. They link back and 449 // forth with the ODCLFUNC via Func.Closure; that is, c.Func.Closure 450 // == f and f.Func.Closure == c. 451 // 452 // Function bodies are stored in f.Nbody, and inline function bodies 453 // are stored in n.Func.Inl. Pragmas are stored in f.Func.Pragma. 454 // 455 // Imported functions skip the ODCLFUNC, so n.Name.Defn is nil. They 456 // also use Dcl instead of Inldcl. 457 458 // Func holds Node fields used only with function-like nodes. 459 type Func struct { 460 Shortname *types.Sym 461 Enter Nodes // for example, allocate and initialize memory for escaping parameters 462 Exit Nodes 463 Cvars Nodes // closure params 464 Dcl []*Node // autodcl for this func/closure 465 466 // Parents records the parent scope of each scope within a 467 // function. The root scope (0) has no parent, so the i'th 468 // scope's parent is stored at Parents[i-1]. 469 Parents []ScopeID 470 471 // Marks records scope boundary changes. 472 Marks []Mark 473 474 // Closgen tracks how many closures have been generated within 475 // this function. Used by closurename for creating unique 476 // function names. 477 Closgen int 478 479 FieldTrack map[*types.Sym]struct{} 480 DebugInfo *ssa.FuncDebug 481 Ntype *Node // signature 482 Top int // top context (ctxCallee, etc) 483 Closure *Node // OCLOSURE <-> ODCLFUNC 484 Nname *Node 485 lsym *obj.LSym 486 487 Inl *Inline 488 489 Label int32 // largest auto-generated label in this function 490 491 Endlineno src.XPos 492 WBPos src.XPos // position of first write barrier; see SetWBPos 493 494 Pragma syntax.Pragma // go:xxx function annotations 495 496 flags bitset16 497 498 // nwbrCalls records the LSyms of functions called by this 499 // function for go:nowritebarrierrec analysis. Only filled in 500 // if nowritebarrierrecCheck != nil. 501 nwbrCalls *[]nowritebarrierrecCallSym 502 } 503 504 // An Inline holds fields used for function bodies that can be inlined. 505 type Inline struct { 506 Cost int32 // heuristic cost of inlining this function 507 508 // Copies of Func.Dcl and Nbody for use during inlining. 509 Dcl []*Node 510 Body []*Node 511 } 512 513 // A Mark represents a scope boundary. 514 type Mark struct { 515 // Pos is the position of the token that marks the scope 516 // change. 517 Pos src.XPos 518 519 // Scope identifies the innermost scope to the right of Pos. 520 Scope ScopeID 521 } 522 523 // A ScopeID represents a lexical scope within a function. 524 type ScopeID int32 525 526 const ( 527 funcDupok = 1 << iota // duplicate definitions ok 528 funcWrapper // is method wrapper 529 funcNeedctxt // function uses context register (has closure variables) 530 funcReflectMethod // function calls reflect.Type.Method or MethodByName 531 funcIsHiddenClosure 532 funcHasDefer // contains a defer statement 533 funcNilCheckDisabled // disable nil checks when compiling this function 534 funcInlinabilityChecked // inliner has already determined whether the function is inlinable 535 funcExportInline // include inline body in export data 536 funcInstrumentBody // add race/msan instrumentation during SSA construction 537 ) 538 539 func (f *Func) Dupok() bool { return f.flags&funcDupok != 0 } 540 func (f *Func) Wrapper() bool { return f.flags&funcWrapper != 0 } 541 func (f *Func) Needctxt() bool { return f.flags&funcNeedctxt != 0 } 542 func (f *Func) ReflectMethod() bool { return f.flags&funcReflectMethod != 0 } 543 func (f *Func) IsHiddenClosure() bool { return f.flags&funcIsHiddenClosure != 0 } 544 func (f *Func) HasDefer() bool { return f.flags&funcHasDefer != 0 } 545 func (f *Func) NilCheckDisabled() bool { return f.flags&funcNilCheckDisabled != 0 } 546 func (f *Func) InlinabilityChecked() bool { return f.flags&funcInlinabilityChecked != 0 } 547 func (f *Func) ExportInline() bool { return f.flags&funcExportInline != 0 } 548 func (f *Func) InstrumentBody() bool { return f.flags&funcInstrumentBody != 0 } 549 550 func (f *Func) SetDupok(b bool) { f.flags.set(funcDupok, b) } 551 func (f *Func) SetWrapper(b bool) { f.flags.set(funcWrapper, b) } 552 func (f *Func) SetNeedctxt(b bool) { f.flags.set(funcNeedctxt, b) } 553 func (f *Func) SetReflectMethod(b bool) { f.flags.set(funcReflectMethod, b) } 554 func (f *Func) SetIsHiddenClosure(b bool) { f.flags.set(funcIsHiddenClosure, b) } 555 func (f *Func) SetHasDefer(b bool) { f.flags.set(funcHasDefer, b) } 556 func (f *Func) SetNilCheckDisabled(b bool) { f.flags.set(funcNilCheckDisabled, b) } 557 func (f *Func) SetInlinabilityChecked(b bool) { f.flags.set(funcInlinabilityChecked, b) } 558 func (f *Func) SetExportInline(b bool) { f.flags.set(funcExportInline, b) } 559 func (f *Func) SetInstrumentBody(b bool) { f.flags.set(funcInstrumentBody, b) } 560 561 func (f *Func) setWBPos(pos src.XPos) { 562 if Debug_wb != 0 { 563 Warnl(pos, "write barrier") 564 } 565 if !f.WBPos.IsKnown() { 566 f.WBPos = pos 567 } 568 } 569 570 //go:generate stringer -type=Op -trimprefix=O 571 572 type Op uint8 573 574 // Node ops. 575 const ( 576 OXXX Op = iota 577 578 // names 579 ONAME // var or func name 580 ONONAME // unnamed arg or return value: f(int, string) (int, error) { etc } 581 OTYPE // type name 582 OPACK // import 583 OLITERAL // literal 584 585 // expressions 586 OADD // Left + Right 587 OSUB // Left - Right 588 OOR // Left | Right 589 OXOR // Left ^ Right 590 OADDSTR // +{List} (string addition, list elements are strings) 591 OADDR // &Left 592 OANDAND // Left && Right 593 OAPPEND // append(List); after walk, Left may contain elem type descriptor 594 OBYTES2STR // Type(Left) (Type is string, Left is a []byte) 595 OBYTES2STRTMP // Type(Left) (Type is string, Left is a []byte, ephemeral) 596 ORUNES2STR // Type(Left) (Type is string, Left is a []rune) 597 OSTR2BYTES // Type(Left) (Type is []byte, Left is a string) 598 OSTR2BYTESTMP // Type(Left) (Type is []byte, Left is a string, ephemeral) 599 OSTR2RUNES // Type(Left) (Type is []rune, Left is a string) 600 OAS // Left = Right or (if Colas=true) Left := Right 601 OAS2 // List = Rlist (x, y, z = a, b, c) 602 OAS2DOTTYPE // List = Rlist (x, ok = I.(int)) 603 OAS2FUNC // List = Rlist (x, y = f()) 604 OAS2MAPR // List = Rlist (x, ok = m["foo"]) 605 OAS2RECV // List = Rlist (x, ok = <-c) 606 OASOP // Left Etype= Right (x += y) 607 OCALL // Left(List) (function call, method call or type conversion) 608 609 // OCALLFUNC, OCALLMETH, and OCALLINTER have the same structure. 610 // Prior to walk, they are: Left(List), where List is all regular arguments. 611 // If present, Right is an ODDDARG that holds the 612 // generated slice used in a call to a variadic function. 613 // After walk, List is a series of assignments to temporaries, 614 // and Rlist is an updated set of arguments, including any ODDDARG slice. 615 // TODO(josharian/khr): Use Ninit instead of List for the assignments to temporaries. See CL 114797. 616 OCALLFUNC // Left(List/Rlist) (function call f(args)) 617 OCALLMETH // Left(List/Rlist) (direct method call x.Method(args)) 618 OCALLINTER // Left(List/Rlist) (interface method call x.Method(args)) 619 OCALLPART // Left.Right (method expression x.Method, not called) 620 OCAP // cap(Left) 621 OCLOSE // close(Left) 622 OCLOSURE // func Type { Body } (func literal) 623 OCOMPLIT // Right{List} (composite literal, not yet lowered to specific form) 624 OMAPLIT // Type{List} (composite literal, Type is map) 625 OSTRUCTLIT // Type{List} (composite literal, Type is struct) 626 OARRAYLIT // Type{List} (composite literal, Type is array) 627 OSLICELIT // Type{List} (composite literal, Type is slice) Right.Int64() = slice length. 628 OPTRLIT // &Left (left is composite literal) 629 OCONV // Type(Left) (type conversion) 630 OCONVIFACE // Type(Left) (type conversion, to interface) 631 OCONVNOP // Type(Left) (type conversion, no effect) 632 OCOPY // copy(Left, Right) 633 ODCL // var Left (declares Left of type Left.Type) 634 635 // Used during parsing but don't last. 636 ODCLFUNC // func f() or func (r) f() 637 ODCLFIELD // struct field, interface field, or func/method argument/return value. 638 ODCLCONST // const pi = 3.14 639 ODCLTYPE // type Int int or type Int = int 640 641 ODELETE // delete(Left, Right) 642 ODOT // Left.Sym (Left is of struct type) 643 ODOTPTR // Left.Sym (Left is of pointer to struct type) 644 ODOTMETH // Left.Sym (Left is non-interface, Right is method name) 645 ODOTINTER // Left.Sym (Left is interface, Right is method name) 646 OXDOT // Left.Sym (before rewrite to one of the preceding) 647 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 648 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 649 OEQ // Left == Right 650 ONE // Left != Right 651 OLT // Left < Right 652 OLE // Left <= Right 653 OGE // Left >= Right 654 OGT // Left > Right 655 ODEREF // *Left 656 OINDEX // Left[Right] (index of array or slice) 657 OINDEXMAP // Left[Right] (index of map) 658 OKEY // Left:Right (key:value in struct/array/map literal) 659 OSTRUCTKEY // Sym:Left (key:value in struct literal, after type checking) 660 OLEN // len(Left) 661 OMAKE // make(List) (before type checking converts to one of the following) 662 OMAKECHAN // make(Type, Left) (type is chan) 663 OMAKEMAP // make(Type, Left) (type is map) 664 OMAKESLICE // make(Type, Left, Right) (type is slice) 665 OMUL // Left * Right 666 ODIV // Left / Right 667 OMOD // Left % Right 668 OLSH // Left << Right 669 ORSH // Left >> Right 670 OAND // Left & Right 671 OANDNOT // Left &^ Right 672 ONEW // new(Left); corresponds to calls to new in source code 673 ONEWOBJ // runtime.newobject(n.Type); introduced by walk; Left is type descriptor 674 ONOT // !Left 675 OBITNOT // ^Left 676 OPLUS // +Left 677 ONEG // -Left 678 OOROR // Left || Right 679 OPANIC // panic(Left) 680 OPRINT // print(List) 681 OPRINTN // println(List) 682 OPAREN // (Left) 683 OSEND // Left <- Right 684 OSLICE // Left[List[0] : List[1]] (Left is untypechecked or slice) 685 OSLICEARR // Left[List[0] : List[1]] (Left is array) 686 OSLICESTR // Left[List[0] : List[1]] (Left is string) 687 OSLICE3 // Left[List[0] : List[1] : List[2]] (Left is untypedchecked or slice) 688 OSLICE3ARR // Left[List[0] : List[1] : List[2]] (Left is array) 689 OSLICEHEADER // sliceheader{Left, List[0], List[1]} (Left is unsafe.Pointer, List[0] is length, List[1] is capacity) 690 ORECOVER // recover() 691 ORECV // <-Left 692 ORUNESTR // Type(Left) (Type is string, Left is rune) 693 OSELRECV // Left = <-Right.Left: (appears as .Left of OCASE; Right.Op == ORECV) 694 OSELRECV2 // List = <-Right.Left: (apperas as .Left of OCASE; count(List) == 2, Right.Op == ORECV) 695 OIOTA // iota 696 OREAL // real(Left) 697 OIMAG // imag(Left) 698 OCOMPLEX // complex(Left, Right) or complex(List[0]) where List[0] is a 2-result function call 699 OALIGNOF // unsafe.Alignof(Left) 700 OOFFSETOF // unsafe.Offsetof(Left) 701 OSIZEOF // unsafe.Sizeof(Left) 702 703 // statements 704 OBLOCK // { List } (block of code) 705 OBREAK // break [Sym] 706 OCASE // case Left or List[0]..List[1]: Nbody (select case after processing; Left==nil and List==nil means default) 707 OXCASE // case List: Nbody (select case before processing; List==nil means default) 708 OCONTINUE // continue [Sym] 709 ODEFER // defer Left (Left must be call) 710 OEMPTY // no-op (empty statement) 711 OFALL // fallthrough 712 OFOR // for Ninit; Left; Right { Nbody } 713 // OFORUNTIL is like OFOR, but the test (Left) is applied after the body: 714 // Ninit 715 // top: { Nbody } // Execute the body at least once 716 // cont: Right 717 // if Left { // And then test the loop condition 718 // List // Before looping to top, execute List 719 // goto top 720 // } 721 // OFORUNTIL is created by walk. There's no way to write this in Go code. 722 OFORUNTIL 723 OGOTO // goto Sym 724 OIF // if Ninit; Left { Nbody } else { Rlist } 725 OLABEL // Sym: 726 OGO // go Left (Left must be call) 727 ORANGE // for List = range Right { Nbody } 728 ORETURN // return List 729 OSELECT // select { List } (List is list of OXCASE or OCASE) 730 OSWITCH // switch Ninit; Left { List } (List is a list of OXCASE or OCASE) 731 OTYPESW // Left = Right.(type) (appears as .Left of OSWITCH) 732 733 // types 734 OTCHAN // chan int 735 OTMAP // map[string]int 736 OTSTRUCT // struct{} 737 OTINTER // interface{} 738 OTFUNC // func() 739 OTARRAY // []int, [8]int, [N]int or [...]int 740 741 // misc 742 ODDD // func f(args ...int) or f(l...) or var a = [...]int{0, 1, 2}. 743 ODDDARG // func f(args ...int), introduced by escape analysis. 744 OINLCALL // intermediary representation of an inlined call. 745 OEFACE // itable and data words of an empty-interface value. 746 OITAB // itable word of an interface value. 747 OIDATA // data word of an interface value in Left 748 OSPTR // base pointer of a slice or string. 749 OCLOSUREVAR // variable reference at beginning of closure function 750 OCFUNC // reference to c function pointer (not go func value) 751 OCHECKNIL // emit code to ensure pointer/interface not nil 752 OVARDEF // variable is about to be fully initialized 753 OVARKILL // variable is dead 754 OVARLIVE // variable is alive 755 ORESULT // result of a function call; Xoffset is stack offset 756 OINLMARK // start of an inlined body, with file/line of caller. Xoffset is an index into the inline tree. 757 758 // arch-specific opcodes 759 ORETJMP // return to other function 760 OGETG // runtime.getg() (read g pointer) 761 762 OEND 763 ) 764 765 // Nodes is a pointer to a slice of *Node. 766 // For fields that are not used in most nodes, this is used instead of 767 // a slice to save space. 768 type Nodes struct{ slice *[]*Node } 769 770 // asNodes returns a slice of *Node as a Nodes value. 771 func asNodes(s []*Node) Nodes { 772 return Nodes{&s} 773 } 774 775 // Slice returns the entries in Nodes as a slice. 776 // Changes to the slice entries (as in s[i] = n) will be reflected in 777 // the Nodes. 778 func (n Nodes) Slice() []*Node { 779 if n.slice == nil { 780 return nil 781 } 782 return *n.slice 783 } 784 785 // Len returns the number of entries in Nodes. 786 func (n Nodes) Len() int { 787 if n.slice == nil { 788 return 0 789 } 790 return len(*n.slice) 791 } 792 793 // Index returns the i'th element of Nodes. 794 // It panics if n does not have at least i+1 elements. 795 func (n Nodes) Index(i int) *Node { 796 return (*n.slice)[i] 797 } 798 799 // First returns the first element of Nodes (same as n.Index(0)). 800 // It panics if n has no elements. 801 func (n Nodes) First() *Node { 802 return (*n.slice)[0] 803 } 804 805 // Second returns the second element of Nodes (same as n.Index(1)). 806 // It panics if n has fewer than two elements. 807 func (n Nodes) Second() *Node { 808 return (*n.slice)[1] 809 } 810 811 // Set sets n to a slice. 812 // This takes ownership of the slice. 813 func (n *Nodes) Set(s []*Node) { 814 if len(s) == 0 { 815 n.slice = nil 816 } else { 817 // Copy s and take address of t rather than s to avoid 818 // allocation in the case where len(s) == 0 (which is 819 // over 3x more common, dynamically, for make.bash). 820 t := s 821 n.slice = &t 822 } 823 } 824 825 // Set1 sets n to a slice containing a single node. 826 func (n *Nodes) Set1(n1 *Node) { 827 n.slice = &[]*Node{n1} 828 } 829 830 // Set2 sets n to a slice containing two nodes. 831 func (n *Nodes) Set2(n1, n2 *Node) { 832 n.slice = &[]*Node{n1, n2} 833 } 834 835 // Set3 sets n to a slice containing three nodes. 836 func (n *Nodes) Set3(n1, n2, n3 *Node) { 837 n.slice = &[]*Node{n1, n2, n3} 838 } 839 840 // MoveNodes sets n to the contents of n2, then clears n2. 841 func (n *Nodes) MoveNodes(n2 *Nodes) { 842 n.slice = n2.slice 843 n2.slice = nil 844 } 845 846 // SetIndex sets the i'th element of Nodes to node. 847 // It panics if n does not have at least i+1 elements. 848 func (n Nodes) SetIndex(i int, node *Node) { 849 (*n.slice)[i] = node 850 } 851 852 // SetFirst sets the first element of Nodes to node. 853 // It panics if n does not have at least one elements. 854 func (n Nodes) SetFirst(node *Node) { 855 (*n.slice)[0] = node 856 } 857 858 // SetSecond sets the second element of Nodes to node. 859 // It panics if n does not have at least two elements. 860 func (n Nodes) SetSecond(node *Node) { 861 (*n.slice)[1] = node 862 } 863 864 // Addr returns the address of the i'th element of Nodes. 865 // It panics if n does not have at least i+1 elements. 866 func (n Nodes) Addr(i int) **Node { 867 return &(*n.slice)[i] 868 } 869 870 // Append appends entries to Nodes. 871 func (n *Nodes) Append(a ...*Node) { 872 if len(a) == 0 { 873 return 874 } 875 if n.slice == nil { 876 s := make([]*Node, len(a)) 877 copy(s, a) 878 n.slice = &s 879 return 880 } 881 *n.slice = append(*n.slice, a...) 882 } 883 884 // Prepend prepends entries to Nodes. 885 // If a slice is passed in, this will take ownership of it. 886 func (n *Nodes) Prepend(a ...*Node) { 887 if len(a) == 0 { 888 return 889 } 890 if n.slice == nil { 891 n.slice = &a 892 } else { 893 *n.slice = append(a, *n.slice...) 894 } 895 } 896 897 // AppendNodes appends the contents of *n2 to n, then clears n2. 898 func (n *Nodes) AppendNodes(n2 *Nodes) { 899 switch { 900 case n2.slice == nil: 901 case n.slice == nil: 902 n.slice = n2.slice 903 default: 904 *n.slice = append(*n.slice, *n2.slice...) 905 } 906 n2.slice = nil 907 } 908 909 // inspect invokes f on each node in an AST in depth-first order. 910 // If f(n) returns false, inspect skips visiting n's children. 911 func inspect(n *Node, f func(*Node) bool) { 912 if n == nil || !f(n) { 913 return 914 } 915 inspectList(n.Ninit, f) 916 inspect(n.Left, f) 917 inspect(n.Right, f) 918 inspectList(n.List, f) 919 inspectList(n.Nbody, f) 920 inspectList(n.Rlist, f) 921 } 922 923 func inspectList(l Nodes, f func(*Node) bool) { 924 for _, n := range l.Slice() { 925 inspect(n, f) 926 } 927 } 928 929 // nodeQueue is a FIFO queue of *Node. The zero value of nodeQueue is 930 // a ready-to-use empty queue. 931 type nodeQueue struct { 932 ring []*Node 933 head, tail int 934 } 935 936 // empty reports whether q contains no Nodes. 937 func (q *nodeQueue) empty() bool { 938 return q.head == q.tail 939 } 940 941 // pushRight appends n to the right of the queue. 942 func (q *nodeQueue) pushRight(n *Node) { 943 if len(q.ring) == 0 { 944 q.ring = make([]*Node, 16) 945 } else if q.head+len(q.ring) == q.tail { 946 // Grow the ring. 947 nring := make([]*Node, len(q.ring)*2) 948 // Copy the old elements. 949 part := q.ring[q.head%len(q.ring):] 950 if q.tail-q.head <= len(part) { 951 part = part[:q.tail-q.head] 952 copy(nring, part) 953 } else { 954 pos := copy(nring, part) 955 copy(nring[pos:], q.ring[:q.tail%len(q.ring)]) 956 } 957 q.ring, q.head, q.tail = nring, 0, q.tail-q.head 958 } 959 960 q.ring[q.tail%len(q.ring)] = n 961 q.tail++ 962 } 963 964 // popLeft pops a node from the left of the queue. It panics if q is 965 // empty. 966 func (q *nodeQueue) popLeft() *Node { 967 if q.empty() { 968 panic("dequeue empty") 969 } 970 n := q.ring[q.head%len(q.ring)] 971 q.head++ 972 return n 973 } 974 975 // NodeSet is a set of Nodes. 976 type NodeSet map[*Node]struct{} 977 978 // Has reports whether s contains n. 979 func (s NodeSet) Has(n *Node) bool { 980 _, isPresent := s[n] 981 return isPresent 982 } 983 984 // Add adds n to s. 985 func (s *NodeSet) Add(n *Node) { 986 if *s == nil { 987 *s = make(map[*Node]struct{}) 988 } 989 (*s)[n] = struct{}{} 990 } 991 992 // Sorted returns s sorted according to less. 993 func (s NodeSet) Sorted(less func(*Node, *Node) bool) []*Node { 994 var res []*Node 995 for n := range s { 996 res = append(res, n) 997 } 998 sort.Slice(res, func(i, j int) bool { return less(res[i], res[j]) }) 999 return res 1000 } 1001