<div dir="ltr">I talked with Nick (CC'd) about mergefunc at one of the socials, and he had some really neat ideas for speeding this up which might complement or supercede the approach that you are proposing (also the one that Tobias is proposing). For example, he had one suggestion based on callgraph SCC's which was really neat.<div>
<br></div><div>Nick, can you maybe give some more details on the ideas you told me and/or provide some feedback about the directions that Stepan (this thread) and Tobias (<<a href="http://llvm-reviews.chandlerc.com/D2591">http://llvm-reviews.chandlerc.com/D2591</a>>) are proposing?</div>
<div><br></div><div>-- Sean Silva</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jan 17, 2014 at 3:25 PM, Stepan Dyatkovskiy <span dir="ltr"><<a href="mailto:stpworld@narod.ru" target="_blank">stpworld@narod.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I propose simple improvement for MergeFunctions pass, that reduced its complexity from O(N^2) to O(log(N)), where N is number of functions in module.<br>
<br>
The idea, is to replace the result of comparison from "bool" to "-1,0,1". In another words: define order relation on functions set.<br>
To be sure, that functions could be comparable that way, we have to prove that order relation is possible on all comparison stage.<br>
<br>
The last one is possible, if for each comparison stage we implement has next properties:<br>
* reflexivity (a <= a, a == a, a >= a),<br>
* antisymmetry (if a <= b and b <= a then a  == b),<br>
* transitivity (a <= b and b <= c, then a <= c)<br>
* asymmetry (if a < b, then a > b or a == b).<br>
<br>
Once we have defined order relation we can store all the functions in binary tree and perform lookup in O(log(N)) time.<br>
<br>
This post has two attachments:<br>
1. The patch, that has implementation of this idea.<br>
2. The MergeFunctions pass detailed description, with explanation how order relation could be possible.<br>
<br>
Hope it helps to make things better!<span class="HOEnZb"><font color="#888888"><br>
<br>
-Stepan.<br>
</font></span><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div>