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