[llvm-dev] RFC Storing BB order in llvm::Instruction for faster local dominance

[Sanjoy Das via llvm-dev]

On Mon, Sep 24, 2018 at 4:03 PM Reid Kleckner <rnk at google.com> wrote:
>
> On Mon, Sep 24, 2018 at 12:30 PM Sanjoy Das <sanjoy at playingwithpointers.com> wrote:
>>
>> On Mon, Sep 24, 2018 at 11:31 AM Sanjoy Das
>> <sanjoy at playingwithpointers.com> wrote:
>> >
>> > Did you consider using the waymarking algorithm we already use for
>> > going from Use->User to store the offset of an instruction in a basic
>> > block?  We could steal the two bits needed from the bb parent pointer
>> > in the instruction.
>>
>> Actually, now that I think of it, in llvm::Instruction we have 6 bits
>> to play with so should be able to create a more efficient scheme than
>> the one used in llvm::Use (well, we have 6 bits even in llvm::Use but
>> efficiency is probably not as important there because Use lives in an
>> array, not a linked list).
>
>
> I hadn't considered it, and it's an interesting idea. I'd rather not pursue it because I think stealing bits from ilist just for Instruction linked lists is going to be difficult. It also has runtime costs for linked list iteration, so it's not completely free. I'd rather get the speed win, spend the memory, and then try to win back the space if it seems like a priority.

We don't need to steal from ilist Prev/Next if we're okay with the
vanilla two-bits-per-node waymarking (which we can get from the parent
basicblock pointer) which may be good enough since it will reduce the
number of hops needed for local dominance from O(n) to O(log n).  I
was kind of hoping that it would be straightforward to pull out the
waymarking code out of Value and re-using it; but if you'd prefer not
doing that now I'm fine with it.

-- Sanjoy