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

[Sean Silva]

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.

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 (<http://llvm-reviews.chandlerc.com/D2591>) are proposing?

-- Sean Silva


On Fri, Jan 17, 2014 at 3:25 PM, Stepan Dyatkovskiy <stpworld at narod.ru>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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140129/233cebc5/attachment.html>