<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Jul 30, 2013, at 6:46 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Tue, Jul 30, 2013 at 2:20 PM, Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>> wrote:<br><blockquote type="cite"><br>On Jul 29, 2013, at 4:08 PM, Guo, Xiaoyi <<a href="mailto:Xiaoyi.Guo@amd.com">Xiaoyi.Guo@amd.com</a>> wrote:<br><br>Hi,<br><br>We have a benchmark where there are 128 MAD computations in a loop. (See the<br>attached IR.) Creating SCEVs for these expressions takes a long time, making<br>the compile time too long. E.g., running opt with the “indvars” pass only<br>takes 45 seconds.<br><br>It seems that the majority of the time is spent in comparing the complexity<br>of the expression operands to sort them.<br><br>I realize that the expression grows to be really large towards the end of<br>the loop.<br><br>I don’t know of all the uses of the built SCEV. But I image it won’t be very<br>useful for such complex expressions. Yet, it’s making the compile time much<br>longer.<br><br>So I’m wondering if it would make sense to abort the creation of SCEV when<br>the expression gets really complex and large. Or is there any way to further<br>optimize the performance of SCEV building for such cases.<br><br>Thanks in advance for any response.<br><br><br>Nice test case. I tried printing the SCEV… oops. I haven’t seen a case this<br>bad, but I know you’re not the first to run into this problem.<br><br>There are two steps in GroupByComplexity, sorting (std::sort) and grouping<br>(N^2).<br><br>The sort calls SCEVComplexityCompare::compare() which can make multiple<br>recursive calls for nodes with multiple operands. This looks like it could<br>be a disaster for expressions that are not strictly trees--exponential in<br>the size of the DAG.<br><br></blockquote>Yes, this is why i suggested computing some deterministic "complexity<br>hash" on the way, and caching it in the SCEV.<br>It would not help if they were all the same, but if they were<br>different only at the end, you wouldn't end up comparing every operand<br>to get there.<br>If they are all the same, you are right that cut-off is the only<br>reasonable answer.<br>Or calculate "complexity" in a way that does not require operand by<br>operand comparison (IE compute a "complexity" number instead of a<br>hash, as you build the SCEV). It's just trying to get a canonical<br>sort here.<br>This would at least make the sort fast, grouping can't be made linear<br>unless you are willing to trust the hash :)</div></blockquote></div><br><div>That would be ideal. I wish it were obvious to me how to implement it.</div><div><br></div><div>Xiaoyi’s simple fix handled this scenario and was totally consistent with the current implementation. It seems we’re not yet running into the issue of visiting all paths in a DAG. I don’t want to discourage a more general fix/redesign though. We could probably recover more compile time in many cases.</div><div><br></div><div>-Andy</div></body></html>