<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 3, 2016 at 10:00 PM, Amos Robinson <span dir="ltr"><<a href="mailto:amos.robinson@gmail.com" target="_blank">amos.robinson@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><br><div class="gmail_quote"><span class=""><div dir="ltr">On Wed, 4 May 2016 at 14:21 Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">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">As a general rule of thumb, if it only removes scalar code, it's pretty useless.<div>If it helps it prove it can remove memory operations, it's great.<br></div></div></blockquote><div><br></div></span><div>Perhaps I am misunderstanding, but I agree my example wasn't very exciting as-is but I imagine you could replace addition with some reasonably expensive function call and it would be a bit more compelling.</div></div></div></blockquote><div>What i've given you is a broad generalization that comes down to "on modern processors you often have to remove 20-100x more arithmetic to match the improvement from removing a single load or other memory op". </div><div><br></div><div>They often can issue multiple arithmetic ops per cycle, and get the results from all of them in a single cycle.</div><div><br></div><div>Are there exceptions to my generalization? Sure. If you call a function 10 billion times, and you remove a single cycle from it, ...</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div>However, I am coming at this from a much higher level of abstraction: I am working on a query compiler that takes a whole bunch of queries and fuses them together into one. Removing duplicates in this case is also much simpler than general GVN, and I'm just trying to get a good story about the relationship.</div></div></div></blockquote><div>GVN would work well for this, but depending on your situation, it may also be massive overkill ;)</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span class=""><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div></div><div><span style="line-height:1.5"> </span><br></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div></div><div>Often, in your example, it's accesses that are loop invariant but common to other accesses in the loop that are most promising.</div><div><br></div><div>IE (taken from a test i wrote for GCC's VN)</div><div><div>int vnum_test8(int *data)</div><div>{</div><div> int i;</div><div> int stop = data[3];</div><div> int m = data[4];</div><div> int n = m;</div><div> int p;</div><div> for (i=0; i<stop; i++) {</div><div> int k = data[2];</div><div> data[k] = 2;</div><div> data[0] = m - n;</div><div> k = data[1];</div><div> m = m + k;</div><div> n = n + k;</div><div> p = data[0];</div><div> }</div><div> return p;</div><div>}</div></div><div><br></div><div>We test that we eliminate m-n in favor of 0, replace n with m, and set p to 0</div><div><br></div><div><br></div><div>Note that this requires proving a bunch of things about the memory accesses here, and properly value numbering memory accesses (which current GVN will not do).<span style="line-height:1.5"> </span></div></div></blockquote><div><br></div></span><div>Do you mean, for example, proving that accessing data[k] does not segfault here, or aliasing things?</div><div><br></div></div></div>
</blockquote></div></div><div class="gmail_extra"><br></div><div class="gmail_extra">It does not require any aliasing assistance, just symbolically evaluating where these things access.</div><div class="gmail_extra"><br></div></div>