<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 21, 2016 at 4:25 PM, 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
It sounds like this new analysis could basically subsume the
existing OrderedBasicBlock. <br>
<br>
Thinking about update semantics, what types of updates need to be
recorded to make this efficient?<br>
- Adding maythrow instructions is obvious required, figuring out how
to update clearly requires OBB info. <br></div></blockquote><div><br></div><div>Yup.</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 text="#000000" bgcolor="#FFFFFF">
- Adding arithmetic instructions - only requires OBB update<br></div></blockquote><div><br></div><div>This is possible to do by skip numbering and using uint64.</div><div><br></div><div>If a given pass performs only insertafter calls, you can show that you can add tons of instructions with O(1) updates by skip-numbering</div><div>Same with only insertbefore.</div><div>You can use the same numbering scheme for both, and just add/subtract 1 in the right places until you run out of space. With int64 as the numbers, it's "a lot of places" :)</div><div><br></div><div>If you allow interspersing of insertbefore/insertafter, the numbering scheme is more complex, and you can only insert max of log(n) instructions between two instructions before you must renumber.</div><div><br></div><div>(this is just using previous inst number+next inst number/2 as the new number)</div><div> </div><div><br></div><div>Whether any of this is worth it, ¯\_(ツ)_/¯</div><div><br></div><div>I'll probably start without it and we can do it if it's too slow.</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 text="#000000" bgcolor="#FFFFFF">
<br>
I'm thinking that some form of lazy update might be the best path
forward here. Have the results re-calculated via a linear scan of
the block only once a) a change has happened and been marked and b)
the request information is required. This would allow batch updates
for instance. We could potentially try to incremental update the
motion barriers, but that seems like potentially too much work.<br></div></blockquote><div>Yup.</div><div><br></div><div> </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 text="#000000" bgcolor="#FFFFFF">
<br>
Also, I'm now thinking that first and last isn't enough
information. Once I ask the speculation question, I think need to
ask what the *next* ordering barrier is. I thinking code of the
following variety:<br>
for block I want to skip:<br>
if not has ordering barrier:<br>
continue<br>
if can speculate over block<br>
continue<br>
barrier = last barrier in block<br>
while can speculate over barrier:<br>
barrier = previous barrier<br>
return next(barrier) as insert pt<br>
return first instruction in function entry</div></blockquote><div><br></div><div><br></div><div>So, so far nothing tries to do that.</div><div><br></div><div>It's easy enough to do though, we can just maintain unordered maps of inst, number, and ordered maps of number, inst (assuming we allow for incremental update) per block.</div><div><br></div><div>Or at least, this is the "simple" way. You can do it in a better time query time bound by unordered maps of inst, {number, next/last inst} (IE you give us the current thing we gave you, we tell you the next or last thing from it).</div><div>This is not sane to incrementally update though.</div><div><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 text="#000000" bgcolor="#FFFFFF"><div><div class="h5"><br>
<br>
<div>On 07/21/2016 12:17 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote type="cite">
<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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div>
<div> <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"></a><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"></a><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"></a><a href="https://reviews.llvm.org/D22547" 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><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>
</blockquote>
<br>
</div></div></div>
</blockquote></div><br></div></div>