<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 21, 2016, at 9:39 AM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" class="">dberlin@dberlin.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick <span dir="ltr" class=""><<a href="mailto:atrick@apple.com" target="_blank" class="">atrick@apple.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><span class=""><blockquote type="cite" class=""><div class="">On Jul 21, 2016, at 7:45 AM, Philip Reames <<a href="mailto:listmail@philipreames.com" target="_blank" class="">listmail@philipreames.com</a>> wrote:</div><br class=""><div class="">
<div text="#000000" bgcolor="#FFFFFF" class="">
Joining in very late, but the tangent here has been interesting (if
rather OT for the original thread).<br class="">
<br class="">
I agree with Danny that we might want to take a close look at how we
model things like maythrow calls, no return, and other implicit
control flow. I'm not convinced that moving to a pure explicit
model is the right idea because we get a lot of gain in practice
from being able to reason about what are essentially a limited form
of extended basic blocks. I would welcome a design discussion about
this, preferably in person, but also don't want to block any current
(or future honestly) work on this until we have a reasonable firm
plan of action. <br class="">
<br class="">
One idea would be to explicitly acknowledge that our "basic blocks"
are actually "extended basic blocks" with internal exits due to
exception propagation, noreturn, and (recently) guards. I could see
a couple of implementation strategies here:<br class="">
1) Extend BasicBlock to explicitly track potential early exiting
instructions. This would probably have to be conservative so that
things like nothrow inference aren't required to update all callers
in one go.<br class="">
2) Conservative assume that BasicBlock has an unknown number of
early exiting instructions and write an analysis pass which answers
questions about where those early exits are. Any pass which does
code motion would require this analysis. (This is essentially the
principled version of our current hacks.)<br class=""></div></div></blockquote><div class=""><br class=""></div></span><div class="">This analysis can be lazy/incremental. Most passes only do “safe” speculation and code sinking without side effects.</div></div></div></blockquote><div class=""><br class=""></div><div class="">While I agree it can be lazy, and should be an analysis, i'm, again, really not sure which passes you are thinking about here that do code sinking/speculation that won't need it.</div><div class=""><br class=""></div><div class="">Here's the list definitely needing it right now:</div><div class="">GVN<br class=""></div><div class="">GVNHoist</div><div class="">LICM</div><div class="">LoadCombine</div><div class="">LoopReroll</div><div class="">LoopUnswitch<br class=""></div><div class="">LoopVersioningLICM</div><div class="">MemCpyOptimizer</div><div class="">MergedLoadStoreMotion</div><div class="">Sink</div><div class=""><br class=""></div><div class="">The list is almost certainly larger than this, this was a pretty trivial grep and examination.</div><div class="">(and doesn't take into account bugs, etc)</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">It would be nice to know which passes, specifically, you are thinking of when you say "most" :)</div></div></div></div></div></blockquote><div><br class=""></div><div>I don’t have a point to argue, just clarifying Philip's language. But if you want to know what I was thinking it’s that there are a couple of passes doing deliberate code motion: GVN and LICM (I didn’t think of the others) and a bunch of passes doing incidental code motion like InstCombine, CodeGenPrepare, a handful of passes calling SCEVExpander, etc.</div><div><br class=""></div><div>I should have said “most passes at most do safe speculation…” so you don’t ask me to grep through the code looking for incidental code motion :)</div><div><br class=""></div><div>-Andy</div><div><br class=""></div><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class="">They don’t need to run the analysis.</div></div></div></blockquote><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class=""><br class=""></div>Thanks Philip. I forgot to mention that LLVM passes historically have taken advantage of implicit extended basic blocks (ISel) and were never improved to handle general EBBs. It took years for loop opts to finally handle early exits well.</div><div class="">-Andy</div><span class=""><div class=""><br class=""></div></span></div></blockquote></div></div></div>
</blockquote></div><br class=""></body></html>