[RDA] Use TinyPtrVector to store reaching defs (NFCI)
authorNikita Popov <nikita.ppv@gmail.com>
Sun, 5 Apr 2020 15:59:57 +0000 (17:59 +0200)
committerNikita Popov <nikita.ppv@gmail.com>
Wed, 8 Apr 2020 15:46:24 +0000 (17:46 +0200)
commit952c2741599ed492cedd37da895d7e81bc175ab9
tree7a6f9da82117924774b759f6622ed5429d0dfd03
parent8abfd2c3bb0d66a123b6a6ae590a3d0200f7a688
[RDA] Use TinyPtrVector to store reaching defs (NFCI)

RDA currently uses SmallVector<int, 1> to store reaching definitions.
A SmallVector<int, 1> is 24 bytes large, and X86 currently has
164 register units, which means we need 3936 bytes per block.
If you have a large function with 1000 blocks, that's already 4MB.

A large fraction of these reg units will not have any reaching defs
(say, those corresponding to zmm registers), and many will have just
one. A TinyPtrVector serves this use-case much better, as it only
needs 8 bytes per register if it has 0 or 1 reaching defs.

As the name implies, TinyPtrVector is designed to work with pointers,
so we need to add some boilerplate to treat our reaching def integers
as pointers, using an appropriate encoding. We need to keep the low
bit free for tagging, and make sure at least one bit is set to
distinguish the null pointer.

Differential Revision: https://reviews.llvm.org/D77513
llvm/include/llvm/CodeGen/ReachingDefAnalysis.h