<div dir="ltr">Sorry for the late response, a few questions/comments below. Teresa<br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, May 1, 2017 at 12:45 PM, Peter Collingbourne <span dir="ltr"><<a href="mailto:peter@pcc.me.uk" target="_blank">peter@pcc.me.uk</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_extra"><div class="gmail_quote"><span class="gmail-">On Mon, May 1, 2017 at 11:06 AM, Mehdi AMINI <span dir="ltr"><<a href="mailto:joker.eph@gmail.com" target="_blank">joker.eph@gmail.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"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-">2017-04-25 12:11 GMT-07:00 Peter Collingbourne <span dir="ltr"><<a href="mailto:peter@pcc.me.uk" target="_blank">peter@pcc.me.uk</a>></span>:<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">Hi all,<div><br></div><div>I've been making a number of changes to the summary representation recently, and I wanted to lay out some of my plans so that folks are aware of my ultimate direction with this.</div><div><br></div><div>Basically I want to move the summary into the irsymtab that we will be storing to disk after D32061 lands. This would help solve a number of problems:</div><div><div>- To read a summary, you need to read all summaries in a module. For example, if a client only wants to read summaries for prevailing symbols, it still needs to read summaries for all symbols. We should be able to design an API that lets clients avoid reading summaries for known non-prevailing symbols.</div></div></div></blockquote><div><br></div></span><div>Why should we? Efficiency? </div></div></div></div></blockquote><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_extra"><div class="gmail_quote"><div>Where in the process would we benefit from that?</div></div></div></div></blockquote><div><br></div></span><div>Efficiency, better dead code stripping (can more easily strip dependencies of non-prevailing symbols) and it would also help us address the correctness problem where we re-implement the linker's prevailing definition logic in the summary and sometimes get it wrong (for non-MachO at least).</div></div></div></div></blockquote><div><br></div><div>Are we getting this wrong in places now with the new LTO API? I.e. we set up the PrevailingModuleForGUID map using linker info, which feeds into weak resolution. </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_extra"><div class="gmail_quote"><div><br></div><div>I also want to try to simplify the summary so that each index entry can only map onto a single definition (by changing the key type from GUID to symbol name), but that's a separate discussion.</div><span class="gmail-"><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_extra"><div class="gmail_quote"><div>Right now we may still cross-module import and inline a non-prevailing symbols, if the prevailing symbol isn't IR defined.</div></div></div></div></blockquote><div><br></div></span><div>We can handle this in the same way as we do for regular LTO: we can add non-prevailing ODR definitions to the index, and change their linkage to available_externally, and if we later see a prevailing definition, we can replace the non-prevailing definition with it.</div><span class="gmail-"><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_extra"><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-"><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><div>- Regular LTO modules do not have summaries. This means that dead stripping is less effective if the module contains both regular and thin LTO modules. (Although this is a somewhat orthogonal problem, since I am making a format change, I'd like to take care of it as part of the same change.)</div></div></div></blockquote><div><br></div></span><div>How do you want do deal with that?</div><div>Do you mind giving a quick example (LTO defines foo, used from bar in a ThinLTO module, but bar is dead).</div></div></div></div></blockquote><div><br></div></span><div>Sure. In your example, we would create summaries (and store them in the bitcode files) that look like this:</div><div>ThinLTO: foo -> {bar}</div><div>FullLTO: bar -> {}</div></div></div></div></blockquote><div><br></div><div>It doesn't look like this maps to the description Mehdi gave, but rather the following (correct me if I'm wrong):</div><div>  LTO defines bar, which is used from foo in a ThinLTO module, but foo is dead (and therefore bar is dead)</div><div> </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_extra"><div class="gmail_quote"><div><br></div><div>The FullLTO summaries would have a flag set to prevent importing (at least to start with).</div><div><br></div><div>At LTO time those summaries would be loaded into a single summary index and we would run computeDeadSymbols over the index. In this case, bar would be added to the set of dead symbols because it is not reachable from a GC root.</div></div></div></div></blockquote><div> </div><div>I assume foo is therefore also dead as I described above</div><div> </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_extra"><div class="gmail_quote"><div>We would move the code that handles loading regular LTO modules to LTO::runRegularLTO. In that function we would check whether bar is dead. Because it is, we would not add it to the list passed to IRMover.</div><span class="gmail-"><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_extra"><div class="gmail_quote"><div>Also I assume code size isn't an issue since -ffunction-sections always allow to dead-strip post-LTO (even though we're losing compile time efficiency and potentially a few optimisations).</div></div></div></div></blockquote><div><br></div></span><div>It is an issue for CFI, because the CFI pass works by merging several vtable globals into a small number of larger globals, which would prevent post-LTO stripping of the unused vtables and virtual functions. Early dead code stripping would allow the unused vtable globals to be stripped before they are merged.</div><span class="gmail-"><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_extra"><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-"><div> </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><div><br></div><div>Basically, the summaries would be stored in an auxiliary structure like storage::Uncommon with a flag in the storage::Symbol indicating whether a given symbol has a summary.</div><div><br></div><div>Currently we use the presence of a summary to indicate whether to compile a module with regular or thin LTO. This will need to change if we want to store summaries for regular LTO modules. To that end, I want to add a record to all bitcode modules to be compiled with thin LTO that marks them as such. This will be used in place of the presence of the summary. For backwards compatibility, the presence of a summary in bitcode format will be used to mark modules as needing to be compiled with thin LTO.</div><div><br></div><div>Because the contents of the summaries, unlike the irsymtab, for the most part do not need to be accurate for correctness, </div></div></div></blockquote><div><br></div></span><div>I'm not sure what you mean about accuracy and correctness. The "for the most part" part especially is raising the question that if there is a part that needs to be accurate for correctness, that's enough to requires accuracy for the summary period.</div></div></div></div></blockquote><div><br></div></span><div>What I was trying to express was that a global's summary must, for correctness, contain a superset of the accurate information for the global. In that sense, the summary that I mention below, which contains a reference edge from each defined symbol to every other symbol in the symbol table, would lead to correct behaviour. When the module is loaded, it will contain fewer symbol references than what is indicated by the summary, but that can be seen as an "optimisation" performed by the bitcode reader.</div><div><br></div><div>For example, suppose that we have this module:</div><div><br></div><div>void g();</div><div>void h();</div><div>void f() {</div><div>  g();</div><div>}</div><div><br></div><div>An equivalent implementation of f would be:</div><div><br></div><div>void f() {</div><div>  void (*p)() = g;</div><div>  p();</div><div>  if (0)</div><div>    h();</div><div>}</div><div><br></div><div>and an accurate summary for f would contain ref edges from f to both g and h. When the first module is read, its definition of f will contain a call edge from f to g and no edge from f to h, but conceptually that can be seen as similar to dead code elimination and constant propagation being applied to the second module's f when it is read.</div><span class="gmail-"><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_extra"><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-"><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><div>I think we don't need as strict rules as we do for the rest of the irsymtab. I.e. we don't need to rebuild the summary entirely if the LLVM revision changes, as I am doing for the irsymtab in D32061. However, the summary must have a correct set of reference edges in order to implement dead stripping.</div></div></div></blockquote><div><br></div></span><div>Note that in the Apple ecosystem, we claim backward compatibility and want ThinLTO static archive built with 4.0 to work seamlessly with 5.0, 6.0, etc. </div></div></div></div></blockquote><div><br></div></span><div>Sure, the design expressly allows for that. The result will not necessarily be optimal, but it will work.</div></div></div></div></blockquote><div><br></div><div>I think this just pessimizes dead stripping, which seems like a reasonable tradeoff. Mehdi?</div><div> </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_extra"><div class="gmail_quote"><span class="gmail-"><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_extra"><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-"><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><div>So the solution I have in mind is to pessimise dead stripping *for that module* if the LLVM revision is out of date. I.e. the upgraded summary would contain a reference edge from every defined symbol to every other symbol in the module. Because we had already regenerated the irsymtab as a result of the revision change, we will have an accurate symbol table for the module, so this seems sound to me. </div></div></div></blockquote><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><div><br></div><div>All other parts of the summary would be preserved, as long as the summary format does not change. This means that the function size and hotness for example would be copied from the existing summary. To make this work, I would add a format version number field to the irsymtab header as part of D32061, and copy the remaining information from the existing summary as long as the version number is the same.</div></div></div></blockquote></span></div></div></div></blockquote></span></div></div></div></blockquote><div><br></div><div>Would this supercede the FS_VERSION record currently written in the global value summary bitcode sections?</div><div><br></div><div>I like the overall idea of combining the summary with the irsymtab. Ideally, as mentioned in the review thread for D32061, it would be great if this information is ultimately deduplicated between the bitcode IR and the irsymtab (e.g. the linkage types etc), but I understand that is a longer term goal.</div><div><br></div><div>My main concern, as noted when we last discussed this, is that the irsymtab is currently encoded in something other than bitcode, and this would move the summary from bitcode record format into this custom format embedded in a blob. I am hoping Mehdi or others will comment on that aspect, as I originally implemented the summary in bitcode format based on the responses to the original ThinLTO RFC. I know that there is some community interest in moving to a more efficient encoding than the current bitcode format, and maybe the irsymtab is a good way to experiment with what that should be, but I am a little concerned about re-implementing the summary in something new before we have community agreement on what that new format should be.<br></div><div><br></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_extra"><div class="gmail_quote"><span class="gmail-"><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_extra"><div class="gmail_quote"><span class="gmail-m_-2596204814464327281m_-4761717065908820891gmail-"><div><br></div></span><div>The last two paragraphs aren't totally clear to me (on the why it is needed and what is the practical impact).</div></div></div></div></blockquote><div><br></div></span><div>I hope the above clarifies things.</div><div><br></div><div>Thanks,</div></div><span class="gmail-HOEnZb"><font color="#888888">-- <br><div class="gmail-m_-2596204814464327281m_-4761717065908820891gmail_signature"><div dir="ltr">-- <div>Peter</div></div></div>
</font></span></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><span style="font-family:times;font-size:medium"><table cellspacing="0" cellpadding="0"><tbody><tr style="color:rgb(85,85,85);font-family:sans-serif;font-size:small"><td nowrap style="border-top:2px solid rgb(213,15,37)">Teresa Johnson |</td><td nowrap style="border-top:2px solid rgb(51,105,232)"> Software Engineer |</td><td nowrap style="border-top:2px solid rgb(0,153,57)"> <a href="mailto:tejohnson@google.com" target="_blank">tejohnson@google.com</a> |</td><td nowrap style="border-top:2px solid rgb(238,178,17)"> 408-460-2413</td></tr></tbody></table></span></div>
</div></div>