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

[Tobias von Koch]

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
>