First patch of patch series that improves MergeFunctions performance time from O...
authorStepan Dyatkovskiy <stpworld@narod.ru>
Thu, 13 Mar 2014 11:54:50 +0000 (11:54 +0000)
committerStepan Dyatkovskiy <stpworld@narod.ru>
Thu, 13 Mar 2014 11:54:50 +0000 (11:54 +0000)
commitab35f3fd0cc745ed110bd2b91bd5683b7ab75400
treed8b64118e3c683194dc1ca9f780db35c0e907e7b
parent2d74092f5f420bbf10b526835b36d9a521746c2a
First patch of patch series that improves MergeFunctions performance time from O(N*N) to
O(N*log(N)). The idea is to introduce total ordering among functions set.
That allows to build binary tree and perform function look-up procedure in O(log(N)) time.

This patch description:
Introduced total ordering among Type instances. Actually it is improvement for existing
isEquivalentType.
0. Coerce pointer of 0 address space to integer.
1. If left and right types are equal (the same Type* value), return 0 (means equal).
2. If types are of different kind (different type IDs). Return result of type IDs
comparison, treating them as numbers.
3. If types are vectors or integers, return result of its
pointers comparison (casted to numbers).
4. Check whether type ID belongs to the next group:
* Void
* Float
* Double
* X86_FP80
* FP128
* PPC_FP128
* Label
* Metadata
If so, return 0.
5. If left and right are pointers, return result of address space
comparison (numbers comparison).
6. If types are complex.
Then both LEFT and RIGHT will be expanded and their element types will be checked with
the same way. If we get Res != 0 on some stage, return it. Otherwise return 0.
7. For all other cases put llvm_unreachable.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203788 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Transforms/IPO/MergeFunctions.cpp