tree 923a87b66ed97c2d52f9e8cc6d94a3d605848d48
parent ca5346313782f53658ed383e802f6e45aaeacd42
author Nicolai Hähnle <nicolai.haehnle@amd.com> 1744311608 -0700
committer GitHub <noreply@github.com> 1744311608 -0700
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsFcBAABCAAQBQJn+BU4CRC1aQ7uu5UhlAAAxawQADGNj5MjGQxf5Z7Nf8E5jbQ+
 1v8+VIawdM9L30Lb6ifLkAj2rCqY2o5KDOJOFxZ9yrPPJMOUbuoYA75sG+uWlLYN
 58jx0hDaOo2Re4q9NCSg0NRbxOQpEI/7BpDZGChQkeSjJFRx6RqvlCmq4IEWOlAQ
 FskeDI8zAOzxChyEWwmLtTmfTIetXdRAm4FiXURCUpBL6h9ZBrUo8HaxhxtutX9k
 YG/RWzNLPJ5oj9I5At6AGRPycvtB5rb0P+sLWjWz66YnXfIViHARreDLhoSPSzGT
 24oGtTrXcheBxT/OMsob80+k9OzyyOUkRWQNcfBw0mpBoAQ6QgnfuoIzWei+31Qd
 RldUyJRjf1pBil6SHQHrk5DdJ3XJVaBHP64fXWTDB97er9W+3esmCldqqVT8TxxD
 BG7BOQj0e3ycpIIMsiadFm2810NBUBHlsrISey+3X20rXUgYYsjVPKWJWsTFFncv
 vqz7Ps79eQ+kPv6ng+yLrVdgo282CetH2vnWibnKqBp17MlZ8JvJD8QBV0C5Yzyf
 quWHr85PJ9bkHV8X7EeDECo0qjNwAGRpDPR92Ma6sryvvMbJPWn8wi+umTwDFZA0
 2tLtNH1bSWOQWwMEiwyNwLszae77HwBqSk98DreGrfO3Cqeml4w2Tgd2gg9AToXO
 NrB0iYJCL6wQaxUvqUG0
 =Ow22
 -----END PGP SIGNATURE-----
 

TableGen: Optimize super-register class computation (#134865)

Inferring super-register classes naively requires checking every
register class against every other register class and sub-register
index.
Each of those checks is itself a non-trivial operation on register sets.

Culling as many (RC, RC, SubIdx) triples as possible is important for
the running time of TableGen for architectures with complex sub-register
relations.

Use transitivity to cull many (RC, RC, SubIdx) triples. This
unfortunately requires us to complete the transitive closure of
super-register classes explicitly, but it still cuts down the running
time on AMDGPU substantially -- in some upcoming work in the
backend by more than half (in very rough measurements).

This changes the names of some of the inferred register classes, since
the order in which they are inferred changes. The names of the inferred
register classes become shorter, which reduces the size of the generated
files.

Replacing some uses of SmallPtrSet by DenseSet shaves off a few more
percent; there are hundreds of register classes in AMDGPU.

Tweaking the topological signature check to skip reigsters without
super-registers further helps skip register classes that have "pseudo"
registers in them whose sub- and super-register structure is trivial.