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.
7 // This file implements the Function and BasicBlock types.
20 // addEdge adds a control-flow graph edge from from to to.
21 func addEdge(from, to *BasicBlock) {
22 from.Succs = append(from.Succs, to)
23 to.Preds = append(to.Preds, from)
26 // Parent returns the function that contains block b.
27 func (b *BasicBlock) Parent() *Function { return b.parent }
29 // String returns a human-readable label of this block.
30 // It is not guaranteed unique within the function.
32 func (b *BasicBlock) String() string {
33 return fmt.Sprintf("%d", b.Index)
36 // emit appends an instruction to the current basic block.
37 // If the instruction defines a Value, it is returned.
39 func (b *BasicBlock) emit(i Instruction) Value {
41 b.Instrs = append(b.Instrs, i)
46 // predIndex returns the i such that b.Preds[i] == c or panics if
48 func (b *BasicBlock) predIndex(c *BasicBlock) int {
49 for i, pred := range b.Preds {
54 panic(fmt.Sprintf("no edge %s -> %s", c, b))
57 // hasPhi returns true if b.Instrs contains φ-nodes.
58 func (b *BasicBlock) hasPhi() bool {
59 _, ok := b.Instrs[0].(*Phi)
63 // phis returns the prefix of b.Instrs containing all the block's φ-nodes.
64 func (b *BasicBlock) phis() []Instruction {
65 for i, instr := range b.Instrs {
66 if _, ok := instr.(*Phi); !ok {
70 return nil // unreachable in well-formed blocks
73 // replacePred replaces all occurrences of p in b's predecessor list with q.
74 // Ordinarily there should be at most one.
76 func (b *BasicBlock) replacePred(p, q *BasicBlock) {
77 for i, pred := range b.Preds {
84 // replaceSucc replaces all occurrences of p in b's successor list with q.
85 // Ordinarily there should be at most one.
87 func (b *BasicBlock) replaceSucc(p, q *BasicBlock) {
88 for i, succ := range b.Succs {
95 // removePred removes all occurrences of p in b's
96 // predecessor list and φ-nodes.
97 // Ordinarily there should be at most one.
99 func (b *BasicBlock) removePred(p *BasicBlock) {
102 // We must preserve edge order for φ-nodes.
104 for i, pred := range b.Preds {
106 b.Preds[j] = b.Preds[i]
107 // Strike out φ-edge too.
108 for _, instr := range phis {
110 phi.Edges[j] = phi.Edges[i]
115 // Nil out b.Preds[j:] and φ-edges[j:] to aid GC.
116 for i := j; i < len(b.Preds); i++ {
118 for _, instr := range phis {
119 instr.(*Phi).Edges[i] = nil
122 b.Preds = b.Preds[:j]
123 for _, instr := range phis {
125 phi.Edges = phi.Edges[:j]
129 // Destinations associated with unlabelled for/switch/select stmts.
130 // We push/pop one of these as we enter/leave each construct and for
131 // each BranchStmt we scan for the innermost target of the right type.
133 type targets struct {
134 tail *targets // rest of stack
136 _continue *BasicBlock
137 _fallthrough *BasicBlock
140 // Destinations associated with a labelled block.
141 // We populate these as labels are encountered in forward gotos or
142 // labelled statements.
147 _continue *BasicBlock
150 // labelledBlock returns the branch target associated with the
151 // specified label, creating it if needed.
153 func (f *Function) labelledBlock(label *ast.Ident) *lblock {
154 lb := f.lblocks[label.Obj]
156 lb = &lblock{_goto: f.newBasicBlock(label.Name)}
157 if f.lblocks == nil {
158 f.lblocks = make(map[*ast.Object]*lblock)
160 f.lblocks[label.Obj] = lb
165 // addParam adds a (non-escaping) parameter to f.Params of the
166 // specified name, type and source position.
168 func (f *Function) addParam(name string, typ types.Type, pos token.Pos) *Parameter {
175 f.Params = append(f.Params, v)
179 func (f *Function) addParamObj(obj types.Object) *Parameter {
182 name = fmt.Sprintf("arg%d", len(f.Params))
184 param := f.addParam(name, obj.Type(), obj.Pos())
189 // addSpilledParam declares a parameter that is pre-spilled to the
190 // stack; the function body will load/store the spilled location.
191 // Subsequent lifting will eliminate spills where possible.
193 func (f *Function) addSpilledParam(obj types.Object) {
194 param := f.addParamObj(obj)
195 spill := &Alloc{Comment: obj.Name()}
196 spill.setType(types.NewPointer(obj.Type()))
197 spill.setPos(obj.Pos())
198 f.objects[obj] = spill
199 f.Locals = append(f.Locals, spill)
201 f.emit(&Store{Addr: spill, Val: param})
204 // startBody initializes the function prior to generating SSA code for its body.
205 // Precondition: f.Type() already set.
207 func (f *Function) startBody() {
208 f.currentBlock = f.newBasicBlock("entry")
209 f.objects = make(map[types.Object]Value) // needed for some synthetics, e.g. init
212 // createSyntacticParams populates f.Params and generates code (spills
213 // and named result locals) for all the parameters declared in the
214 // syntax. In addition it populates the f.objects mapping.
217 // f.startBody() was called.
219 // len(f.Params) == len(f.Signature.Params) + (f.Signature.Recv() ? 1 : 0)
221 func (f *Function) createSyntacticParams(recv *ast.FieldList, functype *ast.FuncType) {
222 // Receiver (at most one inner iteration).
224 for _, field := range recv.List {
225 for _, n := range field.Names {
226 f.addSpilledParam(f.Pkg.info.Defs[n])
228 // Anonymous receiver? No need to spill.
229 if field.Names == nil {
230 f.addParamObj(f.Signature.Recv())
236 if functype.Params != nil {
237 n := len(f.Params) // 1 if has recv, 0 otherwise
238 for _, field := range functype.Params.List {
239 for _, n := range field.Names {
240 f.addSpilledParam(f.Pkg.info.Defs[n])
242 // Anonymous parameter? No need to spill.
243 if field.Names == nil {
244 f.addParamObj(f.Signature.Params().At(len(f.Params) - n))
250 if functype.Results != nil {
251 for _, field := range functype.Results.List {
252 // Implicit "var" decl of locals for named results.
253 for _, n := range field.Names {
254 f.namedResults = append(f.namedResults, f.addLocalForIdent(n))
260 type setNumable interface {
264 // numberRegisters assigns numbers to all SSA registers
265 // (value-defining Instructions) in f, to aid debugging.
266 // (Non-Instruction Values are named at construction.)
268 func numberRegisters(f *Function) {
270 for _, b := range f.Blocks {
271 for _, instr := range b.Instrs {
272 switch instr.(type) {
274 instr.(setNumable).setNum(v)
281 // buildReferrers populates the def/use information in all non-nil
282 // Value.Referrers slice.
283 // Precondition: all such slices are initially empty.
284 func buildReferrers(f *Function) {
286 for _, b := range f.Blocks {
287 for _, instr := range b.Instrs {
288 rands = instr.Operands(rands[:0]) // recycle storage
289 for _, rand := range rands {
290 if r := *rand; r != nil {
291 if ref := r.Referrers(); ref != nil {
292 *ref = append(*ref, instr)
300 // finishBody() finalizes the function after SSA code generation of its body.
301 func (f *Function) finishBody() {
306 // Don't pin the AST in memory (except in debug mode).
307 if n := f.syntax; n != nil && !f.debugInfo() {
308 f.syntax = extentNode{n.Pos(), n.End()}
311 // Remove from f.Locals any Allocs that escape to the heap.
313 for _, l := range f.Locals {
319 // Nil out f.Locals[j:] to aid GC.
320 for i := j; i < len(f.Locals); i++ {
323 f.Locals = f.Locals[:j]
331 if f.Prog.mode&NaiveForm == 0 {
332 // For debugging pre-state of lifting pass:
333 // numberRegisters(f)
334 // f.WriteTo(os.Stderr)
338 f.namedResults = nil // (used by lifting)
342 if f.Prog.mode&PrintFunctions != 0 {
348 if f.Prog.mode&SanityCheckFunctions != 0 {
349 mustSanityCheck(f, nil)
353 // removeNilBlocks eliminates nils from f.Blocks and updates each
354 // BasicBlock.Index. Use this after any pass that may delete blocks.
356 func (f *Function) removeNilBlocks() {
358 for _, b := range f.Blocks {
365 // Nil out f.Blocks[j:] to aid GC.
366 for i := j; i < len(f.Blocks); i++ {
369 f.Blocks = f.Blocks[:j]
372 // SetDebugMode sets the debug mode for package pkg. If true, all its
373 // functions will include full debug info. This greatly increases the
374 // size of the instruction stream, and causes Functions to depend upon
375 // the ASTs, potentially keeping them live in memory for longer.
377 func (pkg *Package) SetDebugMode(debug bool) {
378 // TODO(adonovan): do we want ast.File granularity?
382 // debugInfo reports whether debug info is wanted for this function.
383 func (f *Function) debugInfo() bool {
384 return f.Pkg != nil && f.Pkg.debug
387 // addNamedLocal creates a local variable, adds it to function f and
388 // returns it. Its name and type are taken from obj. Subsequent
389 // calls to f.lookup(obj) will return the same local.
391 func (f *Function) addNamedLocal(obj types.Object) *Alloc {
392 l := f.addLocal(obj.Type(), obj.Pos())
393 l.Comment = obj.Name()
398 func (f *Function) addLocalForIdent(id *ast.Ident) *Alloc {
399 return f.addNamedLocal(f.Pkg.info.Defs[id])
402 // addLocal creates an anonymous local variable of type typ, adds it
403 // to function f and returns it. pos is the optional source location.
405 func (f *Function) addLocal(typ types.Type, pos token.Pos) *Alloc {
407 v.setType(types.NewPointer(typ))
409 f.Locals = append(f.Locals, v)
414 // lookup returns the address of the named variable identified by obj
415 // that is local to function f or one of its enclosing functions.
416 // If escaping, the reference comes from a potentially escaping pointer
417 // expression and the referent must be heap-allocated.
419 func (f *Function) lookup(obj types.Object, escaping bool) Value {
420 if v, ok := f.objects[obj]; ok {
421 if alloc, ok := v.(*Alloc); ok && escaping {
424 return v // function-local var (address)
427 // Definition must be in an enclosing function;
428 // plumb it through intervening closures.
430 panic("no ssa.Value for " + obj.String())
432 outer := f.parent.lookup(obj, true) // escaping
441 f.FreeVars = append(f.FreeVars, v)
445 // emit emits the specified instruction to function f.
446 func (f *Function) emit(instr Instruction) Value {
447 return f.currentBlock.emit(instr)
450 // RelString returns the full name of this function, qualified by
451 // package name, receiver type, etc.
453 // The specific formatting rules are not guaranteed and may change.
456 // "math.IsNaN" // a package-level function
457 // "(*bytes.Buffer).Bytes" // a declared method or a wrapper
458 // "(*bytes.Buffer).Bytes$thunk" // thunk (func wrapping method; receiver is param 0)
459 // "(*bytes.Buffer).Bytes$bound" // bound (func wrapping method; receiver supplied by closure)
460 // "main.main$1" // an anonymous function in main
461 // "main.init#1" // a declared init function
462 // "main.init" // the synthesized package initializer
464 // When these functions are referred to from within the same package
465 // (i.e. from == f.Pkg.Object), they are rendered without the package path.
466 // For example: "IsNaN", "(*Buffer).Bytes", etc.
468 // All non-synthetic functions have distinct package-qualified names.
469 // (But two methods may have the same name "(T).f" if one is a synthetic
470 // wrapper promoting a non-exported method "f" from another package; in
471 // that case, the strings are equal but the identifiers "f" are distinct.)
473 func (f *Function) RelString(from *types.Package) string {
476 // An anonymous function's Name() looks like "parentName$1",
477 // but its String() should include the type/package/etc.
478 parent := f.parent.RelString(from)
479 for i, anon := range f.parent.AnonFuncs {
481 return fmt.Sprintf("%s$%d", parent, 1+i)
485 return f.name // should never happen
488 // Method (declared or wrapper)?
489 if recv := f.Signature.Recv(); recv != nil {
490 return f.relMethod(from, recv.Type())
495 return f.relMethod(from, f.method.Recv())
499 if len(f.FreeVars) == 1 && strings.HasSuffix(f.name, "$bound") {
500 return f.relMethod(from, f.FreeVars[0].Type())
503 // Package-level function?
504 // Prefix with package name for cross-package references only.
505 if p := f.pkg(); p != nil && p != from {
506 return fmt.Sprintf("%s.%s", p.Path(), f.name)
513 func (f *Function) relMethod(from *types.Package, recv types.Type) string {
514 return fmt.Sprintf("(%s).%s", relType(recv, from), f.name)
517 // writeSignature writes to buf the signature sig in declaration syntax.
518 func writeSignature(buf *bytes.Buffer, from *types.Package, name string, sig *types.Signature, params []*Parameter) {
519 buf.WriteString("func ")
520 if recv := sig.Recv(); recv != nil {
522 if n := params[0].Name(); n != "" {
526 types.WriteType(buf, params[0].Type(), types.RelativeTo(from))
527 buf.WriteString(") ")
529 buf.WriteString(name)
530 types.WriteSignature(buf, sig, types.RelativeTo(from))
533 func (f *Function) pkg() *types.Package {
540 var _ io.WriterTo = (*Function)(nil) // *Function implements io.Writer
542 func (f *Function) WriteTo(w io.Writer) (int64, error) {
544 WriteFunction(&buf, f)
545 n, err := w.Write(buf.Bytes())
549 // WriteFunction writes to buf a human-readable "disassembly" of f.
550 func WriteFunction(buf *bytes.Buffer, f *Function) {
551 fmt.Fprintf(buf, "# Name: %s\n", f.String())
553 fmt.Fprintf(buf, "# Package: %s\n", f.Pkg.Pkg.Path())
555 if syn := f.Synthetic; syn != "" {
556 fmt.Fprintln(buf, "# Synthetic:", syn)
558 if pos := f.Pos(); pos.IsValid() {
559 fmt.Fprintf(buf, "# Location: %s\n", f.Prog.Fset.Position(pos))
563 fmt.Fprintf(buf, "# Parent: %s\n", f.parent.Name())
566 if f.Recover != nil {
567 fmt.Fprintf(buf, "# Recover: %s\n", f.Recover)
572 if f.FreeVars != nil {
573 buf.WriteString("# Free variables:\n")
574 for i, fv := range f.FreeVars {
575 fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, fv.Name(), relType(fv.Type(), from))
579 if len(f.Locals) > 0 {
580 buf.WriteString("# Locals:\n")
581 for i, l := range f.Locals {
582 fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, l.Name(), relType(deref(l.Type()), from))
585 writeSignature(buf, from, f.Name(), f.Signature, f.Params)
586 buf.WriteString(":\n")
589 buf.WriteString("\t(external)\n")
592 // NB. column calculations are confused by non-ASCII
593 // characters and assume 8-space tabs.
594 const punchcard = 80 // for old time's sake.
596 for _, b := range f.Blocks {
599 fmt.Fprintf(buf, ".nil:\n")
602 n, _ := fmt.Fprintf(buf, "%d:", b.Index)
603 bmsg := fmt.Sprintf("%s P:%d S:%d", b.Comment, len(b.Preds), len(b.Succs))
604 fmt.Fprintf(buf, "%*s%s\n", punchcard-1-n-len(bmsg), "", bmsg)
606 if false { // CFG debugging
607 fmt.Fprintf(buf, "\t# CFG: %s --> %s --> %s\n", b.Preds, b, b.Succs)
609 for _, instr := range b.Instrs {
610 buf.WriteString("\t")
611 switch v := instr.(type) {
613 l := punchcard - tabwidth
614 // Left-align the instruction.
615 if name := v.Name(); name != "" {
616 n, _ := fmt.Fprintf(buf, "%s = ", name)
619 n, _ := buf.WriteString(instr.String())
621 // Right-align the type if there's space.
622 if t := v.Type(); t != nil {
624 ts := relType(t, from)
625 l -= len(ts) + len(" ") // (spaces before and after type)
627 fmt.Fprintf(buf, "%*s", l, "")
632 // Be robust against bad transforms.
633 buf.WriteString("<deleted>")
635 buf.WriteString(instr.String())
637 buf.WriteString("\n")
640 fmt.Fprintf(buf, "\n")
643 // newBasicBlock adds to f a new basic block and returns it. It does
644 // not automatically become the current block for subsequent calls to emit.
645 // comment is an optional string for more readable debugging output.
647 func (f *Function) newBasicBlock(comment string) *BasicBlock {
649 Index: len(f.Blocks),
653 b.Succs = b.succs2[:0]
654 f.Blocks = append(f.Blocks, b)
658 // NewFunction returns a new synthetic Function instance belonging to
659 // prog, with its name and signature fields set as specified.
661 // The caller is responsible for initializing the remaining fields of
662 // the function object, e.g. Pkg, Params, Blocks.
664 // It is practically impossible for clients to construct well-formed
665 // SSA functions/packages/programs directly, so we assume this is the
666 // job of the Builder alone. NewFunction exists to provide clients a
667 // little flexibility. For example, analysis tools may wish to
668 // construct fake Functions for the root of the callgraph, a fake
669 // "reflect" package, etc.
671 // TODO(adonovan): think harder about the API here.
673 func (prog *Program) NewFunction(name string, sig *types.Signature, provenance string) *Function {
674 return &Function{Prog: prog, name: name, Signature: sig, Synthetic: provenance}
677 type extentNode [2]token.Pos
679 func (n extentNode) Pos() token.Pos { return n[0] }
680 func (n extentNode) End() token.Pos { return n[1] }
682 // Syntax returns an ast.Node whose Pos/End methods provide the
683 // lexical extent of the function if it was defined by Go source code
684 // (f.Synthetic==""), or nil otherwise.
686 // If f was built with debug information (see Package.SetDebugRef),
687 // the result is the *ast.FuncDecl or *ast.FuncLit that declared the
688 // function. Otherwise, it is an opaque Node providing only position
689 // information; this avoids pinning the AST in memory.
691 func (f *Function) Syntax() ast.Node { return f.syntax }