<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 21, 2016 at 9:39 AM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</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="">On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.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 style="word-wrap:break-word"><br><div><span><blockquote type="cite"><div>On Jul 21, 2016, at 7:45 AM, Philip Reames <<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>> wrote:</div><br><div>
<div text="#000000" bgcolor="#FFFFFF">
Joining in very late, but the tangent here has been interesting (if
rather OT for the original thread).<br>
<br>
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>
<br>
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>
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>
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></div></div></blockquote><div><br></div></span><div>This analysis can be lazy/incremental. Most passes only do “safe” speculation and code sinking without side effects.</div></div></div></blockquote><div><br></div></span><div>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><br></div><div>Here's the list definitely needing it right now:</div><div>GVN<br></div><div>GVNHoist</div><div>LICM</div><div>LoadCombine</div><div>LoopReroll</div><div>LoopUnswitch<br></div><div>LoopVersioningLICM</div><div>MemCpyOptimizer</div><div>MergedLoadStoreMotion</div><div>Sink</div><div><br></div><div>The list is almost certainly larger than this, this was a pretty trivial grep and examination.</div><div>(and doesn't take into account bugs, etc)</div><div><br></div></div></div></div></blockquote><div><br></div><div><br></div><div>(Note, this list is stuff in the Scalar directory only. Everything in Vectorize would n eed it, etc)<br><br></div><div>And in case folks want more evidence that reasonable llvm developers need something that just gives easy and right answers, see <a href="https://reviews.llvm.org/D22547" rel="noreferrer" target="_blank" style="font-size:12.8px">https://reviews.llvm.org/D22547</a> from just yesterday :)</div><div><br></div><div>To move this along, i will go build the analysis (I already have it mostly done, actually). If someone updates our docs to make this stuff clear and obvious, that would be wonderful :)</div><div><br></div><div>The analysis currently computes, internally, for a given BB:<br><br></div><div>EarliestLoadHoistBarrier (used to see if you can move something out of a block)</div><div>LatestLoadHoistBarrier (used to find the latest safe insertion point in a block, if any)</div><div>EarliestStoreSinkBarrier (insertion)</div><div>LatestStoreSinkBarrier (movement)</div><div><br></div><div><br></div><div>(stores are maythrow dependent, loads are isGuaranteedToTransferExecutionToSuccessor dependent)</div><div><br></div><div>I'm still coming up with the external API, the users all want to know either:<br><br></div><div>1. Can i move a load up out of this block to a direct predecessor</div><div>2. Can i move a store down out of this block to a direct successor</div><div><br></div><div>GVN's current load PRE is complex to get "right" from it's current standpoint, the APi that will provide the easiest way to fix it will be:<br><br></div><div>3. What is the latest insertion point in a block for a load, if it is safe (IE the block does not end in an instruction you cannot move the load before).</div><div><br></div><div>Nothing is doing global store sinking right now that i see, so nothing needs the analogous store api.</div><div><br></div></div></div></div>