[LLVMdev] MergeFunctions: reduce complexity to O(log(N))
Duncan P. N. Exon Smith
dexonsmith at apple.com
Tue Jan 21 11:23:05 PST 2014
Hi Stepan,
This looks interesting! Some high-level comments:
- Please post the patch untarred next time. Also, I'm not sure if it's typical
to provide supporting documents in .doc format; while many of us probably
have access to Word, a more portable and email-friendly format (like text,
markdown or rst) is probably better.
- Have you profiled this? What's the speedup? I second Raul's question about
whether improving the hashing (or doing secondary hashing) could result in a
larger benefit (maybe even with simpler code).
- At the beginning of FunctionComparator::cmpEnumerate, you have a comment that
you can't introduce an order relation for cross-references, and the following
code:
// Unfortunately we can't introduce order relation for
// cross reference case. It is possible for self-reference only.
if (V1 == F1) {
if (V2 == F2)
return 0;
return -1;
}
if (V2 == F2) {
if (V1 == F1)
return 0;
return 1;
}
Can't this break asymmetry? Doesn't breaking the ordering relation cause a
correctness problem? I.e., what am I missing here?
I also have a few low-level comments (and nitpicks):
- The comments at the top of the file don't match the new implementation!
- Lots of strange tabbing after your changes. E.g.:
+ int cmpGEP(const GetElementPtrInst *GEP1,
const GetElementPtrInst *GEP2) {
- After the FunctionPtr class declaration, you have an extra blank line. There
are a few of these scattered through (e.g., at the beginning of
FunctionComparator::cmpConstants).
- Your new helper functions (such as cmpNumbers) that are local to the file
should be declared 'static'.
- You use the following pattern throughout:
int Res;
// ...
Res = cmpNumbers(I1->getNumOperands(), I2->getNumOperands());
if (Res != 0)
return Res;
whereas, since you never use Res unless it's non-zero, I think the
following is more clear and concise:
if (int Res = cmpNumbers(I1->getNumOperands(), I2->getNumOperands()))
return Res;
- I'm not sure if your MERGEFUNC_SANITY should be included the way it is:
+//#define MERGEFUNC_SANITY 900
+#ifdef MERGEFUNC_SANITY
- I’m also unsure about the following:
+ // If we have some problematic functions, perhaps we would like
+ // to keep declarations only, and those definitions fires the problem.
+ // We could insert manualy last ones (notepad, nano, vi, whatever else :-) )
+#if 0
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
+ Function *F = I;
+ F->deleteBody();
+ }
+#endif
Cheers,
Duncan
On Jan 21, 2014, at 9:58 AM, Stepan Dyatkovskiy <stpworld at narod.ru> wrote:
> 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).
For asymmetry, I think it’s: if a < b, then not a > b and not 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
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
More information about the llvm-dev
mailing list