[LLVMdev] MergeFunctions: reduce complexity to O(log(N))
Stepan Dyatkovskiy
stpworld at narod.ru
Fri Jan 17 12:25:19 PST 2014
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MergeFunctions.doc.tar.gz
Type: application/x-gzip
Size: 20480 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140118/16992e44/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mergefunctions-less-comparison-2014-01-17.patch.tar.gz
Type: application/x-gzip
Size: 10240 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140118/16992e44/attachment-0001.bin>
More information about the llvm-dev
mailing list