<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2017-04-04 19:15 GMT+02:00 Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</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"><div class="gmail_quote"><div><div class="gmail-h5"><div dir="ltr">On Mon, Apr 3, 2017 at 2:01 PM Piotr Padlewski <<a href="mailto:piotr.padlewski@gmail.com" target="_blank">piotr.padlewski@gmail.com</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" class="gmail-m_-3063311781355450007gmail_msg"><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><div class="gmail_quote gmail-m_-3063311781355450007gmail_msg">2017-04-01 15:59 GMT+02:00 Piotr Padlewski <span dir="ltr" class="gmail-m_-3063311781355450007gmail_msg"><<a href="mailto:piotr.padlewski@gmail.com" class="gmail-m_-3063311781355450007gmail_msg" target="_blank">piotr.padlewski@gmail.com</a>></span>:<br class="gmail-m_-3063311781355450007gmail_msg"><blockquote class="gmail_quote gmail-m_-3063311781355450007gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class="gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><div class="gmail-m_-3063311781355450007gmail_msg"><div class="gmail-m_-3063311781355450007m_-5981021597662213057h5 gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"><div class="gmail_quote gmail-m_-3063311781355450007gmail_msg">2017-03-31 23:20 GMT+02:00 Sanjoy Das <span dir="ltr" class="gmail-m_-3063311781355450007gmail_msg"><<a href="mailto:sanjoy@playingwithpointers.com" class="gmail-m_-3063311781355450007gmail_msg" target="_blank">sanjoy@playingwithpointers.<wbr>com</a>></span>:<br class="gmail-m_-3063311781355450007gmail_msg"><blockquote class="gmail_quote gmail-m_-3063311781355450007gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Piotr,<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
On March 31, 2017 at 1:07:12 PM, Piotr Padlewski<br class="gmail-m_-3063311781355450007gmail_msg">
(<a href="mailto:piotr.padlewski@gmail.com" class="gmail-m_-3063311781355450007gmail_msg" target="_blank">piotr.padlewski@gmail.com</a>) wrote:<br class="gmail-m_-3063311781355450007gmail_msg">
> [snip]<br class="gmail-m_-3063311781355450007gmail_msg">
<span class="gmail-m_-3063311781355450007m_-5981021597662213057m_-1472521890028536057gmail- gmail-m_-3063311781355450007gmail_msg">> Do I understand it correctly, that it is legal to do the hoist because all<br class="gmail-m_-3063311781355450007gmail_msg">
> of the instructions above %vtable does not throw?<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
</span>Yes, I think you're right.  HeaderMayThrow is a conservative<br class="gmail-m_-3063311781355450007gmail_msg">
approximation, and the conservativeness is biting us here.<br class="gmail-m_-3063311781355450007gmail_msg">
<span class="gmail-m_-3063311781355450007m_-5981021597662213057m_-1472521890028536057gmail- gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg">
> Are there any plans to fix it in the future? The fix doesn't seem hard to<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
</span>Not to my knowledge.<br class="gmail-m_-3063311781355450007gmail_msg">
<span class="gmail-m_-3063311781355450007m_-5981021597662213057m_-1472521890028536057gmail- gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg">
> write and I can do it, but I am not sure if it won't be too expensive.<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
</span>Maybe we can do it (relatively) cheaply:<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
 - Remember the first throwing instruction in the header, instead of a<br class="gmail-m_-3063311781355450007gmail_msg">
   boolean, in LoopSafetyInfo<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
 - In hoistRegion, remember if you've seen the first throwing<br class="gmail-m_-3063311781355450007gmail_msg">
   instruction yet<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
 - Pass the above as a boolean parameter to isGuaranteedToExecute, and<br class="gmail-m_-3063311781355450007gmail_msg">
   instead of<br class="gmail-m_-3063311781355450007gmail_msg">
     if (Inst.getParent() == CurLoop->getHeader())<br class="gmail-m_-3063311781355450007gmail_msg">
       return !SafetyInfo->HeaderMayThrow;<br class="gmail-m_-3063311781355450007gmail_msg">
   do something like<br class="gmail-m_-3063311781355450007gmail_msg">
     if (Inst.getParent() == CurLoop->getHeader())<br class="gmail-m_-3063311781355450007gmail_msg">
       return IsBeforeThrowingInst;<br class="gmail-m_-3063311781355450007gmail_msg">
