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

[Stepan Dyatkovskiy]

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>