[LLVMdev] MergeFunctions: reduce complexity to O(log(N))
Sean Silva
chisophugis at gmail.com
Wed Jan 29 11:52:27 PST 2014
On Tue, Jan 28, 2014 at 2:47 PM, Tobias von Koch
<tobias.von.koch at gmail.com>wrote:
> Hi Stepan,
>
> Sorry for the delay. It's great that you are working on MergeFunctions as
> well and I agree, we should definitely try to combine our efforts to
> improve MergeFunctions.
>
> Just to give you some context, the pass (with the similar function merging
> patch) is already being used in a production setting. From my point of
> view, it would be better if we focus on improving its capability of merging
> functions at this stage rather than on reduction of compilation time.
>
> I'll give a brief overview of how our similar function merging algorithm
> works (you can also watch the presentation from the US LLVM conference to
> hear me explain it using an animation).
>
> 1. Hash all functions into buckets
>
> In each bucket, separately:
>
> 2. Compare functions pair-wise and determine a
> similarity metric for each pair (%age of equivalent instructions)
>
> 3. Merge identical functions (with similarity = 100%), update call
> sites for those functions.
>
> 4. If the updates of call sites have touched other functions,
> go back to step 2 and re-compare *only* those functions to all
> others in their buckets.
>
> Finally,
>
> 5. Form groups of similar functions for merging:
> a) Pick most similar pair (A,B)
> b) Find all functions C that are also similar to B but are not
> more similar to some other function D.
> c) Merge A with B and all the C's.
> Repeat until there are no more functions to merge.
>
> As you can see, we need to compute a similarity measure for each pair of
> functions in a bucket. If I understand correctly, your patch reduces
> compile-time by avoiding comparisons of functions that cannot be identical.
> That's exactly what you want to do if you only want to merge identical
> functions. However, because we also need to determine whether functions are
> merely *similar*, I can't see how your idea could be applied in that case.
>
Yeah, the existing pass only tries to merge identical functions (identical
in machine code). I'm wondering if the "similar" function merging would be
better as a separate pass (I'm genuinely wondering; I have no clue). I
would wait for Nick's feedback.
-- Sean Silva
>
> Looking at your statistics, I see that you are considering a very large
> number of functions. I don't know which benchmarks you are using, but I
> doubt that many of these are worth merging. For instance, you rarely gain a
> code size benefit from merging functions with just a few instructions. Our
> patch takes care of this using thresholds. It's worth looking at actual
> code size reductions, rather than just numbers of functions merged/
> compilation time spent comparing functions. It turns out that the number of
> functions in each bucket is really quite small once you apply some
> heuristics (and could still be further reduced!).
>
> Given your experience with MergeFunctions, it would be really great if you
> could review our patch and also try it out on your benchmarks.
>
> Tobias
>
>
> On 24/01/2014 19:11, Stepan Dyatkovskiy wrote:
>
>> Hi Tobias.
>>
>> So, what do you think?
>>
>> If it means to much extra-job for your team, may be I can help you
>> somehow? I really would like to.
>>
>> -Stepan
>>
>> Stepan Dyatkovskiy wrote:
>>
>>> Hi Tobias,
>>>
>>> I can't really see a way to combine our approach with your patch. What
>>>> are your thoughts?
>>>>
>>>
>>> I think it is possible. Even more - we need to combine our efforts, in
>>> order to bring this pass into real live.
>>> I'have read your presentation file, and unfortunately read your patch
>>> only a little.
>>> How exactly you scan functions on 2nd stage? Could you explain the
>>> algorithm in few words, how you compare workflow? Is it possible to
>>> scan binary tree instead of hash table? ...OK.
>>>
>>> That's how I see the modification. Now its important to explain idea,
>>> so consider the simplest case: you need to catch two functions that
>>> are differs with single instruction somewhere.
>>>
>>> 1. Imagine, that IR *module* contents is represented as binary tree:
>>> Each line (trace) from root to terminal node is a function.
>>> Each node - is function's primitive (instruction opcode, for example).
>>> Down - is direction to terminal nodes, up - is direction to the root.
>>>
>>> 2. Now you are standing on some node. And you have two directions
>>> down-left and down-right.
>>>
>>> 3. If you are able to find two equal sub-traces down (at left and at
>>> right), then the only difference lies in this node. Then we catch that
>>> case.
>>>
>>> 4. Even more, if two subtrees at left and at right are equal, than you
>>> catch at once all the cases that are represented by these subtrees.
>>>
>>> I still didn't look at you patch carefully. Sorry.. But I hope that
>>> helps, and I'll try look at it in nearest time and perhaps its not the
>>> best solution I gave in this post.
>>>
>>> -Stepan
>>>
>>> 22.01.2014, 20:53, "Tobias von Koch" <tobias.von.koch at gmail.com>:
>>>
>>>> Hi Stepan,
>>>>
>>>> As you've seen we have recently implemented a significant enhancement to
>>>> the MergeFunctions pass that also allows merging of functions that are
>>>> only similar but not identical
>>>> (http://llvm-reviews.chandlerc.com/D2591).
>>>>
>>>> Our patch also changes the way that functions are compared quite
>>>> significantly. This is necessary because we need to compare all
>>>> functions in a bucket in order to get a similarity measure for each
>>>> pair, so we can then decide which 'groups' of functions to merge.
>>>>
>>>> I can't really see a way to combine our approach with your patch. What
>>>> are your thoughts?
>>>>
>>>> Another way to improve the performance of MergeFunctions might be to
>>>> make the hash function better. I've already added the size of the first
>>>> BB to it, and perhaps there are other factors we could try... if we
>>>> don't have to compare functions in the first place (because they're in
>>>> different buckets) then that's obviously a much bigger win.
>>>>
>>>> Thanks,
>>>> Tobias
>>>>
>>>> On 17/01/2014 20:25, Stepan Dyatkovskiy wrote:
>>>>
>>>> Hi all,
>>>>>
>>>>> 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.
>>>>>
>>>>> The idea, is to replace the result of comparison from "bool" to
>>>>> "-1,0,1". In another words: define order relation on functions set.
>>>>> To be sure, that functions could be comparable that way, we have to
>>>>> prove that order relation is possible on all comparison stage.
>>>>>
>>>>> The last one is possible, if for each comparison stage we
>>>>> implement has
>>>>> next properties:
>>>>> * reflexivity (a <= a, a == a, a >= a),
>>>>> * antisymmetry (if a <= b and b <= a then a == b),
>>>>> * transitivity (a <= b and b <= c, then a <= c)
>>>>> * asymmetry (if a < b, then a > b or a == b).
>>>>>
>>>>> Once we have defined order relation we can store all the functions in
>>>>> binary tree and perform lookup in O(log(N)) time.
>>>>>
>>>>> This post has two attachments:
>>>>> 1. The patch, that has implementation of this idea.
>>>>> 2. The MergeFunctions pass detailed description, with explanation how
>>>>> order relation could be possible.
>>>>>
>>>>> Hope it helps to make things better!
>>>>>
>>>>> -Stepan.
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>>
>>>>
>>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140129/77b8206b/attachment.html>
More information about the llvm-dev
mailing list