<br class="gmail-m_-3063311781355450007gmail_msg">
-- Sanjoy<br class="gmail-m_-3063311781355450007gmail_msg">
</blockquote></div></div></div>I was thinking about something very similar and it seems to be a good approach to me because it has much lower complexity.</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">In the review Sanjoy correctly spoted that I am not discarding invariant.group metadata when hoisting, which is incorrect in general.</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">This generates a big problem to devirtualization, because discarding metadata when hoisting vtable load might be worse than not hoisting when</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">there might be another load/store with !invariant.group dominating it (e.g. after inlining).</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">I don't see any way to model it right now in LLVM, but I see a one simple solution:</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"> add extra information to the metadata nodes indicating that this property is non-local:</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">%0 = load... %p, !invariant.group !1, !dereferenceable !2</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg">%1 = load ... %0, !invariant.load !0, !dereferenceable !2</span><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg">!0 = !{!"GlobalProperty"}</span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg">!1 = !{!"MyType", !"GlobalProperty"}</span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg">!2 = !{i64 8, !"GlobalProperty}</span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><span style="font-size:12.8px" class="gmail-m_-3063311781355450007gmail_msg">With that we would strip only the metadata not containing this information.</span></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">For devirtualization it would make sense with invariant.load, invariant.group and dereferenceable.</div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg">What do you think about this idea? </div><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><br class="gmail-m_-3063311781355450007gmail_msg"></div></div></blockquote></div></div></div><div dir="ltr" class="gmail-m_-3063311781355450007gmail_msg"><div class="gmail_extra gmail-m_-3063311781355450007gmail_msg"><div class="gmail_quote gmail-m_-3063311781355450007gmail_msg"><div class="gmail-m_-3063311781355450007gmail_msg">Do you have any comments? I would like to know if the idea does even make sense, so I won't start writing prototype that will be throwed to thrash</div></div></div></div></blockquote><div><br></div></div></div><div>I don't really see why you need a separate property....</div><div><br></div><div>It seems plausible that rather than having the hoisting logic handle invariant metadata generically (by stripping it when hoisting) it could instead be aware of invariant metadata and try to avoid hoisting the load.</div><div><br></div></div></div></blockquote><div>So when we hoist based on the guarantee that it will be executed it seems to be safe to keep the metadata. LICM always discard. </div><div>So we could only hoist invariant.group loads if they are guarantee to execute.</div><div>Right now LICM will not hoist any invariant.group load, because it doesn't know it is invariant. </div><div><br></div><div>It would be still nice to hoist it when we know that it is safe to load from vptr and from vtable, but we can't do it if we will discard medata (for this</div><div>case we need dereferenceable)</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_quote"><div></div><div>But this will end up being yet another way in which enabling invariants obstructs normal optimizations to get devirtualization. I'm increasingly worried that the cost is going to outweigh the gain.</div></div></div></blockquote><div>What kind of cost you are reffering?</div><div>If we would add a way to say that specific metadata is a global property, then I don't think the cost of maitanence (understanding idea, fixing documentation</div><div>and fixing passes) would be higher than the gains, because I assume it would be very low.</div><div>It does not seem to be that complicated to understand and use,</div><div>and to implement this we would only need function like `dropAllUnknownLocalMetadata` that would replace `dropAllUnknownMedatata` in most of the</div><div>places. We could even firstly fix LICM, and then fix other passes, because the global properties would not guarantee that they would be not discarded.</div><div> </div></div></div><div class="gmail_extra">When we add medata in the frontend then in most cases (probably all, because it is not that easy to add metadata depending on the BB) it is a non local property. Because of this it seems weird that we can only model it as a local property.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Piotr</div><div class="gmail_extra"><br></div></div>