Debian Codegraph @

go/ir/func.go

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