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

[Daniel Berlin via llvm-dev]

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