blob: 540f4068cb8ea8be8a2816a0f0631f4ce49c745b [file] [log] [blame]
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ld
import (
"cmd/internal/objabi"
"cmd/internal/sys"
"cmd/link/internal/sym"
"fmt"
"strings"
"unicode"
)
// deadcode marks all reachable symbols.
//
// The basis of the dead code elimination is a flood fill of symbols,
// following their relocations, beginning at *flagEntrySymbol.
//
// This flood fill is wrapped in logic for pruning unused methods.
// All methods are mentioned by relocations on their receiver's *rtype.
// These relocations are specially defined as R_METHODOFF by the compiler
// so we can detect and manipulated them here.
//
// There are three ways a method of a reachable type can be invoked:
//
// 1. direct call
// 2. through a reachable interface type
// 3. reflect.Value.Call, .Method, or reflect.Method.Func
//
// The first case is handled by the flood fill, a directly called method
// is marked as reachable.
//
// The second case is handled by decomposing all reachable interface
// types into method signatures. Each encountered method is compared
// against the interface method signatures, if it matches it is marked
// as reachable. This is extremely conservative, but easy and correct.
//
// The third case is handled by looking to see if any of:
// - reflect.Value.Call is reachable
// - reflect.Value.Method is reachable
// - reflect.Type.Method or MethodByName is called.
// If any of these happen, all bets are off and all exported methods
// of reachable types are marked reachable.
//
// Any unreached text symbols are removed from ctxt.Textp.
func deadcode(ctxt *Link) {
if ctxt.Debugvlog != 0 {
ctxt.Logf("%5.2f deadcode\n", Cputime())
}
d := &deadcodepass{
ctxt: ctxt,
ifaceMethod: make(map[methodsig]bool),
}
// First, flood fill any symbols directly reachable in the call
// graph from *flagEntrySymbol. Ignore all methods not directly called.
d.init()
d.flood()
callSym := ctxt.Syms.ROLookup("reflect.Value.Call", 0)
methSym := ctxt.Syms.ROLookup("reflect.Value.Method", 0)
reflectSeen := false
if ctxt.DynlinkingGo() {
// Exported methods may satisfy interfaces we don't know
// about yet when dynamically linking.
reflectSeen = true
}
for {
if !reflectSeen {
if d.reflectMethod || (callSym != nil && callSym.Attr.Reachable()) || (methSym != nil && methSym.Attr.Reachable()) {
// Methods might be called via reflection. Give up on
// static analysis, mark all exported methods of
// all reachable types as reachable.
reflectSeen = true
}
}
// Mark all methods that could satisfy a discovered
// interface as reachable. We recheck old marked interfaces
// as new types (with new methods) may have been discovered
// in the last pass.
var rem []methodref
for _, m := range d.markableMethods {
if (reflectSeen && m.isExported()) || d.ifaceMethod[m.m] {
d.markMethod(m)
} else {
rem = append(rem, m)
}
}
d.markableMethods = rem
if len(d.markQueue) == 0 {
// No new work was discovered. Done.
break
}
d.flood()
}
// Remove all remaining unreached R_METHODOFF relocations.
for _, m := range d.markableMethods {
for _, r := range m.r {
d.cleanupReloc(r)
}
}
if ctxt.BuildMode != BuildModeShared {
// Keep a itablink if the symbol it points at is being kept.
// (When BuildModeShared, always keep itablinks.)
for _, s := range ctxt.Syms.Allsym {
if strings.HasPrefix(s.Name, "go.itablink.") {
s.Attr.Set(sym.AttrReachable, len(s.R) == 1 && s.R[0].Sym.Attr.Reachable())
}
}
}
for _, lib := range ctxt.Library {
lib.Textp = lib.Textp[:0]
}
// Remove dead text but keep file information (z symbols).
textp := make([]*sym.Symbol, 0, len(ctxt.Textp))
for _, s := range ctxt.Textp {
if s.Attr.Reachable() {
if s.Lib != nil {
s.Lib.Textp = append(s.Lib.Textp, s)
}
textp = append(textp, s)
}
}
ctxt.Textp = textp
}
// methodref holds the relocations from a receiver type symbol to its
// method. There are three relocations, one for each of the fields in
// the reflect.method struct: mtyp, ifn, and tfn.
type methodref struct {
m methodsig
src *sym.Symbol // receiver type symbol
r [3]*sym.Reloc // R_METHODOFF relocations to fields of runtime.method
}
func (m methodref) ifn() *sym.Symbol { return m.r[1].Sym }
func (m methodref) isExported() bool {
for _, r := range m.m {
return unicode.IsUpper(r)
}
panic("methodref has no signature")
}
// deadcodepass holds state for the deadcode flood fill.
type deadcodepass struct {
ctxt *Link
markQueue []*sym.Symbol // symbols to flood fill in next pass
ifaceMethod map[methodsig]bool // methods declared in reached interfaces
markableMethods []methodref // methods of reached types
reflectMethod bool
}
func (d *deadcodepass) cleanupReloc(r *sym.Reloc) {
if r.Sym.Attr.Reachable() {
r.Type = objabi.R_ADDROFF
} else {
if d.ctxt.Debugvlog > 1 {
d.ctxt.Logf("removing method %s\n", r.Sym.Name)
}
r.Sym = nil
r.Siz = 0
}
}
// mark appends a symbol to the mark queue for flood filling.
func (d *deadcodepass) mark(s, parent *sym.Symbol) {
if s == nil || s.Attr.Reachable() {
return
}
if s.Attr.ReflectMethod() {
d.reflectMethod = true
}
if *flagDumpDep {
p := "_"
if parent != nil {
p = parent.Name
}
fmt.Printf("%s -> %s\n", p, s.Name)
}
s.Attr |= sym.AttrReachable
if d.ctxt.Reachparent != nil {
d.ctxt.Reachparent[s] = parent
}
d.markQueue = append(d.markQueue, s)
}
// markMethod marks a method as reachable.
func (d *deadcodepass) markMethod(m methodref) {
for _, r := range m.r {
d.mark(r.Sym, m.src)
r.Type = objabi.R_ADDROFF
}
}
// init marks all initial symbols as reachable.
// In a typical binary, this is *flagEntrySymbol.
func (d *deadcodepass) init() {
var names []string
if d.ctxt.Arch.Family == sys.ARM {
// mark some functions that are only referenced after linker code editing
names = append(names, "runtime.read_tls_fallback")
}
if d.ctxt.BuildMode == BuildModeShared {
// Mark all symbols defined in this library as reachable when
// building a shared library.
for _, s := range d.ctxt.Syms.Allsym {
if s.Type != 0 && s.Type != sym.SDYNIMPORT {
d.mark(s, nil)
}
}
} else {
// In a normal binary, start at main.main and the init
// functions and mark what is reachable from there.
if d.ctxt.linkShared && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
names = append(names, "main.main", "main.init")
} else {
// The external linker refers main symbol directly.
if d.ctxt.LinkMode == LinkExternal && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
if d.ctxt.HeadType == objabi.Hwindows && d.ctxt.Arch.Family == sys.I386 {
*flagEntrySymbol = "_main"
} else {
*flagEntrySymbol = "main"
}
}
names = append(names, *flagEntrySymbol)
if d.ctxt.BuildMode == BuildModePlugin {
names = append(names, objabi.PathToPrefix(*flagPluginPath)+".init", objabi.PathToPrefix(*flagPluginPath)+".main", "go.plugin.tabs")
// We don't keep the go.plugin.exports symbol,
// but we do keep the symbols it refers to.
exports := d.ctxt.Syms.ROLookup("go.plugin.exports", 0)
if exports != nil {
for _, r := range exports.R {
d.mark(r.Sym, nil)
}
}
}
}
for _, s := range dynexp {
d.mark(s, nil)
}
}
for _, name := range names {
d.mark(d.ctxt.Syms.ROLookup(name, 0), nil)
}
}
// flood fills symbols reachable from the markQueue symbols.
// As it goes, it collects methodref and interface method declarations.
func (d *deadcodepass) flood() {
for len(d.markQueue) > 0 {
s := d.markQueue[0]
d.markQueue = d.markQueue[1:]
if s.Type == sym.STEXT {
if d.ctxt.Debugvlog > 1 {
d.ctxt.Logf("marktext %s\n", s.Name)
}
if s.FuncInfo != nil {
for _, a := range s.FuncInfo.Autom {
d.mark(a.Gotype, s)
}
}
}
if strings.HasPrefix(s.Name, "type.") && s.Name[5] != '.' {
if len(s.P) == 0 {
// Probably a bug. The undefined symbol check
// later will give a better error than deadcode.
continue
}
if decodetypeKind(d.ctxt.Arch, s)&kindMask == kindInterface {
for _, sig := range decodeIfaceMethods(d.ctxt.Arch, s) {
if d.ctxt.Debugvlog > 1 {
d.ctxt.Logf("reached iface method: %s\n", sig)
}
d.ifaceMethod[sig] = true
}
}
}
mpos := 0 // 0-3, the R_METHODOFF relocs of runtime.uncommontype
var methods []methodref
for i := range s.R {
r := &s.R[i]
if r.Sym == nil {
continue
}
if r.Type == objabi.R_WEAKADDROFF {
// An R_WEAKADDROFF relocation is not reason
// enough to mark the pointed-to symbol as
// reachable.
continue
}
if r.Type != objabi.R_METHODOFF {
d.mark(r.Sym, s)
continue
}
// Collect rtype pointers to methods for
// later processing in deadcode.
if mpos == 0 {
m := methodref{src: s}
m.r[0] = r
methods = append(methods, m)
} else {
methods[len(methods)-1].r[mpos] = r
}
mpos++
if mpos == len(methodref{}.r) {
mpos = 0
}
}
if len(methods) > 0 {
// Decode runtime type information for type methods
// to help work out which methods can be called
// dynamically via interfaces.
methodsigs := decodetypeMethods(d.ctxt.Arch, s)
if len(methods) != len(methodsigs) {
panic(fmt.Sprintf("%q has %d method relocations for %d methods", s.Name, len(methods), len(methodsigs)))
}
for i, m := range methodsigs {
name := string(m)
name = name[:strings.Index(name, "(")]
if !strings.HasSuffix(methods[i].ifn().Name, name) {
panic(fmt.Sprintf("%q relocation for %q does not match method %q", s.Name, methods[i].ifn().Name, name))
}
methods[i].m = m
}
d.markableMethods = append(d.markableMethods, methods...)
}
if s.FuncInfo != nil {
for i := range s.FuncInfo.Funcdata {
d.mark(s.FuncInfo.Funcdata[i], s)
}
}
d.mark(s.Gotype, s)
d.mark(s.Sub, s)
d.mark(s.Outer, s)
}
}