<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, May 23, 2018 at 8:15 AM, James Y Knight <span dir="ltr"><<a href="mailto:jyknight@google.com" target="_blank">jyknight@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span class="m_-8752634773912160582m_-5239039830073959161gmail-"><div dir="ltr">On Tue, May 22, 2018 at 6:06 PM Peter Collingbourne via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi all,</div><div><br></div>Context: ld.gold has an --icf=safe flag which is intended to apply ICF only to sections which can be safely merged according to the guarantees provided by the language. It works using a set of heuristics (symbol name matching and relocation scanning). That's not only imprecise but it only works with certain languages and is slow due to the need to demangle symbols and scan relocations. It's also redundant with the (local_)unnamed_addr analysis already performed by LLVM.<div><br></div><div>I implemented an alternative to this approach in clang and lld. It works by adding a section to each object file containing the indexes of the symbols which are address-significant (i.e. not (local_)unnamed_addr in IR).<br><div><br></div><div>I used this implementation to link clang with release+asserts with each of --icf={none,safe,all}. The binary sizes were:</div><div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">none: 109407184</div></div><div><div>safe: 108534736 (-0.8%)<br></div></div><div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">all: 107281360 (-2%)<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div></div><div>I measured the object file overhead of these sections in my clang build at 0.08%. That's almost nothing, and I think it's small enough that we can turn it on by default.</div><div><br></div><div>I've uploaded a patch series for this feature here: <a href="https://github.com/pcc/llvm-project/tree/llvm-addrsig" target="_blank">https://github.com/pcc/l<wbr>lvm-project/tree/llvm-addrsig</a></div><div>I intend to start sending it for review soon.</div></div></div></blockquote><div><br></div></span><div>This sounds like a nice idea, but it'd be great to put in some effort to see if we can get this done in a cross-toolchain collaborative manner, instead of llvm-specific. The need is clearly generic, after all.</div><div><br></div></div></div></blockquote><div><br></div><div>Peter Smith has suggested making a proposal to generic-abi and that certainly seems reasonable, but there seems to be a practical problem there: the generic-abi is unmaintained and there doesn't seem to be an authority responsible for assigning section numbers (see the recent SHT_RELR thread for example). Since this proposal requires a new section number I would suggest that we make the proposal to generic-abi, incorporate any design feedback from there and proceed with a section number in the LLVM namespace until the generic-abi gets a maintainer, at which point we can change lld to accept both section numbers or maybe just the generic one (since reading the section is optional).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div></div><div><div style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">I'm a bit worried of the scheme of emitting symbol indexes into a section. AFAIK there is nothing else in ELF which puts symbol indexes in data at the moment (only in relocations and section headers). In particular, if <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">anyone were to use a tool which rewrites the symbol table, it'll break things, unless that tool knows about this special section.</span></div></div></div></div></blockquote><div><br></div><div>The design accounts for this :)</div><div><br></div><div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">To begin with, in practice I don't think we can get this right for every conceivable tool, because the tool could put something in the object file that would invalidate the metadata by making a symbol address-significant. For example, I can use ld -r to combine a metadata-containing object file defining a function foo with a non-metadata-containing object file defining a function bar that returns the address of foo, which would invalidate the metadata for foo. So I think the best that we can hope for is to arrange for most tools to "naturally" invalidate the metadata.</div><br></div><div>There turns out to be a way to do this: most tools will reset the sh_link field of an unrecognized section to zero if that sh_link field points to the .symtab section. GNU objcopy, ld.bfd -r, ld.gold -r and ld.lld -r all do this. (It looks like llvm-objcopy will preserve the sh_link, but we can fix that.) So what we can do is make the sh_link in our section point to .symtab and use sh_link=0 as a signal that a tool has operated on the object file, and therefore ignore the section. This resetting of sh_link for unrecognized sections doesn't appear to be required by the generic-abi, so this is probably something that we'd want to bring up there in addition to the section itself. Also, this should hopefully become a non-problem once this proposal makes its way into either the generic ABI or GNU-gABI and tools learn about the section.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><br></div><div>I wonder if it's possible to put the data in the symbol table. Unfortunately, there's not a whole lot of available space there...</div><div><br></div><div>The "st_other" field has some space available -- only the bottom 2 bits are currently used in general for visibility, so one could imagine adding a flag at 0x04, perhaps, for this indicator. Unfortunately, the bits of this field are widely used by a variety of architecture-specific things, which makes that rather more complicated. MIPS uses almost all the remaining bits in that field, but seemingly not bit 3. PowerPC uses bits 5-8 for the local-call optimization, leaving bits 3-4. Alpha uses bits 4 and 8 for what I think may be a similar optimization. IA64 OpenVMS uses bits 5-8 for additional function-type and linkage annotations. m68k uses bits 7-8 for identifying "far" functions and interrupt handlers.</div><br class="m_-8752634773912160582m_-5239039830073959161gmail-m_-2216932256482161235gmail-Apple-interchange-newline"><div>So...that might be viable -- just barely --  but even after suggesting that, I'd not really want to argue for it. =)</div><div><br></div></div></div>
</blockquote></div><div class="gmail_extra"><br></div>I thought about using st_other for this, but I came to the same conclusion that it would probably be too hard to stake out a bit with the architecture-specific things going on there. From the looks of things it looks like MIPS is (somewhat gratuitously in the case of STO_MIPS_MIPS16) using all of the "unused" bits: <a href="http://llvm-cs.pcc.me.uk/include/llvm/BinaryFormat/ELF.h#554" target="_blank">http://llvm-cs.pcc.me.uk<wbr>/include/llvm/BinaryFormat/ELF<wbr>.h#554</a></div><div class="gmail_extra">So if we did something with st_other we'd probably need to exclude MIPS and maybe other architectures and get tools to do the right thing (which seems harder than with the sh_link trick).</div><div class="gmail_extra"><br clear="all"><div>Thanks,</div>-- <br><div class="m_-8752634773912160582m_-5239039830073959161gmail_signature"><div dir="ltr">-- <div>Peter</div></div></div>
</div></div>