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

[Stepan Dyatkovskiy]

ping
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
>