...
Run Format

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

Documentation: cmd/link/internal/ld

  // 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"
  	"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 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(AttrReachable, len(s.R) == 1 && s.R[0].Sym.Attr.Reachable())
  			}
  		}
  	}
  
  	// Remove dead text but keep file information (z symbols).
  	textp := make([]*Symbol, 0, len(ctxt.Textp))
  	for _, s := range ctxt.Textp {
  		if s.Attr.Reachable() {
  			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 *Symbol   // receiver type symbol
  	r   [3]*Reloc // R_METHODOFF relocations to fields of runtime.method
  }
  
  func (m methodref) ifn() *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       []*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 *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 *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 |= AttrReachable
  	s.Reachparent = 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 SysArch.Family == sys.ARM {
  		// mark some functions that are only referenced after linker code editing
  		names = append(names, "runtime.read_tls_fallback")
  	}
  
  	if 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 != 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.
  		names = append(names, *flagEntrySymbol)
  		if *FlagLinkshared && (Buildmode == BuildmodeExe || Buildmode == BuildmodePIE) {
  			names = append(names, "main.main", "main.init")
  		} else if Buildmode == BuildmodePlugin {
  			names = append(names, *flagPluginPath+".init", *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 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 == 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(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 := 0; i < len(s.R); i++ {
  			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)
  	}
  }
  

View as plain text