[llvm-dev] RFC: speedups with instruction side-data (ADCE, perhaps others?)

[escha via llvm-dev]

I tried changing it to 16 and only saw a very small speedup. I’m pretty sure that no matter how you slice it, adding every single instruction in a function to a set is going to be expensive.

—escha

> On Sep 14, 2015, at 11:34 AM, Daniel Berlin <dberlin at dberlin.org> wrote:
> 
> I did something similar for dominators, for GVN, etc.
> All see significant speedups.
> 
> However, the answer i got back when i mentioned this was "things like
> ptrset and densemap should only have a small performance difference
> from side data when used and sized right", and i've found this to
> mostly be true after looking harder.
> 
> In the case you are looking at, i see:
> 
> -  SmallPtrSet<Instruction*, 128> Alive;
> 
> This seems ... wrong.
> In fact, it seems optimally bad.
> 
> 
> This says the small ptr set size is 128.
> That is, the smallsize is 128.
> 
> SmallPtrSet will linear search the array when it's size <= smallsize,
> and otherwise fall back to building a non-small array and using better
> algorithms.
> 
> Linear searching a 128 member array == slow
> 
> I bet if you change the 128 to 8, you will see significant speedups.
> 
> 
> 
> On Mon, Sep 14, 2015 at 11:23 AM, Steve King via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> On Mon, Sep 14, 2015 at 9:37 AM, escha via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>>> Are there any other passes that could benefit from having a single bit (or similarly small amount) of per-Instruction metadata local to the pass, i.e. to avoid having to keep a side-Set of instructions...
>> 
>> FWIW, I have a target specific pass that needs exactly this sort of
>> tracking.  Once you offer 1 bit, it's a slippery slope to giving a
>> whole pointer.  I like your idea regardless.
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev