[llvm-dev] Fwd: Is the fast register allocator O(n^2) in the size of the function?

[David Blaikie via llvm-dev]

+Lang who might still have some register allocation knowledge kicking
around (but his responses may be a bit delayed)

Generally there's a bunch of algorithms that don't scale really well on
especially large function - and I'd encourage users to modify any code
generators to chunk up functions, or they'll be chasing down these sort of
issues indefinitely, really.

But improvements are certainly appreciated - though I don't have any
particular knowledge or pointers regarding how to improve the register
allocator. (my gut reaction would be that probably a lot of people have
looked and haven't found better tradeoffs - but I'm a bit of a pessimist,
fresh eyes can often help :) )

On Wed, Feb 10, 2021 at 10:48 AM Dwight Guth via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi,
>
> I am the maintainer of an open source compiler that makes use of the
> LLVM toolchain to perform code generation. A user of our compiler, who
> is working on a proprietary project, recently shared with me an
> example where our toolchain was invoking `llc -O0` on a file with a
> rather large function in it, and the register allocation pass was
> taking upwards of 5 minutes. This seemed unusual to me, so I
> downloaded the debug symbols for LLVM (this was with LLVM 11.0.0), and
> I found that slightly over 50% of the runtime of LLC was spent within
> a very small loop within llvm::MachineRegisterInfo::hasOneNonDBGUse. I
> believe this loop to correspond to the while loop in
> llvm::MachineRegisterInfo::defusechain_iterator::advance.
>
> It looks like this function is just scanning through all the defs and
> uses of a register in the function until it finds one that it
> considers satisfactory? That seems like it would be introducing
> behavior that is quadratic in the size of the function to me. Am I
> missing something? Is there some other, more sensible reason why the
> profile seems so dependent on this one loop of code? Did I
> misunderstand something?
>
> My end goal here would be to submit a patch that might optimize this
> case, since it seems to me something that might be able to be computed
> more efficiently. But I don't understand the code or the algorithm
> hugely well, so I was hoping someone could give me some pointers on
> where to get started with something like this.
>
> Does anyone have any suggestions on what I could do to make register
> allocation run faster on quite large functions?
>
> Thanks,
>
> --
> Dwight Guth
>
> Chief Information Officer
> Runtime Verification, Inc.
> Email: dwight.guth at runtimeverification.com
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210222/73321777/attachment.html>