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

[Reid Kleckner via llvm-dev]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180924/57d8d8cd/attachment.html>