...
Run Format

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

Documentation: cmd/link/internal/ld

     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", 0)
    64  	methSym := ctxt.Syms.ROLookup("reflect.Value.Method", 0)
    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.Arch.Family == sys.ARM {
   213  		// mark some functions that are only referenced after linker code editing
   214  		names = append(names, "runtime.read_tls_fallback")
   215  	}
   216  
   217  	if d.ctxt.BuildMode == BuildModeShared {
   218  		// Mark all symbols defined in this library as reachable when
   219  		// building a shared library.
   220  		for _, s := range d.ctxt.Syms.Allsym {
   221  			if s.Type != 0 && s.Type != sym.SDYNIMPORT {
   222  				d.mark(s, nil)
   223  			}
   224  		}
   225  	} else {
   226  		// In a normal binary, start at main.main and the init
   227  		// functions and mark what is reachable from there.
   228  
   229  		if d.ctxt.linkShared && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
   230  			names = append(names, "main.main", "main.init")
   231  		} else {
   232  			// The external linker refers main symbol directly.
   233  			if d.ctxt.LinkMode == LinkExternal && (d.ctxt.BuildMode == BuildModeExe || d.ctxt.BuildMode == BuildModePIE) {
   234  				if d.ctxt.HeadType == objabi.Hwindows && d.ctxt.Arch.Family == sys.I386 {
   235  					*flagEntrySymbol = "_main"
   236  				} else {
   237  					*flagEntrySymbol = "main"
   238  				}
   239  			}
   240  			names = append(names, *flagEntrySymbol)
   241  			if d.ctxt.BuildMode == BuildModePlugin {
   242  				names = append(names, objabi.PathToPrefix(*flagPluginPath)+".init", objabi.PathToPrefix(*flagPluginPath)+".main", "go.plugin.tabs")
   243  
   244  				// We don't keep the go.plugin.exports symbol,
   245  				// but we do keep the symbols it refers to.
   246  				exports := d.ctxt.Syms.ROLookup("go.plugin.exports", 0)
   247  				if exports != nil {
   248  					for _, r := range exports.R {
   249  						d.mark(r.Sym, nil)
   250  					}
   251  				}
   252  			}
   253  		}
   254  		for _, s := range dynexp {
   255  			d.mark(s, nil)
   256  		}
   257  	}
   258  
   259  	for _, name := range names {
   260  		d.mark(d.ctxt.Syms.ROLookup(name, 0), nil)
   261  	}
   262  }
   263  
   264  // flood fills symbols reachable from the markQueue symbols.
   265  // As it goes, it collects methodref and interface method declarations.
   266  func (d *deadcodepass) flood() {
   267  	for len(d.markQueue) > 0 {
   268  		s := d.markQueue[0]
   269  		d.markQueue = d.markQueue[1:]
   270  		if s.Type == sym.STEXT {
   271  			if d.ctxt.Debugvlog > 1 {
   272  				d.ctxt.Logf("marktext %s\n", s.Name)
   273  			}
   274  			if s.FuncInfo != nil {
   275  				for _, a := range s.FuncInfo.Autom {
   276  					d.mark(a.Gotype, s)
   277  				}
   278  			}
   279  
   280  		}
   281  
   282  		if strings.HasPrefix(s.Name, "type.") && s.Name[5] != '.' {
   283  			if len(s.P) == 0 {
   284  				// Probably a bug. The undefined symbol check
   285  				// later will give a better error than deadcode.
   286  				continue
   287  			}
   288  			if decodetypeKind(d.ctxt.Arch, s)&kindMask == kindInterface {
   289  				for _, sig := range decodeIfaceMethods(d.ctxt.Arch, s) {
   290  					if d.ctxt.Debugvlog > 1 {
   291  						d.ctxt.Logf("reached iface method: %s\n", sig)
   292  					}
   293  					d.ifaceMethod[sig] = true
   294  				}
   295  			}
   296  		}
   297  
   298  		mpos := 0 // 0-3, the R_METHODOFF relocs of runtime.uncommontype
   299  		var methods []methodref
   300  		for i := range s.R {
   301  			r := &s.R[i]
   302  			if r.Sym == nil {
   303  				continue
   304  			}
   305  			if r.Type == objabi.R_WEAKADDROFF {
   306  				// An R_WEAKADDROFF relocation is not reason
   307  				// enough to mark the pointed-to symbol as
   308  				// reachable.
   309  				continue
   310  			}
   311  			if r.Type != objabi.R_METHODOFF {
   312  				d.mark(r.Sym, s)
   313  				continue
   314  			}
   315  			// Collect rtype pointers to methods for
   316  			// later processing in deadcode.
   317  			if mpos == 0 {
   318  				m := methodref{src: s}
   319  				m.r[0] = r
   320  				methods = append(methods, m)
   321  			} else {
   322  				methods[len(methods)-1].r[mpos] = r
   323  			}
   324  			mpos++
   325  			if mpos == len(methodref{}.r) {
   326  				mpos = 0
   327  			}
   328  		}
   329  		if len(methods) > 0 {
   330  			// Decode runtime type information for type methods
   331  			// to help work out which methods can be called
   332  			// dynamically via interfaces.
   333  			methodsigs := decodetypeMethods(d.ctxt.Arch, s)
   334  			if len(methods) != len(methodsigs) {
   335  				panic(fmt.Sprintf("%q has %d method relocations for %d methods", s.Name, len(methods), len(methodsigs)))
   336  			}
   337  			for i, m := range methodsigs {
   338  				name := string(m)
   339  				name = name[:strings.Index(name, "(")]
   340  				if !strings.HasSuffix(methods[i].ifn().Name, name) {
   341  					panic(fmt.Sprintf("%q relocation for %q does not match method %q", s.Name, methods[i].ifn().Name, name))
   342  				}
   343  				methods[i].m = m
   344  			}
   345  			d.markableMethods = append(d.markableMethods, methods...)
   346  		}
   347  
   348  		if s.FuncInfo != nil {
   349  			for i := range s.FuncInfo.Funcdata {
   350  				d.mark(s.FuncInfo.Funcdata[i], s)
   351  			}
   352  		}
   353  		d.mark(s.Gotype, s)
   354  		d.mark(s.Sub, s)
   355  		d.mark(s.Outer, s)
   356  	}
   357  }
   358  

View as plain text