.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/ir/func.go

   1 // Copyright 2013 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 package ir
   6
   7 // This file implements the Function and BasicBlock types.
   8
   9 import (
  10         "bytes"
  11         "fmt"
  12         "go/ast"
  13         "go/constant"
  14         "go/format"
  15         "go/token"
  16         "go/types"
  17         "io"
  18         "os"
  19         "strings"
  20 )
  21
  22 // addEdge adds a control-flow graph edge from from to to.
  23 func addEdge(from, to *BasicBlock) {
  24         from.Succs = append(from.Succs, to)
  25         to.Preds = append(to.Preds, from)
  26 }
  27
  28 // Control returns the last instruction in the block.
  29 func (b *BasicBlock) Control() Instruction {
  30         if len(b.Instrs) == 0 {
  31                 return nil
  32         }
  33         return b.Instrs[len(b.Instrs)-1]
  34 }
  35
  36 // SIgmaFor returns the sigma node for v coming from pred.
  37 func (b *BasicBlock) SigmaFor(v Value, pred *BasicBlock) *Sigma {
  38         for _, instr := range b.Instrs {
  39                 sigma, ok := instr.(*Sigma)
  40                 if !ok {
  41                         // no more sigmas
  42                         return nil
  43                 }
  44                 if sigma.From == pred && sigma.X == v {
  45                         return sigma
  46                 }
  47         }
  48         return nil
  49 }
  50
  51 // Parent returns the function that contains block b.
  52 func (b *BasicBlock) Parent() *Function { return b.parent }
  53
  54 // String returns a human-readable label of this block.
  55 // It is not guaranteed unique within the function.
  56 //
  57 func (b *BasicBlock) String() string {
  58         return fmt.Sprintf("%d", b.Index)
  59 }
  60
  61 // emit appends an instruction to the current basic block.
  62 // If the instruction defines a Value, it is returned.
  63 //
  64 func (b *BasicBlock) emit(i Instruction, source ast.Node) Value {
  65         i.setSource(source)
  66         i.setBlock(b)
  67         b.Instrs = append(b.Instrs, i)
  68         v, _ := i.(Value)
  69         return v
  70 }
  71
  72 // predIndex returns the i such that b.Preds[i] == c or panics if
  73 // there is none.
  74 func (b *BasicBlock) predIndex(c *BasicBlock) int {
  75         for i, pred := range b.Preds {
  76                 if pred == c {
  77                         return i
  78                 }
  79         }
  80         panic(fmt.Sprintf("no edge %s -> %s", c, b))
  81 }
  82
  83 // succIndex returns the i such that b.Succs[i] == c or -1 if there is none.
  84 func (b *BasicBlock) succIndex(c *BasicBlock) int {
  85         for i, succ := range b.Succs {
  86                 if succ == c {
  87                         return i
  88                 }
  89         }
  90         return -1
  91 }
  92
  93 // hasPhi returns true if b.Instrs contains φ-nodes.
  94 func (b *BasicBlock) hasPhi() bool {
  95         _, ok := b.Instrs[0].(*Phi)
  96         return ok
  97 }
  98
  99 func (b *BasicBlock) Phis() []Instruction {
 100         return b.phis()
 101 }
 102
 103 // phis returns the prefix of b.Instrs containing all the block's φ-nodes.
 104 func (b *BasicBlock) phis() []Instruction {
 105         for i, instr := range b.Instrs {
 106                 if _, ok := instr.(*Phi); !ok {
 107                         return b.Instrs[:i]
 108                 }
 109         }
 110         return nil // unreachable in well-formed blocks
 111 }
 112
 113 // replacePred replaces all occurrences of p in b's predecessor list with q.
 114 // Ordinarily there should be at most one.
 115 //
 116 func (b *BasicBlock) replacePred(p, q *BasicBlock) {
 117         for i, pred := range b.Preds {
 118                 if pred == p {
 119                         b.Preds[i] = q
 120                 }
 121         }
 122 }
 123
 124 // replaceSucc replaces all occurrences of p in b's successor list with q.
 125 // Ordinarily there should be at most one.
 126 //
 127 func (b *BasicBlock) replaceSucc(p, q *BasicBlock) {
 128         for i, succ := range b.Succs {
 129                 if succ == p {
 130                         b.Succs[i] = q
 131                 }
 132         }
 133 }
 134
 135 // removePred removes all occurrences of p in b's
 136 // predecessor list and φ-nodes.
 137 // Ordinarily there should be at most one.
 138 //
 139 func (b *BasicBlock) removePred(p *BasicBlock) {
 140         phis := b.phis()
 141
 142         // We must preserve edge order for φ-nodes.
 143         j := 0
 144         for i, pred := range b.Preds {
 145                 if pred != p {
 146                         b.Preds[j] = b.Preds[i]
 147                         // Strike out φ-edge too.
 148                         for _, instr := range phis {
 149                                 phi := instr.(*Phi)
 150                                 phi.Edges[j] = phi.Edges[i]
 151                         }
 152                         j++
 153                 }
 154         }
 155         // Nil out b.Preds[j:] and φ-edges[j:] to aid GC.
 156         for i := j; i < len(b.Preds); i++ {
 157                 b.Preds[i] = nil
 158                 for _, instr := range phis {
 159                         instr.(*Phi).Edges[i] = nil
 160                 }
 161         }
 162         b.Preds = b.Preds[:j]
 163         for _, instr := range phis {
 164                 phi := instr.(*Phi)
 165                 phi.Edges = phi.Edges[:j]
 166         }
 167 }
 168
 169 // Destinations associated with unlabelled for/switch/select stmts.
 170 // We push/pop one of these as we enter/leave each construct and for
 171 // each BranchStmt we scan for the innermost target of the right type.
 172 //
 173 type targets struct {
 174         tail         *targets // rest of stack
 175         _break       *BasicBlock
 176         _continue    *BasicBlock
 177         _fallthrough *BasicBlock
 178 }
 179
 180 // Destinations associated with a labelled block.
 181 // We populate these as labels are encountered in forward gotos or
 182 // labelled statements.
 183 //
 184 type lblock struct {
 185         _goto     *BasicBlock
 186         _break    *BasicBlock
 187         _continue *BasicBlock
 188 }
 189
 190 // labelledBlock returns the branch target associated with the
 191 // specified label, creating it if needed.
 192 //
 193 func (f *Function) labelledBlock(label *ast.Ident) *lblock {
 194         lb := f.lblocks[label.Obj]
 195         if lb == nil {
 196                 lb = &lblock{_goto: f.newBasicBlock(label.Name)}
 197                 if f.lblocks == nil {
 198                         f.lblocks = make(map[*ast.Object]*lblock)
 199                 }
 200                 f.lblocks[label.Obj] = lb
 201         }
 202         return lb
 203 }
 204
 205 // addParam adds a (non-escaping) parameter to f.Params of the
 206 // specified name, type and source position.
 207 //
 208 func (f *Function) addParam(name string, typ types.Type, source ast.Node) *Parameter {
 209         var b *BasicBlock
 210         if len(f.Blocks) > 0 {
 211                 b = f.Blocks[0]
 212         }
 213         v := &Parameter{
 214                 name: name,
 215         }
 216         v.setBlock(b)
 217         v.setType(typ)
 218         v.setSource(source)
 219         f.Params = append(f.Params, v)
 220         if b != nil {
 221                 // There may be no blocks if this function has no body. We
 222                 // still create params, but aren't interested in the
 223                 // instruction.
 224                 f.Blocks[0].Instrs = append(f.Blocks[0].Instrs, v)
 225         }
 226         return v
 227 }
 228
 229 func (f *Function) addParamObj(obj types.Object, source ast.Node) *Parameter {
 230         name := obj.Name()
 231         if name == "" {
 232                 name = fmt.Sprintf("arg%d", len(f.Params))
 233         }
 234         param := f.addParam(name, obj.Type(), source)
 235         param.object = obj
 236         return param
 237 }
 238
 239 // addSpilledParam declares a parameter that is pre-spilled to the
 240 // stack; the function body will load/store the spilled location.
 241 // Subsequent lifting will eliminate spills where possible.
 242 //
 243 func (f *Function) addSpilledParam(obj types.Object, source ast.Node) {
 244         param := f.addParamObj(obj, source)
 245         spill := &Alloc{}
 246         spill.setType(types.NewPointer(obj.Type()))
 247         spill.source = source
 248         f.objects[obj] = spill
 249         f.Locals = append(f.Locals, spill)
 250         f.emit(spill, source)
 251         emitStore(f, spill, param, source)
 252         // f.emit(&Store{Addr: spill, Val: param})
 253 }
 254
 255 // startBody initializes the function prior to generating IR code for its body.
 256 // Precondition: f.Type() already set.
 257 //
 258 func (f *Function) startBody() {
 259         entry := f.newBasicBlock("entry")
 260         f.currentBlock = entry
 261         f.objects = make(map[types.Object]Value) // needed for some synthetics, e.g. init
 262 }
 263
 264 func (f *Function) blockset(i int) *BlockSet {
 265         bs := &f.blocksets[i]
 266         if len(bs.values) != len(f.Blocks) {
 267                 if cap(bs.values) >= len(f.Blocks) {
 268                         bs.values = bs.values[:len(f.Blocks)]
 269                         bs.Clear()
 270                 } else {
 271                         bs.values = make([]bool, len(f.Blocks))
 272                 }
 273         } else {
 274                 bs.Clear()
 275         }
 276         return bs
 277 }
 278
 279 func (f *Function) exitBlock() {
 280         old := f.currentBlock
 281
 282         f.Exit = f.newBasicBlock("exit")
 283         f.currentBlock = f.Exit
 284
 285         ret := f.results()
 286         results := make([]Value, len(ret))
 287         // Run function calls deferred in this
 288         // function when explicitly returning from it.
 289         f.emit(new(RunDefers), nil)
 290         for i, r := range ret {
 291                 results[i] = emitLoad(f, r, nil)
 292         }
 293
 294         f.emit(&Return{Results: results}, nil)
 295         f.currentBlock = old
 296 }
 297
 298 // createSyntacticParams populates f.Params and generates code (spills
 299 // and named result locals) for all the parameters declared in the
 300 // syntax.  In addition it populates the f.objects mapping.
 301 //
 302 // Preconditions:
 303 // f.startBody() was called.
 304 // Postcondition:
 305 // len(f.Params) == len(f.Signature.Params) + (f.Signature.Recv() ? 1 : 0)
 306 //
 307 func (f *Function) createSyntacticParams(recv *ast.FieldList, functype *ast.FuncType) {
 308         // Receiver (at most one inner iteration).
 309         if recv != nil {
 310                 for _, field := range recv.List {
 311                         for _, n := range field.Names {
 312                                 f.addSpilledParam(f.Pkg.info.Defs[n], n)
 313                         }
 314                         // Anonymous receiver?  No need to spill.
 315                         if field.Names == nil {
 316                                 f.addParamObj(f.Signature.Recv(), field)
 317                         }
 318                 }
 319         }
 320
 321         // Parameters.
 322         if functype.Params != nil {
 323                 n := len(f.Params) // 1 if has recv, 0 otherwise
 324                 for _, field := range functype.Params.List {
 325                         for _, n := range field.Names {
 326                                 f.addSpilledParam(f.Pkg.info.Defs[n], n)
 327                         }
 328                         // Anonymous parameter?  No need to spill.
 329                         if field.Names == nil {
 330                                 f.addParamObj(f.Signature.Params().At(len(f.Params)-n), field)
 331                         }
 332                 }
 333         }
 334
 335         // Named results.
 336         if functype.Results != nil {
 337                 for _, field := range functype.Results.List {
 338                         // Implicit "var" decl of locals for named results.
 339                         for _, n := range field.Names {
 340                                 f.namedResults = append(f.namedResults, f.addLocalForIdent(n))
 341                         }
 342                 }
 343
 344                 if len(f.namedResults) == 0 {
 345                         sig := f.Signature.Results()
 346                         for i := 0; i < sig.Len(); i++ {
 347                                 // XXX position information
 348                                 v := f.addLocal(sig.At(i).Type(), nil)
 349                                 f.implicitResults = append(f.implicitResults, v)
 350                         }
 351                 }
 352         }
 353 }
 354
 355 func numberNodes(f *Function) {
 356         var base ID
 357         for _, b := range f.Blocks {
 358                 for _, instr := range b.Instrs {
 359                         if instr == nil {
 360                                 continue
 361                         }
 362                         base++
 363                         instr.setID(base)
 364                 }
 365         }
 366 }
 367
 368 // buildReferrers populates the def/use information in all non-nil
 369 // Value.Referrers slice.
 370 // Precondition: all such slices are initially empty.
 371 func buildReferrers(f *Function) {
 372         var rands []*Value
 373         for _, b := range f.Blocks {
 374                 for _, instr := range b.Instrs {
 375                         rands = instr.Operands(rands[:0]) // recycle storage
 376                         for _, rand := range rands {
 377                                 if r := *rand; r != nil {
 378                                         if ref := r.Referrers(); ref != nil {
 379                                                 *ref = append(*ref, instr)
 380                                         }
 381                                 }
 382                         }
 383                 }
 384         }
 385 }
 386
 387 func (f *Function) emitConsts() {
 388         if len(f.Blocks) == 0 {
 389                 f.consts = nil
 390                 return
 391         }
 392
 393         // TODO(dh): our deduplication only works on booleans and
 394         // integers. other constants are represented as pointers to
 395         // things.
 396         if len(f.consts) == 0 {
 397                 return
 398         } else if len(f.consts) <= 32 {
 399                 f.emitConstsFew()
 400         } else {
 401                 f.emitConstsMany()
 402         }
 403 }
 404
 405 func (f *Function) emitConstsFew() {
 406         dedup := make([]*Const, 0, 32)
 407         for _, c := range f.consts {
 408                 if len(*c.Referrers()) == 0 {
 409                         continue
 410                 }
 411                 found := false
 412                 for _, d := range dedup {
 413                         if c.typ == d.typ && c.Value == d.Value {
 414                                 replaceAll(c, d)
 415                                 found = true
 416                                 break
 417                         }
 418                 }
 419                 if !found {
 420                         dedup = append(dedup, c)
 421                 }
 422         }
 423
 424         instrs := make([]Instruction, len(f.Blocks[0].Instrs)+len(dedup))
 425         for i, c := range dedup {
 426                 instrs[i] = c
 427                 c.setBlock(f.Blocks[0])
 428         }
 429         copy(instrs[len(dedup):], f.Blocks[0].Instrs)
 430         f.Blocks[0].Instrs = instrs
 431         f.consts = nil
 432 }
 433
 434 func (f *Function) emitConstsMany() {
 435         type constKey struct {
 436                 typ   types.Type
 437                 value constant.Value
 438         }
 439
 440         m := make(map[constKey]Value, len(f.consts))
 441         areNil := 0
 442         for i, c := range f.consts {
 443                 if len(*c.Referrers()) == 0 {
 444                         f.consts[i] = nil
 445                         areNil++
 446                         continue
 447                 }
 448
 449                 k := constKey{
 450                         typ:   c.typ,
 451                         value: c.Value,
 452                 }
 453                 if dup, ok := m[k]; !ok {
 454                         m[k] = c
 455                 } else {
 456                         f.consts[i] = nil
 457                         areNil++
 458                         replaceAll(c, dup)
 459                 }
 460         }
 461
 462         instrs := make([]Instruction, len(f.Blocks[0].Instrs)+len(f.consts)-areNil)
 463         i := 0
 464         for _, c := range f.consts {
 465                 if c != nil {
 466                         instrs[i] = c
 467                         c.setBlock(f.Blocks[0])
 468                         i++
 469                 }
 470         }
 471         copy(instrs[i:], f.Blocks[0].Instrs)
 472         f.Blocks[0].Instrs = instrs
 473         f.consts = nil
 474 }
 475
 476 // buildFakeExits ensures that every block in the function is
 477 // reachable in reverse from the Exit block. This is required to build
 478 // a full post-dominator tree, and to ensure the exit block's
 479 // inclusion in the dominator tree.
 480 func buildFakeExits(fn *Function) {
 481         // Find back-edges via forward DFS
 482         fn.fakeExits = BlockSet{values: make([]bool, len(fn.Blocks))}
 483         seen := fn.blockset(0)
 484         backEdges := fn.blockset(1)
 485
 486         var dfs func(b *BasicBlock)
 487         dfs = func(b *BasicBlock) {
 488                 if !seen.Add(b) {
 489                         backEdges.Add(b)
 490                         return
 491                 }
 492                 for _, pred := range b.Succs {
 493                         dfs(pred)
 494                 }
 495         }
 496         dfs(fn.Blocks[0])
 497 buildLoop:
 498         for {
 499                 seen := fn.blockset(2)
 500                 var dfs func(b *BasicBlock)
 501                 dfs = func(b *BasicBlock) {
 502                         if !seen.Add(b) {
 503                                 return
 504                         }
 505                         for _, pred := range b.Preds {
 506                                 dfs(pred)
 507                         }
 508                         if b == fn.Exit {
 509                                 for _, b := range fn.Blocks {
 510                                         if fn.fakeExits.Has(b) {
 511                                                 dfs(b)
 512                                         }
 513                                 }
 514                         }
 515                 }
 516                 dfs(fn.Exit)
 517
 518                 for _, b := range fn.Blocks {
 519                         if !seen.Has(b) && backEdges.Has(b) {
 520                                 // Block b is not reachable from the exit block. Add a
 521                                 // fake jump from b to exit, then try again. Note that we
 522                                 // only add one fake edge at a time, as it may make
 523                                 // multiple blocks reachable.
 524                                 //
 525                                 // We only consider those blocks that have back edges.
 526                                 // Any unreachable block that doesn't have a back edge
 527                                 // must flow into a loop, which by definition has a
 528                                 // back edge. Thus, by looking for loops, we should
 529                                 // need fewer fake edges overall.
 530                                 fn.fakeExits.Add(b)
 531                                 continue buildLoop
 532                         }
 533                 }
 534
 535                 break
 536         }
 537 }
 538
 539 // finishBody() finalizes the function after IR code generation of its body.
 540 func (f *Function) finishBody() {
 541         f.objects = nil
 542         f.currentBlock = nil
 543         f.lblocks = nil
 544
 545         // Remove from f.Locals any Allocs that escape to the heap.
 546         j := 0
 547         for _, l := range f.Locals {
 548                 if !l.Heap {
 549                         f.Locals[j] = l
 550                         j++
 551                 }
 552         }
 553         // Nil out f.Locals[j:] to aid GC.
 554         for i := j; i < len(f.Locals); i++ {
 555                 f.Locals[i] = nil
 556         }
 557         f.Locals = f.Locals[:j]
 558
 559         optimizeBlocks(f)
 560         buildReferrers(f)
 561         buildDomTree(f)
 562         buildPostDomTree(f)
 563
 564         if f.Prog.mode&NaiveForm == 0 {
 565                 lift(f)
 566         }
 567
 568         // emit constants after lifting, because lifting may produce new constants.
 569         f.emitConsts()
 570
 571         f.namedResults = nil // (used by lifting)
 572         f.implicitResults = nil
 573
 574         numberNodes(f)
 575
 576         defer f.wr.Close()
 577         f.wr.WriteFunc("start", "start", f)
 578
 579         if f.Prog.mode&PrintFunctions != 0 {
 580                 printMu.Lock()
 581                 f.WriteTo(os.Stdout)
 582                 printMu.Unlock()
 583         }
 584
 585         if f.Prog.mode&SanityCheckFunctions != 0 {
 586                 mustSanityCheck(f, nil)
 587         }
 588 }
 589
 590 func isUselessPhi(phi *Phi) (Value, bool) {
 591         var v0 Value
 592         for _, e := range phi.Edges {
 593                 if e == phi {
 594                         continue
 595                 }
 596                 if v0 == nil {
 597                         v0 = e
 598                 }
 599                 if v0 != e {
 600                         if v0, ok := v0.(*Const); ok {
 601                                 if e, ok := e.(*Const); ok {
 602                                         if v0.typ == e.typ && v0.Value == e.Value {
 603                                                 continue
 604                                         }
 605                                 }
 606                         }
 607                         return nil, false
 608                 }
 609         }
 610         return v0, true
 611 }
 612
 613 func (f *Function) RemoveNilBlocks() {
 614         f.removeNilBlocks()
 615 }
 616
 617 // removeNilBlocks eliminates nils from f.Blocks and updates each
 618 // BasicBlock.Index.  Use this after any pass that may delete blocks.
 619 //
 620 func (f *Function) removeNilBlocks() {
 621         j := 0
 622         for _, b := range f.Blocks {
 623                 if b != nil {
 624                         b.Index = j
 625                         f.Blocks[j] = b
 626                         j++
 627                 }
 628         }
 629         // Nil out f.Blocks[j:] to aid GC.
 630         for i := j; i < len(f.Blocks); i++ {
 631                 f.Blocks[i] = nil
 632         }
 633         f.Blocks = f.Blocks[:j]
 634 }
 635
 636 // SetDebugMode sets the debug mode for package pkg.  If true, all its
 637 // functions will include full debug info.  This greatly increases the
 638 // size of the instruction stream, and causes Functions to depend upon
 639 // the ASTs, potentially keeping them live in memory for longer.
 640 //
 641 func (pkg *Package) SetDebugMode(debug bool) {
 642         // TODO(adonovan): do we want ast.File granularity?
 643         pkg.debug = debug
 644 }
 645
 646 // debugInfo reports whether debug info is wanted for this function.
 647 func (f *Function) debugInfo() bool {
 648         return f.Pkg != nil && f.Pkg.debug
 649 }
 650
 651 // addNamedLocal creates a local variable, adds it to function f and
 652 // returns it.  Its name and type are taken from obj.  Subsequent
 653 // calls to f.lookup(obj) will return the same local.
 654 //
 655 func (f *Function) addNamedLocal(obj types.Object, source ast.Node) *Alloc {
 656         l := f.addLocal(obj.Type(), source)
 657         f.objects[obj] = l
 658         return l
 659 }
 660
 661 func (f *Function) addLocalForIdent(id *ast.Ident) *Alloc {
 662         return f.addNamedLocal(f.Pkg.info.Defs[id], id)
 663 }
 664
 665 // addLocal creates an anonymous local variable of type typ, adds it
 666 // to function f and returns it.  pos is the optional source location.
 667 //
 668 func (f *Function) addLocal(typ types.Type, source ast.Node) *Alloc {
 669         v := &Alloc{}
 670         v.setType(types.NewPointer(typ))
 671         f.Locals = append(f.Locals, v)
 672         f.emit(v, source)
 673         return v
 674 }
 675
 676 // lookup returns the address of the named variable identified by obj
 677 // that is local to function f or one of its enclosing functions.
 678 // If escaping, the reference comes from a potentially escaping pointer
 679 // expression and the referent must be heap-allocated.
 680 //
 681 func (f *Function) lookup(obj types.Object, escaping bool) Value {
 682         if v, ok := f.objects[obj]; ok {
 683                 if alloc, ok := v.(*Alloc); ok && escaping {
 684                         alloc.Heap = true
 685                 }
 686                 return v // function-local var (address)
 687         }
 688
 689         // Definition must be in an enclosing function;
 690         // plumb it through intervening closures.
 691         if f.parent == nil {
 692                 panic("no ir.Value for " + obj.String())
 693         }
 694         outer := f.parent.lookup(obj, true) // escaping
 695         v := &FreeVar{
 696                 name:   obj.Name(),
 697                 typ:    outer.Type(),
 698                 outer:  outer,
 699                 parent: f,
 700         }
 701         f.objects[obj] = v
 702         f.FreeVars = append(f.FreeVars, v)
 703         return v
 704 }
 705
 706 // emit emits the specified instruction to function f.
 707 func (f *Function) emit(instr Instruction, source ast.Node) Value {
 708         return f.currentBlock.emit(instr, source)
 709 }
 710
 711 // RelString returns the full name of this function, qualified by
 712 // package name, receiver type, etc.
 713 //
 714 // The specific formatting rules are not guaranteed and may change.
 715 //
 716 // Examples:
 717 //      "math.IsNaN"                  // a package-level function
 718 //      "(*bytes.Buffer).Bytes"       // a declared method or a wrapper
 719 //      "(*bytes.Buffer).Bytes$thunk" // thunk (func wrapping method; receiver is param 0)
 720 //      "(*bytes.Buffer).Bytes$bound" // bound (func wrapping method; receiver supplied by closure)
 721 //      "main.main$1"                 // an anonymous function in main
 722 //      "main.init#1"                 // a declared init function
 723 //      "main.init"                   // the synthesized package initializer
 724 //
 725 // When these functions are referred to from within the same package
 726 // (i.e. from == f.Pkg.Object), they are rendered without the package path.
 727 // For example: "IsNaN", "(*Buffer).Bytes", etc.
 728 //
 729 // All non-synthetic functions have distinct package-qualified names.
 730 // (But two methods may have the same name "(T).f" if one is a synthetic
 731 // wrapper promoting a non-exported method "f" from another package; in
 732 // that case, the strings are equal but the identifiers "f" are distinct.)
 733 //
 734 func (f *Function) RelString(from *types.Package) string {
 735         // Anonymous?
 736         if f.parent != nil {
 737                 // An anonymous function's Name() looks like "parentName$1",
 738                 // but its String() should include the type/package/etc.
 739                 parent := f.parent.RelString(from)
 740                 for i, anon := range f.parent.AnonFuncs {
 741                         if anon == f {
 742                                 return fmt.Sprintf("%s$%d", parent, 1+i)
 743                         }
 744                 }
 745
 746                 return f.name // should never happen
 747         }
 748
 749         // Method (declared or wrapper)?
 750         if recv := f.Signature.Recv(); recv != nil {
 751                 return f.relMethod(from, recv.Type())
 752         }
 753
 754         // Thunk?
 755         if f.method != nil {
 756                 return f.relMethod(from, f.method.Recv())
 757         }
 758
 759         // Bound?
 760         if len(f.FreeVars) == 1 && strings.HasSuffix(f.name, "$bound") {
 761                 return f.relMethod(from, f.FreeVars[0].Type())
 762         }
 763
 764         // Package-level function?
 765         // Prefix with package name for cross-package references only.
 766         if p := f.pkg(); p != nil && p != from {
 767                 return fmt.Sprintf("%s.%s", p.Path(), f.name)
 768         }
 769
 770         // Unknown.
 771         return f.name
 772 }
 773
 774 func (f *Function) relMethod(from *types.Package, recv types.Type) string {
 775         return fmt.Sprintf("(%s).%s", relType(recv, from), f.name)
 776 }
 777
 778 // writeSignature writes to buf the signature sig in declaration syntax.
 779 func writeSignature(buf *bytes.Buffer, from *types.Package, name string, sig *types.Signature, params []*Parameter) {
 780         buf.WriteString("func ")
 781         if recv := sig.Recv(); recv != nil {
 782                 buf.WriteString("(")
 783                 if n := params[0].Name(); n != "" {
 784                         buf.WriteString(n)
 785                         buf.WriteString(" ")
 786                 }
 787                 types.WriteType(buf, params[0].Type(), types.RelativeTo(from))
 788                 buf.WriteString(") ")
 789         }
 790         buf.WriteString(name)
 791         types.WriteSignature(buf, sig, types.RelativeTo(from))
 792 }
 793
 794 func (f *Function) pkg() *types.Package {
 795         if f.Pkg != nil {
 796                 return f.Pkg.Pkg
 797         }
 798         return nil
 799 }
 800
 801 var _ io.WriterTo = (*Function)(nil) // *Function implements io.Writer
 802
 803 func (f *Function) WriteTo(w io.Writer) (int64, error) {
 804         var buf bytes.Buffer
 805         WriteFunction(&buf, f)
 806         n, err := w.Write(buf.Bytes())
 807         return int64(n), err
 808 }
 809
 810 // WriteFunction writes to buf a human-readable "disassembly" of f.
 811 func WriteFunction(buf *bytes.Buffer, f *Function) {
 812         fmt.Fprintf(buf, "# Name: %s\n", f.String())
 813         if f.Pkg != nil {
 814                 fmt.Fprintf(buf, "# Package: %s\n", f.Pkg.Pkg.Path())
 815         }
 816         if syn := f.Synthetic; syn != "" {
 817                 fmt.Fprintln(buf, "# Synthetic:", syn)
 818         }
 819         if pos := f.Pos(); pos.IsValid() {
 820                 fmt.Fprintf(buf, "# Location: %s\n", f.Prog.Fset.Position(pos))
 821         }
 822
 823         if f.parent != nil {
 824                 fmt.Fprintf(buf, "# Parent: %s\n", f.parent.Name())
 825         }
 826
 827         from := f.pkg()
 828
 829         if f.FreeVars != nil {
 830                 buf.WriteString("# Free variables:\n")
 831                 for i, fv := range f.FreeVars {
 832                         fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, fv.Name(), relType(fv.Type(), from))
 833                 }
 834         }
 835
 836         if len(f.Locals) > 0 {
 837                 buf.WriteString("# Locals:\n")
 838                 for i, l := range f.Locals {
 839                         fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, l.Name(), relType(deref(l.Type()), from))
 840                 }
 841         }
 842         writeSignature(buf, from, f.Name(), f.Signature, f.Params)
 843         buf.WriteString(":\n")
 844
 845         if f.Blocks == nil {
 846                 buf.WriteString("\t(external)\n")
 847         }
 848
 849         for _, b := range f.Blocks {
 850                 if b == nil {
 851                         // Corrupt CFG.
 852                         fmt.Fprintf(buf, ".nil:\n")
 853                         continue
 854                 }
 855                 fmt.Fprintf(buf, "b%d:", b.Index)
 856                 if len(b.Preds) > 0 {
 857                         fmt.Fprint(buf, " ←")
 858                         for _, pred := range b.Preds {
 859                                 fmt.Fprintf(buf, " b%d", pred.Index)
 860                         }
 861                 }
 862                 if b.Comment != "" {
 863                         fmt.Fprintf(buf, " # %s", b.Comment)
 864                 }
 865                 buf.WriteByte('\n')
 866
 867                 if false { // CFG debugging
 868                         fmt.Fprintf(buf, "\t# CFG: %s --> %s --> %s\n", b.Preds, b, b.Succs)
 869                 }
 870
 871                 buf2 := &bytes.Buffer{}
 872                 for _, instr := range b.Instrs {
 873                         buf.WriteString("\t")
 874                         switch v := instr.(type) {
 875                         case Value:
 876                                 // Left-align the instruction.
 877                                 if name := v.Name(); name != "" {
 878                                         fmt.Fprintf(buf, "%s = ", name)
 879                                 }
 880                                 buf.WriteString(instr.String())
 881                         case nil:
 882                                 // Be robust against bad transforms.
 883                                 buf.WriteString("<deleted>")
 884                         default:
 885                                 buf.WriteString(instr.String())
 886                         }
 887                         buf.WriteString("\n")
 888
 889                         if f.Prog.mode&PrintSource != 0 {
 890                                 if s := instr.Source(); s != nil {
 891                                         buf2.Reset()
 892                                         format.Node(buf2, f.Prog.Fset, s)
 893                                         for {
 894                                                 line, err := buf2.ReadString('\n')
 895                                                 if len(line) == 0 {
 896                                                         break
 897                                                 }
 898                                                 buf.WriteString("\t\t> ")
 899                                                 buf.WriteString(line)
 900                                                 if line[len(line)-1] != '\n' {
 901                                                         buf.WriteString("\n")
 902                                                 }
 903                                                 if err != nil {
 904                                                         break
 905                                                 }
 906                                         }
 907                                 }
 908                         }
 909                 }
 910                 buf.WriteString("\n")
 911         }
 912 }
 913
 914 // newBasicBlock adds to f a new basic block and returns it.  It does
 915 // not automatically become the current block for subsequent calls to emit.
 916 // comment is an optional string for more readable debugging output.
 917 //
 918 func (f *Function) newBasicBlock(comment string) *BasicBlock {
 919         b := &BasicBlock{
 920                 Index:   len(f.Blocks),
 921                 Comment: comment,
 922                 parent:  f,
 923         }
 924         b.Succs = b.succs2[:0]
 925         f.Blocks = append(f.Blocks, b)
 926         return b
 927 }
 928
 929 // NewFunction returns a new synthetic Function instance belonging to
 930 // prog, with its name and signature fields set as specified.
 931 //
 932 // The caller is responsible for initializing the remaining fields of
 933 // the function object, e.g. Pkg, Params, Blocks.
 934 //
 935 // It is practically impossible for clients to construct well-formed
 936 // IR functions/packages/programs directly, so we assume this is the
 937 // job of the Builder alone.  NewFunction exists to provide clients a
 938 // little flexibility.  For example, analysis tools may wish to
 939 // construct fake Functions for the root of the callgraph, a fake
 940 // "reflect" package, etc.
 941 //
 942 // TODO(adonovan): think harder about the API here.
 943 //
 944 func (prog *Program) NewFunction(name string, sig *types.Signature, provenance string) *Function {
 945         return &Function{Prog: prog, name: name, Signature: sig, Synthetic: provenance}
 946 }
 947
 948 //lint:ignore U1000 we may make use of this for functions loaded from export data
 949 type extentNode [2]token.Pos
 950
 951 func (n extentNode) Pos() token.Pos { return n[0] }
 952 func (n extentNode) End() token.Pos { return n[1] }
 953
 954 func (f *Function) initHTML(name string) {
 955         if name == "" {
 956                 return
 957         }
 958         if rel := f.RelString(nil); rel == name {
 959                 f.wr = NewHTMLWriter("ir.html", rel, "")
 960         }
 961 }