[committed] Patches 8-12 of Mariam & Matevos's CRC optimization work

[Jeff Law]

[ Resent with compressed patches to get undre the 400k limit. ]











The fourth patch actually replaces a CRC loop with an IFN.







Thanks Mariam & Matevos!

Jeff

This is the bulk of Mariam's & Matevos's work on CRC optimization. It covers detection, validation and final transformation of a bitwise CRC loop into an IFN. Once in IFN form the expansion code from earlier this week can expand it into a table lookup, carryless multiply sequence or a CRC instruction. I've spot checked each of patches in this push to verify that the tree remains bisectable at each point and made one trivial adjustment as result. The first patch identifies loops that may compute a CRC; it does a series of relatively inexpensive tests to identify candidate loops based on the operations inside the loop. The second patch introduces a symbolic execution engine that can do bitwise tracking of state. We use this capability to verify that a candidate loop is actually a CRC computation. The third patch adds code to use the symbolic execution engine to validate that a candidate loop is a CRC computation suitable for optimization into a table lookup, carryless multiply sequence or CRC instruction. The fifth patch is the generic bits of the testsuite. This includes a combination of tests which are and are not CRC computations. It includes some dump scanning tests as well as execution tests. With the exception of two dump scanning tests (which fail due to early IL differences on some embedded targets), the tests should be working consistently on all our platforms. As I mentioned, I've tested these patches one at a time to ensure trunk bisectability in my tester. They've also been bootstrapped and regression tested on x86_64. There's still some risc-v tests to add now that the main bits are in. And there's aarch64 & x86 bits to take care of as well. But the major work is committed. I'll let any dust settle before I take care of these final items.

P1.gz
Description: application/gzip

P2.gz
Description: application/gzip

P3.gz
Description: application/gzip

P5.gz
Description: application/gzip

P4.gz
Description: application/gzip