llvm dev - Jan 2014 - [LLVMdev] MergeFunctions: reduce complexity to O(log(N))

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>

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).
>
> 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
>

Hi, Stepan...

Each insertion in the tree will be O(log(N)), which would make the whole
process O(N log(N)), right?
It is still an improvement over an O(N^2) all-to-all check, of course....

Have you explored alternatives by improving the hashing or doing some
secondary hashing? That might have an even bigger impact, potentially
making it O(N) on cases with perfect-hashing.



On Fri, Jan 17, 2014 at 12:25 PM, Stepan Dyatkovskiy <stpworld at
narod.ru>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).
>
> 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
>
>

-- 
 Raúl E. Silvera
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140121/3ba0bbe3/attachment.html>

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

Hi Stepan,

As you've seen we have recently implemented a significant enhancement to 
the MergeFunctions pass that also allows merging of functions that are 
only similar but not identical
(http://llvm-reviews.chandlerc.com/D2591).

Our patch also changes the way that functions are compared quite 
significantly. This is necessary because we need to compare all 
functions in a bucket in order to get a similarity measure for each 
pair, so we can then decide which 'groups' of functions to merge.

I can't really see a way to combine our approach with your patch. What 
are your thoughts?

Another way to improve the performance of MergeFunctions might be to 
make the hash function better. I've already added the size of the first 
BB to it, and perhaps there are other factors we could try... if we 
don't have to compare functions in the first place (because they're in 
different buckets) then that's obviously a much bigger win.

Thanks,
Tobias

On 17/01/2014 20:25, 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).
>
> 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
>

Hi Tobias,
> I can't really see a way to combine our approach with your patch. What
> are your thoughts?
I think it is possible. Even more - we need to combine our efforts, in order to
bring this pass into real live.
I'have read your presentation file, and unfortunately read your patch only a
little.
How exactly you scan functions on 2nd stage? Could you explain the algorithm in
few words, how you compare workflow? Is it possible to scan binary tree instead
of hash table? ...OK.

That's how I see the modification. Now its important to explain idea, so
consider the simplest case: you need to catch two functions that are differs
with single instruction somewhere.

1. Imagine, that IR *module* contents is represented as binary tree:
Each line (trace) from root to terminal node is a function.
Each node - is function's primitive (instruction opcode, for example).
Down - is direction to terminal nodes, up - is direction to the root.

2. Now you are standing on some node. And you have two directions down-left and
down-right.

3. If you are able to find two equal sub-traces down (at left and at right),
then the only difference lies in this node. Then we catch that case.

4. Even more, if two subtrees at left and at right are equal, than you catch at
once all the cases that are represented by these subtrees.

I still didn't look at you patch carefully. Sorry.. But I hope that helps,
and I'll try look at it in nearest time and perhaps its not the best
solution I gave in this post.

-Stepan

22.01.2014, 20:53, "Tobias von Koch" <tobias.von.koch at
gmail.com>:
> Hi Stepan,
>
> As you've seen we have recently implemented a significant enhancement
to
> the MergeFunctions pass that also allows merging of functions that are
> only similar but not identical
> (http://llvm-reviews.chandlerc.com/D2591).
>
> Our patch also changes the way that functions are compared quite
> significantly. This is necessary because we need to compare all
> functions in a bucket in order to get a similarity measure for each
> pair, so we can then decide which 'groups' of functions to merge.
>
> I can't really see a way to combine our approach with your patch. What
> are your thoughts?
>
> Another way to improve the performance of MergeFunctions might be to
> make the hash function better. I've already added the size of the first
> BB to it, and perhaps there are other factors we could try... if we
> don't have to compare functions in the first place (because they're
in
> different buckets) then that's obviously a much bigger win.
>
> Thanks,
> Tobias
>
> On 17/01/2014 20:25, 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).
>>
>>  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

I talked with Nick (CC'd) about mergefunc at one of the socials, and he had
some really neat ideas for speeding this up which might complement or
supercede the approach that you are proposing (also the one that Tobias is
proposing). For example, he had one suggestion based on callgraph SCC's
which was really neat.

Nick, can you maybe give some more details on the ideas you told me and/or
provide some feedback about the directions that Stepan (this thread) and
Tobias (<http://llvm-reviews.chandlerc.com/D2591>) are proposing?

-- Sean Silva


On Fri, Jan 17, 2014 at 3:25 PM, Stepan Dyatkovskiy <stpworld at
narod.ru>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).
>
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140129/233cebc5/attachment.html>