[LLVMdev] MergeFunctions: reduce complexity to O(log(N))
Tobias von Koch
tobias.von.koch at gmail.com
Wed Jan 22 08:53:27 PST 2014
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
>
More information about the llvm-dev
mailing list