Source file src/pkg/cmd/link/internal/ld/deadcode.go

     1	// Copyright 2016 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 ld
     6	
     7	import (
     8		"cmd/internal/objabi"
     9		"cmd/internal/sys"
    10		"cmd/link/internal/sym"
    11		"fmt"
    12		"strings"
    13		"unicode"
    14	)
    15	
    16	// deadcode marks all reachable symbols.
    17	//
    18	// The basis of the dead code elimination is a flood fill of symbols,
    19	// following their relocations, beginning at *flagEntrySymbol.
    20	//
    21	// This flood fill is wrapped in logic for pruning unused methods.
    22	// All methods are mentioned by relocations on their receiver's *rtype.
    23	// These relocations are specially defined as R_METHODOFF by the compiler
    24	// so we can detect and manipulated them here.
    25	//
    26	// There are three ways a method of a reachable type can be invoked:
    27	//
    28	//	1. direct call
    29	//	2. through a reachable interface type
    30	//	3. reflect.Value.Call, .Method, or reflect.Method.Func
    31	//
    32	// The first case is handled by the flood fill, a directly called method
    33	// is marked as reachable.
    34	//
    35	// The second case is handled by decomposing all reachable interface
    36	// types into method signatures. Each encountered method is compared
    37	// against the interface method signatures, if it matches it is marked
    38	// as reachable. This is extremely conservative, but easy and correct.
    39	//
    40	// The third case is handled by looking to see if any of:
    41	//	- reflect.Value.Call is reachable
    42	//	- reflect.Value.Method is reachable
    43	// 	- reflect.Type.Method or MethodByName is called.
    44	// If any of these happen, all bets are off and all exported methods
    45	// of reachable types are marked reachable.
    46	//
    47	// Any unreached text symbols are removed from ctxt.Textp.
    48	func deadcode(ctxt *Link) {
    49		if ctxt.Debugvlog != 0 {
    50			ctxt.Logf("%5.2f deadcode\n", Cputime())
    51		}
    52	
    53		d := &deadcodepass{
    54			ctxt:        ctxt,
    55			ifaceMethod: make(map[methodsig]bool),
    56		}
    57	
    58		// First, flood fill any symbols directly reachable in the call
    59		// graph from *flagEntrySymbol. Ignore all methods not directly called.
    60		d.init()
    61		d.flood()
    62	
    63		callSym := ctxt.Syms.ROLookup("reflect.Value.Call", sym.SymVerABIInternal)
    64		methSym := ctxt.Syms.ROLookup("reflect.Value.Method", sym.SymVerABIInternal)
    65		reflectSeen := false
    66	
    67		if ctxt.DynlinkingGo() {
    68			// Exported methods may satisfy interfaces we don't know
    69			// about yet when dynamically linking.
    70			reflectSeen = true
    71		}
    72	
    73		for {
    74			if !reflectSeen {
    75				if d.reflectMethod || (callSym != nil && callSym.Attr.Reachable()) || (methSym != nil && methSym.Attr.Reachable()) {
    76					// Methods might be called via reflection. Give up on
    77					// static analysis, mark all exported methods of
    78					// all reachable types as reachable.
    79					reflectSeen = true
    80				}
    81			}
    82	
    83			// Mark all methods that could satisfy a discovered
    84			// interface as reachable. We recheck old marked interfaces
    85			// as new types (with new methods) may have been discovered
    86			// in the last pass.
    87			var rem []methodref
    88			for _, m := range d.markableMethods {
    89				if (reflectSeen && m.isExported()) || d.ifaceMethod[m.m] {
    90					d.markMethod(m)
    91				} else {
    92					rem = append(rem, m)
    93				}
    94			}
    95			d.markableMethods = rem
    96	
    97			if len(d.markQueue) == 0 {
    98				// No new work was discovered. Done.
    99				break
   100			}
   101			d.flood()
   102		}
   103	
   104		// Remove all remaining unreached R_METHODOFF relocations.
   105		for _, m := range d.markableMethods {
   106			for _, r := range m.r {
   107				d.cleanupReloc(r)
   108			}
   109		}
   110	
   111		if ctxt.BuildMode != BuildModeShared {
   112			// Keep a itablink if the symbol it points at is being kept.
   113			// (When BuildModeShared, always keep itablinks.)
   114			for _, s := range ctxt.Syms.Allsym {
   115				if strings.HasPrefix(s.Name, "go.itablink.") {
   116					s.Attr.Set(sym.AttrReachable, len(s.R) == 1 && s.R[0].Sym.Attr.Reachable())
   117				}
   118			}
   119		}
   120	
   121		for _, lib := range ctxt.Library {
   122			lib.Textp = lib.Textp[:0]
   123		}
   124	
   125		// Remove dead text but keep file information (z symbols).
   126		textp := make([]*sym.Symbol, 0, len(ctxt.Textp))
   127		for _, s := range ctxt.Textp {
   128			if s.Attr.Reachable() {
   129				if s.Lib != nil {
   130					s.Lib.Textp = append(s.Lib.Textp, s)
   131				}
   132				textp = append(textp, s)
   133			}
   134		}
   135		ctxt.Textp = textp
   136	}
   137	
   138	// methodref holds the relocations from a receiver type symbol to its
   139	// method. There are three relocations, one for each of the fields in
   140	// the reflect.method struct: mtyp, ifn, and tfn.
   141	type methodref struct {
   142		m   methodsig
   143		src *sym.Symbol   // receiver type symbol
   144		r   [3]*sym.Reloc // R_METHODOFF relocations to fields of runtime.method
   145	}
   146	
   147	func (m methodref) ifn() *sym.Symbol { return m.r[1].Sym }
   148	
   149	func (m methodref) isExported() bool {
   150		for _, r := range m.m {
   151			return unicode.IsUpper(r)
   152		}
   153		panic("methodref has no signature")
   154	}
   155	
   156	// deadcodepass holds state for the deadcode flood fill.
   157	type deadcodepass struct {
   158		ctxt            *Link
   159		markQueue       []*sym.Symbol      // symbols to flood fill in next pass
   160		ifaceMethod     map[methodsig]bool // methods declared in reached interfaces
   161		markableMethods []methodref        // methods of reached types
   162		reflectMethod   bool
   163	}
   164	
   165	func (d *deadcodepass) cleanupReloc(r *sym.Reloc) {
   166		if r.Sym.Attr.Reachable() {
   167			r.Type = objabi.R_ADDROFF
   168		} else {
   169			if d.ctxt.Debugvlog > 1 {
   170				d.ctxt.Logf("removing method %s\n", r.Sym.Name)
   171			}
   172			r.Sym = nil
   173			r.Siz = 0
   174		}
   175	}
   176	
   177	// mark appends a symbol to the mark queue for flood filling.
   178	func (d *deadcodepass) mark(s, parent *sym.Symbol) {
   179		if s == nil || s.Attr.Reachable() {
   180			return
   181		}
   182		if s.Attr.ReflectMethod() {
   183			d.reflectMethod = true
   184		}
   185		if *flagDumpDep {
   186			p := "_"
   187			if parent != nil {
   188				p = parent.Name
   189			}
   190			fmt.Printf("%s -> %s\n", p, s.Name)
   191		}
   192		s.Attr |= sym.AttrReachable
   193		if d.ctxt.Reachparent != nil {
   194			d.ctxt.Reachparent[s] = parent
   195		}
   196		d.markQueue = append(d.markQueue, s)
   197	}
   198	
   199	// markMethod marks a method as reachable.
   200	func (d *deadcodepass) markMethod(m methodref) {
   201		for _, r := range m.r {
   202			d.mark(r.Sym, m.src)
   203			r.Type = objabi.R_ADDROFF
   204		}
   205	}
   206	
   207	// init marks all initial symbols as reachable.
   208	// In a typical binary, this is *flagEntrySymbol.
   209	func (d *deadcodepass) init() {
   210		var names []string
   211	
   212		if d.ctxt.BuildMode == BuildModeShared {
   213			// Mark all symbols defined in this library as reachable when
   214			// building a shared library.
   215			for _, s := range d.ctxt.Syms.Allsym {
   216				if s.Type != 0 && s.Type != sym.SDYNIMPORT {
   217					d.mark(s, nil)
   218				}
   219			}
   220		} else {
   221			// In a normal binary, start at main.main and the init
   222			// functions and mark what is reachable from there.
   223	
   224			if d.ctxt.linkShared && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
   225				names = append(names, "main.main", "main..inittask")
   226			} else {
   227				// The external linker refers main symbol directly.
   228				if d.ctxt.LinkMode == LinkExternal && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
   229					if d.ctxt.HeadType == objabi.Hwindows && d.ctxt.Arch.Family == sys.I386 {
   230						*flagEntrySymbol = "_main"
   231					} else {
   232						*flagEntrySymbol = "main"
   233					}
   234				}
   235				names = append(names, *flagEntrySymbol)
   236				if d.ctxt.BuildMode == BuildModePlugin {
   237					names = append(names, objabi.PathToPrefix(*flagPluginPath)+"..inittask", objabi.PathToPrefix(*flagPluginPath)+".main", "go.plugin.tabs")
   238	
   239					// We don't keep the go.plugin.exports symbol,
   240					// but we do keep the symbols it refers to.
   241					exports := d.ctxt.Syms.ROLookup("go.plugin.exports", 0)
   242					if exports != nil {
   243						for i := range exports.R {
   244							d.mark(exports.R[i].Sym, nil)
   245						}
   246					}
   247				}
   248			}
   249			for _, s := range dynexp {
   250				d.mark(s, nil)
   251			}
   252		}
   253	
   254		for _, name := range names {
   255			// Mark symbol as an data/ABI0 symbol.
   256			d.mark(d.ctxt.Syms.ROLookup(name, 0), nil)
   257			// Also mark any Go functions (internal ABI).
   258			d.mark(d.ctxt.Syms.ROLookup(name, sym.SymVerABIInternal), nil)
   259		}
   260	}
   261	
   262	// flood fills symbols reachable from the markQueue symbols.
   263	// As it goes, it collects methodref and interface method declarations.
   264	func (d *deadcodepass) flood() {
   265		for len(d.markQueue) > 0 {
   266			s := d.markQueue[0]
   267			d.markQueue = d.markQueue[1:]
   268			if s.Type == sym.STEXT {
   269				if d.ctxt.Debugvlog > 1 {
   270					d.ctxt.Logf("marktext %s\n", s.Name)
   271				}
   272				if s.FuncInfo != nil {
   273					for _, a := range s.FuncInfo.Autom {
   274						d.mark(a.Gotype, s)
   275					}
   276				}
   277	
   278			}
   279	
   280			if strings.HasPrefix(s.Name, "type.") && s.Name[5] != '.' {
   281				if len(s.P) == 0 {
   282					// Probably a bug. The undefined symbol check
   283					// later will give a better error than deadcode.
   284					continue
   285				}
   286				if decodetypeKind(d.ctxt.Arch, s)&kindMask == kindInterface {
   287					for _, sig := range decodeIfaceMethods(d.ctxt.Arch, s) {
   288						if d.ctxt.Debugvlog > 1 {
   289							d.ctxt.Logf("reached iface method: %s\n", sig)
   290						}
   291						d.ifaceMethod[sig] = true
   292					}
   293				}
   294			}
   295	
   296			mpos := 0 // 0-3, the R_METHODOFF relocs of runtime.uncommontype
   297			var methods []methodref
   298			for i := range s.R {
   299				r := &s.R[i]
   300				if r.Sym == nil {
   301					continue
   302				}
   303				if r.Type == objabi.R_WEAKADDROFF {
   304					// An R_WEAKADDROFF relocation is not reason
   305					// enough to mark the pointed-to symbol as
   306					// reachable.
   307					continue
   308				}
   309				if r.Sym.Type == sym.SABIALIAS {
   310					// Patch this relocation through the
   311					// ABI alias before marking.
   312					r.Sym = resolveABIAlias(r.Sym)
   313				}
   314				if r.Type != objabi.R_METHODOFF {
   315					d.mark(r.Sym, s)
   316					continue
   317				}
   318				// Collect rtype pointers to methods for
   319				// later processing in deadcode.
   320				if mpos == 0 {
   321					m := methodref{src: s}
   322					m.r[0] = r
   323					methods = append(methods, m)
   324				} else {
   325					methods[len(methods)-1].r[mpos] = r
   326				}
   327				mpos++
   328				if mpos == len(methodref{}.r) {
   329					mpos = 0
   330				}
   331			}
   332			if len(methods) > 0 {
   333				// Decode runtime type information for type methods
   334				// to help work out which methods can be called
   335				// dynamically via interfaces.
   336				methodsigs := decodetypeMethods(d.ctxt.Arch, s)
   337				if len(methods) != len(methodsigs) {
   338					panic(fmt.Sprintf("%q has %d method relocations for %d methods", s.Name, len(methods), len(methodsigs)))
   339				}
   340				for i, m := range methodsigs {
   341					name := string(m)
   342					name = name[:strings.Index(name, "(")]
   343					if !strings.HasSuffix(methods[i].ifn().Name, name) {
   344						panic(fmt.Sprintf("%q relocation for %q does not match method %q", s.Name, methods[i].ifn().Name, name))
   345					}
   346					methods[i].m = m
   347				}
   348				d.markableMethods = append(d.markableMethods, methods...)
   349			}
   350	
   351			if s.FuncInfo != nil {
   352				for i := range s.FuncInfo.Funcdata {
   353					d.mark(s.FuncInfo.Funcdata[i], s)
   354				}
   355			}
   356			d.mark(s.Gotype, s)
   357			d.mark(s.Sub, s)
   358			d.mark(s.Outer, s)
   359		}
   360	}
   361	

View as plain text