<div dir="ltr">Okay, so it sounds like it might actually be better to be even more low level, call it "ExtendedBBInfo" or something, and rename what it provides to be more clearly structural:<div><br></div><div>A. Inst * FirstI<span style="font-size:12.8px">sGuaranteedToTransferExecutio</span><span style="font-size:12.8px">nToSuccessor(BB) (naming bikeshed open on this one :P)</span></div><div><span style="font-size:12.8px">B. Inst * LastI</span><span style="font-size:12.8px">sGuaranteedToTransferExecutio</span><span style="font-size:12.8px">nToSuccessor(BB)</span></div><div>C. Inst *FirstMayThrow(BB)<br>D. Inst *LastMayThrow(BB)</div><div><br></div><div><br></div><div>Most things want to know if a given inst is before or after these.</div><div><br></div><div>Since we have to touch the entire set of instructions for a bb anyway, we could also provide dominates (like orderedbasicblock) to give you the answer to that question for free (otherwise everything has to rewalk the entire inst list again)</div><div><br></div><div>Rather than make it part of the API for this class, this would basically be making OrderedBasicBlock an interface, and this class happens to be able to provide a pointer to something satisfying that interface as well.</div><div><br></div><div>(IE getOrderedBasicBlock() on EBBInfo will return you something that has locallyDominates())</div><div><br></div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 21, 2016 at 11:59 AM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><div><div class="h5">
<br>
<br>
<div>On 07/21/2016 10:30 AM, Daniel Berlin
wrote:<br>
</div>
<blockquote type="cite">
<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>On Thu, Jul
21, 2016 at 9:26 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank"></a><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" style="font-size:12.8px" target="_blank">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>
</div>
</div>
</blockquote></div></div>
I would argue that we should have this analysis *only* report the
EBB information. Doing this in the form of the information you've
mentioned is fine, but I would not want to see this become our deref
analysis for instance. I think that needs to be a separate analysis
which is well layered on top of this one. (i.e. once I encounter a
hoist barrier, I need to then ask if a load is safe to speculate
beyond that point as a separate question.)<span class=""><br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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>
</blockquote>
<br>
</span></div>
</blockquote></div><br></div>