<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jul 22, 2015 at 11:33 PM, John Regehr <span dir="ltr"><<a href="mailto:regehr@cs.utah.edu" target="_blank">regehr@cs.utah.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Interesting. Do you happen to have some examples laying around?<br>
</blockquote>
<br></span>
Sorry, no, I'll have to re-run. I felt that the select-heavy results were sort of humorous and clever at first, but then just annoying.<span class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Except for decode-limited situations, in general decreasing the critical path length is more important<br>
than eliminating instructions. The critical path length is a target-independent lower bound on the<br>
maximum achievable execution speed; the number of instructions is not.<br>
</blockquote>
<br></span>
Sounds easy enough. I'll give it a try. I've observed many situations where Souper can shorten the critical path but I hadn't really thought about making that into a top-level goal.<br></blockquote><div><br></div><div>What I said is sort of misleading in that the targets have a variety of "exotic" instructions that can effectively collapse multiple nodes in the critical path e.g. x86 BMI, PPC rlwinm, etc. Even stuff like whether the target has ANDN will affect the critical path (or an instruction taking a general truth table). Also the precise cost in a critical path of the individual instructions can vary a fair <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__amount.to&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=0ifShjQzJ6zf1eggef90Srhym1waTTSPalQiQbm0lmc&s=7bIuaudgOnWWUJ9tUQ6Q0zbY_SvnjvPAdPJXnEBGU3Y&e=">amount.to</a> the extent that except for getting rid of mul's or div's it's not a universal win (even with mul, there are often situations where the mul latency doesn't cost you anything, so the mul is effectively "cheap as an add").</div><div><br></div><div>The above notwithstanding, the critical path is still likely to be a better indicator than number than instructions. Ultimately the hardware implementation of these instructions is critical-path-limited, so besides actually reducing the critical path of instructions, optimizing for critical path is more likely to land you near something which might actually be a single cycle instruction in the hardware. That's my intuition, at least.</div><div><br></div><div><br></div><div>I guess another way to select interesting transformations could be to look for sequences where the result uses a "subset" of the input instruction sequence. E.g. if the input instruction sequence involves a CMP, then reducing the input sequence to a single CMP is a win. If the input contain a shift-imm, then reducing the entire sequence to a shift-imm ("absorbing" into it) is a win. Maybe there is a generalization of this intuition to multiple-instruction result sequences?</div><div><br></div><div><div>%0:i32 = var</div><div>%1:i32 = addnw 1:i32, %0</div><div>%2:i32 = shl 1:i32, %1</div><div>infer %2</div><div>%3:i32 = shl 2:i32, %0</div><div>result %3</div></div><div><br></div><div><div>%0:i8 = var</div><div>%1:i1 = ult 191:i8, %0</div><div>%2:i1 = slt 255:i8, %0</div><div>%3:i1 = or %1, %2</div><div>infer %3</div><div>%4:i1 = sle 192:i8, %0</div><div>result %4</div></div><div><br></div><div><div>%0:i32 = var</div><div>%1:i32 = shlnsw %0, 1:i32</div><div>%2:i32 = or 1:i32, %1</div><div>%3:i1 = slt %1, %2</div><div>infer %3</div><div>result 1:i1</div></div><div><br></div><div>"or" and "and" are basically interchangeable as far as cost is concerned, so this one also seems like a "subset":<br></div><div><br></div><div><div>%0:i32 = var</div><div>%1:i32 = addnsw 4294967295:i32, %0</div><div>%2:i32 = var</div><div>%3:i32 = or 1:i32, %2</div><div>%4:i32 = addnsw %1, %3</div><div>infer %4</div><div>%5:i32 = and 4294967294:i32, %2</div><div>%6:i32 = add %0, %5</div><div>result %6</div></div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Thanks,<br>
<br>
John<br>
</blockquote></div><br></div></div>