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

[Daniel Berlin via llvm-dev]

On Mon, Sep 14, 2015 at 11:41 AM, escha <escha at apple.com> wrote:
> 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.

Yes, it will be.

For reference, we had two ways of doing this in GCC:

One, things had id numbers, so we could create bitmaps that told us
what was in a set without storing pointers :)
There were also flags, but in practice, flags were as fast as the bitmaps.


>
> —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
>