The CRC optimization relies on stripping the auxiliary data completely, and should hence be forbidden when it has a user in the exit-block. Forbid this case, fixing a miscompile. Fixes #165382.
```
/home/david.spickett/llvm-project/llvm/lib/Analysis/HashRecognize.cpp:100:54: warning: comparison of integers of different signs:
'typename iterator_traits<ilist_iterator_w_bits<node_options<Instruction, true, false, void, true, BasicBlock>, false, false>>::difference_type' (aka 'int') and 'size_type' (aka 'unsigned int') [-Wsign-compare]
100 | return std::distance(Latch->begin(), Latch->end()) != Visited.size();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~~~~~~
```
By using Latch->size() instead.
Unify explanation for GF(2^n) and GF(2), which was previously convoluted.
Checking if trip-count exceeds 256 is no longer necessary, as we have moved away from KnownBits computations to pattern-matching, which is very cheap and independent of TC.
The ValueEvolution logic is deeply flawed, and checking that zero-bits are shifted can be exploited for miscompiles. In an effort to redo HashRecognize with a pattern-matching based approach, extract and fix the core logic of ValueEvolution, and strip it completely, showing that none of the tests rely on the KnownBits computation of ValueEvolution. Co-authored-by: Piotr Fusik <p.fusik@samsung.com>
Require that all Instructions in the Loop are visited by ValueEvolution, as any stray instructions would complicate life for the optimization.
The trip-count of a CRC algorithm can legitimately be greater than the bitwidth of the result: what it cannot exceed is the bitwidth of the data, or LHSAux. crc8.le.tc16 is now successfully recognized as a CRC algorithm.
The test crc8.le.tc16 is a valid CRC algorithm, but isn't recognized as such due to a buggy arePHIsIntertwined, which is asymmetric in its PHINode arguments. There is also a fundamental correctness issue: the core functionality is to match a XOR that's a recurrence in both PHI nodes, ignoring casts, but the user of the XOR is never checked. Rewrite and rename the function. crc8.le.tc16 is still not recognized as a valid CRC algorithm, due to an incorrect check for loop iterations exceeding the bitwidth of the result: in reality, it should not exceed the bitwidth of LHSAux, but we leave this fix to a follow-up. Co-authored-by: Piotr Fusik <p.fusik@samsung.com>
Make HashRecognize a non-PassManager analysis that can be called to get the result on-demand, creating a new getResult() entry-point. The issue was discovered when attempting to use the analysis to perform a transform in LoopIdiomRecognize.