[LLVMdev] MergeFunctions: reduce complexity to O(log(N))

[Stepan Dyatkovskiy]

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