[LLVMdev] MergeFunctions: reduce complexity to O(log(N))
stpworld at narod.ru
Tue Jan 21 09:58:08 PST 2014
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
> 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!
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev