<div dir="ltr">Hi Danny,<div><br></div><div>Thanks for that :) However I've just updated the prototype patch to NewGVN and it didn't need any API changes - all I rely on is GVNExpression.</div><div><br></div><div>Hongbin,</div><div><br></div><div><div>I wanted to explain a little about what GVNSink can currently do, what it was designed for and hopefully how to make it handle your testcase.</div><div><br></div><div><u><b>Background</b></u></div><div><br></div><div>Common code sinking is more difficult to efficently do than one might expect. Prior to October 2016, LLVM was able to handle simple cases of this within SimplifyCFG, for example:</div><div><br></div><div><font face="monospace"> if (a) {</font></div><div><font face="monospace"> b += 42;</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> b += 42;</font></div><div><font face="monospace"> }</font></div><div><font face="monospace"> // -> b += 42</font></div><div><br></div><div>It could even sink operations where a phi was required:</div><div><br></div><div> <font face="monospace"> if (a) {</font></div><div><font face="monospace"> b += 42;</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> b += 64;</font></div><div><font face="monospace"> }</font></div><div><font face="monospace"> // -> b += phi(42, 64)</font></div><div><br></div><div>However it had a simplistic execution model and so:</div><div> 1) Restricted itself to blocks with only TWO incoming arcs</div><div> 2) Would only ever produce one PHI and then bail out</div><div><br></div><div>Generally, the factors that make the search space for a good generic sinking optimization large are:</div><div><br></div><div> 1) The number of incoming edges to a block.</div><div> 2) Non-monotonicity of heuristic - for example it might not be worthwhile sinking 2 instructions but may be worthwhile sinking 3 instructions.</div><div> 3) Permutations of otherwise similar instructions in incoming blocks.</div><div><br></div><div>I'll describe them all in a bit more detail:</div><div><br></div><div><b><u>1) The number of incoming edges to a block</u></b></div><div><br></div><div>There are many constructs that can create a block with more than two input edges. An obvious example is a switch:</div><div><br></div><div><font face="monospace"> switch (a) {</font></div><div><font face="monospace"> case 1: b += 32; break;</font></div><div><font face="monospace"> case 2: b += 43; break;</font></div><div><font face="monospace"> default: break;</font></div><div><font face="monospace"> }</font></div><div><br></div><div>Another is a chain of if-elses:</div><div><br></div><div><font face="monospace"> if (a) {</font></div><div><font face="monospace"> b += 32;</font></div><div><font face="monospace"> } else if (c) {</font></div><div><font face="monospace"> b += 43;</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> b += 65;</font></div><div><font face="monospace"> }</font></div><div><br></div><div>Note that those two examples are subtly different. In the latter example, every branch performs an addition to 'b'. We can therefore sink all the adds to the end and perform only one add:</div><div><br></div><div><font face="monospace"> b += phi(32, 43, 65);</font></div><div><br></div><div>However in the former case things aren't so simple. The default case never does any add, so we have to speculate the add instruction in that case. For adds, this is simple - adds don't have sideeffects and we can speculate by adding with an identity (0):</div><div><br></div><div><font face="monospace"> b += phi(32, 43, 0);</font></div><div><br></div><div>However what if 'b' was a global variable? In this case, each case of the switch will have a load/add/store sequence:</div><div><br></div><div><font face="monospace"> switch(a) ---------------</font></div><div><font face="monospace"> / \ \</font></div><div><font face="monospace"> | | |</font></div><div><font face="monospace"> [t1 = load @b] [t2 = load @b] |</font></div><div><font face="monospace"> [t1 = add t1, 32] [t2 = add t2, 43] |</font></div><div><font face="monospace"> [store @b, t1] [store @b, t2] |</font></div><div><font face="monospace"> \ / /</font></div><div><font face="monospace"> v v v-------------</font></div><div><font face="monospace"> [ ]</font></div><div><br></div><div>In most cases, we cannot be sure that in the default case @b is allowed to be written to. Speculating a store in this case could be invalid. Therefore, if we want to sink the store (and thus the add and load) we need to invent a new block to sink them to.</div><div><br></div><div><font face="monospace"> switch(a) ---------------</font></div><div><font face="monospace"> / \ \</font></div><div><font face="monospace"> | | |</font></div><div><font face="monospace"> [t1 = load @b] [t2 = load @b] |</font></div><div><font face="monospace"> [t1 = add t1, 32] [t2 = add t2, 43] |</font></div><div><font face="monospace"> \ / |</font></div><div><font face="monospace"> [ p = phi(t1, t2) ] /</font></div><div><font face="monospace"> [ store @b, p ] /</font></div><div><font face="monospace"> | +------------</font></div><div><font face="monospace"> v v</font></div><div><font face="monospace"> [ ]</font></div><div><br></div><div>Creating this new block allows the switch to be turned into a trivial one that can be lowered to a bit test or jump table.</div><div><br></div><div>There is an even more complex case that appears quite a bit:</div><div><br></div><div><font face="monospace"> if (a) {</font></div><div><font face="monospace"> switch (b) {</font></div><div><font face="monospace"> case 1: c += 42; break;</font></div><div><font face="monospace"> case 2: c += 2; break;</font></div><div><font face="monospace"> default: c += 3; break;</font></div><div><font face="monospace"> }</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> switch (d) {</font></div><div><font face="monospace"> case 1: e -= 2; break;</font></div><div><font face="monospace"> case 2: e -= 6; break;</font></div><div><font face="monospace"> default: e -= 32; break;</font></div><div><font face="monospace"> }</font></div><div><font face="monospace"> }</font></div><div><br></div><div>We canonicalize this CFG to one cleanup block with six incoming arcs. In this case, it takes some nontrivial analysis to determine what to do, as it requires partitioning the incoming arcs into sets, performing different sinking operations on each (in this case two disjoint sets, but there are cases where the sets are not disjoint and some cost heuristic needs to be used).</div><div><br></div><div><b><u>2) Non-monotonicity of heuristic</u></b></div><div><br></div><div>What I'm trying to say here is the greedy algorithms work best when the heuristic they are computing is monotonic. Consider this:</div><div><br></div><div><font face="monospace"> if (a) {</font></div><div><font face="monospace"> tmp1 = *b;</font></div><div><font face="monospace"> tmp2 = *c;</font></div><div><font face="monospace"> tmp3 = tmp1 + tmp2;</font></div><div><font face="monospace"> *d = tmp3;</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> tmp4 = *b;</font></div><div><font face="monospace"> tmp5 = *c;</font></div><div><font face="monospace"> tmp6 = tmp4 + tmp5;</font></div><div><font face="monospace"> *e = tmp6;</font></div><div><font face="monospace"> }</font></div><div><br></div><div>If we proceed sequentially from the bottom of these blocks, trying to determine if sinking them is worthwhile:</div><div><br></div><div>Step 1: [*e = tmp6], [*d = tmp3]</div><div> - This is the same operation, a store, but it requires two PHIs - one for (e,d) and one for (tmp6, tmp3).</div><div> - This is NOT worthwhile. We are constraining register allocation for only one instruction commonned.</div><div><br></div><div>Step 2: [tmp6 = tmp4 + tmp5], [tmp3 = tmp1 + tmp2]</div><div> - Again, the operation is the same, but now we need another two PHIs, plus one PHI from Step 1 (the phi required for (tmp6, tmp3) is now no longer required).</div><div> - Three PHIs required for two instructions sunk. NOT worth it.</div><div><br></div><div>Step 3: [tmp5 = *c], [tmp2 = *c]</div><div> - These can be sunk, and have the same arguments so no PHIs required. We still need two of the PHIs from step 2 (the (tmp5, tmp2) phi now is no longer required)</div><div> - At this point we've sunk three instructions for two PHIs. Maybe it's worth it?</div><div><br></div><div>Step 4: [tmp4 = *b], [tmp1 = *b]</div><div> - Same as step 3, but now the (tmp4, tmp1) PHI from step 2 goes away too</div><div> - So now we're sinking 4 instructions for one PHI.</div><div> - Now it's definitely worth it!</div><div><br></div><div>Whatever heuristic one chooses, in a case like this it will get worse, then maybe get better again. So we can't simply bail out when the heuristic reaches some threshold, because maybe it will improve as we analyze more instructions!</div><div><br></div><div><b><u>3) Permutations of otherwise similar instructions</u></b></div><div><br></div><div>This is the case you describe. Stores (for example) that look similar but have been permuted:</div><div><br></div><div><font face="monospace"> if (a) {</font></div><div><font face="monospace"> *b = 52;</font></div><div><font face="monospace"> *c = 43;</font></div><div><font face="monospace"> } else {</font></div><div><font face="monospace"> *c = 87;</font></div><div><font face="monospace"> *b = 54;</font></div><div><font face="monospace"> }</font></div><div><br></div><div>If we approach this bottom-up, we will compare [*b = 54], [*c = 43], then [*c = 87], [*b = 52] and conclude that two instructions can be sunk, but 4 PHIs are required (because the target of the store and value are different in each case). If we looked at [*b = 54], [*b = 52], perhaps we would have seen that we can sink this with only *two* PHIs required and that might change our decision.</div><div><br></div><div>This is generally quite difficult and especially shows up with memory instructions like this (if c and b alias, then permuting them when sinking would be illegal. So we need alias analysis here).</div><div><br></div><div><b><u>What GVNSink attempts to solve</u></b></div><div><br></div><div>The current implementation of GVNSink was meant to solve 1) and 2), but NOT 3). 3) wasn't within scope when I was writing GVNSink, but I think 3) is doable for some cases within the framework of GVNSink.</div><div><br></div><div><u><b>How GVNSink works</b></u></div><div><br></div><div>GVNSink works by computing a value number for each IR instruction, similar to GVN. However, GVNSink's value numbering works slightly from GVN's.</div><div><br></div><div>To recap, the value number (VN) of an instruction is a function of the instruction. If VN[I] == VN[J], I and J can be considered equivalent, for some definition of equivalence.</div><div><br></div><div>In GVN, VN[I] is based upon I and all of I's operands, transitively. Therefore if VN[I] == VN[J], I and J were computed in the same way and J can be used instead of I.</div><div><br></div><div>In GVNSink, we flip this on its head. VN[I] is based upon I's *uses*, transitively. Therefore if VN[I] == VN[J], all of the uses of I are the same as all of the uses of J. Therefore I and J can be merged. So this:</div><div><br></div><div><font face="monospace"> [ %a = add %I, 1 ] [ %c = add %J, 1 ] </font></div><div><font face="monospace"> [ %b = sub %a, 5 ] [ %d = sub %c, 5 ]</font></div><div><font face="monospace"> [ ret %b ] [ ret %d ]</font></div><div><br></div><div>Can be transformed into this:</div><div><br></div><div> <font face="monospace"> [] []</font></div><div><font face="monospace"> \ /</font></div><div><font face="monospace"> [ %IJ = phi %I, %J ]</font></div><div><font face="monospace"> [ %a = add %IJ, 1 ]</font></div><div><font face="monospace"> [ %b = sub %a, 5 ]</font></div><div><font face="monospace"> [ ret %b ]</font></div><div><br></div><div>In GVNSink, we step backwards across all instructions in all incoming basic blocks (see LockstepReverseIterator). This produces, conceptually, a sequence of sets of instructions.</div><div><br></div><div>Each of these sets is analyzed in turn (see analyzeInstructionForSinking) - the value number of each contained instruction is calculated and used to determine if the entire set is mergeable or not (all values have the same VN).</div><div><br></div><div>If not all instructions in the set have the same VN, the set is pruned to just those with the same VN (or we stop if all instructions had different VNs). If this set passes extra legality checks, a SinkingInstructionCandidate is created. This contains pertinent data for the cost heuristic:</div><div><br></div><div> 1) Number of instructions from each incoming block being sunk</div><div> 2) Number of blocks to pick instructions from (this can be a subset of all the incoming blocks!)</div><div> 3) How many PHIs would be generated in total</div><div><br></div><div>After all candidates have been examined, they are sorted based on a heuristic and the best candidate picked and applied.</div><div><br></div><div>The use of value numbering in this algorithm is what allows us to do this in somewhat-linear time with respect to the number of instructions inspected.</div><div><br></div><div>Now, to solve 3), I think the component that needs swapping out is LockstepReverseIterator. This currently iterates backwards in lockstep across a set of blocks. To handle permutations, I think we could use a priority queue that feeds the main algorithm instructions from the input blocks in a slightly sorted order.</div><div><br></div><div>For example, perhaps it might order sequences of stores by their target operand (assuming alias analysis says it can), ensuring sequences of stores in different blocks appear in the same order?</div><div><br></div><div>Anyway, I hope this has helped understand a bit more about what GVNSink does, can do and how to modify it if you want to solve your problem.</div><div><br></div><div>Cheers,</div><div><br></div><div>James</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Wed, 26 Apr 2017 at 18:16 Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I have a patch i'm working on to split newgvn into a proper analysis.<div>It works (and happy to share it), it's just the interface i'm using is a little ugly (haven't decided what the right API is), but let me know what GVNSink needs from life and i'll make sure it's there :)<div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 26, 2017 at 10:09 AM, James Molloy via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">It's basically ready to commit; the reviewers were fairly happy with it. It needs rebasing on top of NewGVN and any bugs that shakes out fixed, but that's about it. <br><br>I want to get around to it soon-ish, but I've wanted that for a while!<div class="m_482060495886829570HOEnZb"><div class="m_482060495886829570h5"><br><div class="gmail_quote"><div dir="ltr">On Wed, 26 Apr 2017 at 16:50, Hongbin Zheng <<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi James,<div><br></div><div>I have an ad-hoc solution in mind to solve this problem.</div><div>But if it can be solved under the framework of GVN"Sink", it is even better.</div><div><br></div><div>any plan on your <a href="https://reviews.llvm.org/D24805" target="_blank">https://reviews.llvm.org/D24805</a>?</div><div><br></div><div>Thanks</div><div></div></div><div dir="ltr"><div>Hongbin</div></div><div dir="ltr"><div><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 26, 2017 at 2:13 AM, James Molloy <span dir="ltr"><<a href="mailto:james@jamesmolloy.co.uk" target="_blank">james@jamesmolloy.co.uk</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">Hi,<div><br></div><div>Yes, I can see why that would not work.</div><div><br></div><div>The sinking algorithm in SimplifyCFG isn't particularly clever. In particular it can't reason about memory ordering and aliasing. In unswitch1(), it can identify that the stores correlate because the correlating stores appear in the same relative source order. In unswitch2() they have been permuted, and the algorithm cannot deal with this. This requires some kind of value numbering to do efficiently.</div><div><br></div><div>The GVNSink pass that I really should get around to updating should solve this, eventually!</div><div><br></div><div>James</div><div><br></div></div><br><div class="gmail_quote"><div><div class="m_482060495886829570m_5858360018036737575m_3724635475393343372gmail-h5"><div dir="ltr">On Wed, 26 Apr 2017 at 08:19 Hongbin Zheng via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></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><div class="m_482060495886829570m_5858360018036737575m_3724635475393343372gmail-h5"><div dir="ltr"><div>Looks like this do not work:</div><div><br></div><div><div>// Type your code here, or load an example.</div><div>int a[10];</div><div><br></div><div>void unswitch2(int i, int x, int y0, int y1) {</div></div></div><div dir="ltr"><div><div> if (x) {</div><div> a[i] = y0;</div></div></div><div dir="ltr"><div><div> a[i + 1] = y1;</div><div> } else {</div><div> a[i + 1] = y0;</div><div> a[i] = y1;</div><div> }</div><div>}</div></div><div><br></div><a href="https://godbolt.org/g/Ldd5qV" target="_blank">https://godbolt.org/g/Ldd5qV</a><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 10:22 PM, Hongbin Zheng <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.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 dir="ltr">Thanks,<div><br></div><div>Looks like inst combine do the job</div></div><div class="m_482060495886829570m_5858360018036737575m_3724635475393343372gmail-m_-4621254103529992432m_-8513395923213523446HOEnZb"><div class="m_482060495886829570m_5858360018036737575m_3724635475393343372gmail-m_-4621254103529992432m_-8513395923213523446h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 9:36 PM, Davide Italiano <span dir="ltr"><<a href="mailto:davide@freebsd.org" target="_blank">davide@freebsd.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"><span>On Tue, Apr 25, 2017 at 9:24 PM, Hongbin Zheng via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
> Hi,<br>
><br>
> Is there a pass in LLVM that can optimize:<br>
><br>
> if (x)<br>
> a[i] = y0;<br>
> else<br>
> a[i] = y1;<br>
><br>
> to<br>
><br>
> a[i] = x ? y0 : y1?<br>
><br>
> I tried opt (3.9) with -O3 but looks like such an optimization do not<br>
> happened.<br>
><br>
<br>
</span>The same IR at -O3 for both cases on this example.<br>
<a href="https://godbolt.org/g/Tk2MM8" rel="noreferrer" target="_blank">https://godbolt.org/g/Tk2MM8</a><br>
<span class="m_482060495886829570m_5858360018036737575m_3724635475393343372gmail-m_-4621254103529992432m_-8513395923213523446m_-7575599966051767950HOEnZb"><font color="#888888"><br>
--<br>
Davide<br>
<br>
"There are no solved problems; there are only problems that are more<br>
or less solved" -- Henri Poincare<br>
</font></span></blockquote></div><br></div>
</div></div></blockquote></div><br></div></div></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</blockquote></div><br></div></div></div></blockquote></div>
</div></div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>
</blockquote></div></div>