[SCEV] Fix FoldID::addInteger(unsigned long I)

[vitalybuka]

Summary

"unsigned long" can be 8 bytes, but the code assumes 4.

This this the real root cause D122215 was reverted.

[fhahn]

LGTM, thanks for tracking this down!

[nikic]

Looks like this had a fairly significant compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=c23f29d6f05b1fe4fa2dd50cbb78ee2b30e0de4d&to=a53d940cee6f281ef1a20d4f0fb39b23b4e98614&stat=instructions:u

I think the current uses of FoldID will now have 5 elements and as such overflow SmallVector space, each resulting in a vector allocation?

It's not great that this change was backported without approval, bypassing the required backport process, immediately after landing the change on main, without even waiting for any fallout :(

[vitalybuka]

As is it's a really land mine, it's cut off half of the pointer in the key, and can affect correctness anything that uses SCEV

Regarding perf, I have improved patch, which I planed to send for review, but not to backport:
https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions%3Au&remote=vitalybuka

We can backport both of them, to be incremental:

1. correctness
2. perf

In D144316#4137232, @nikic wrote:

Looks like this had a fairly significant compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=c23f29d6f05b1fe4fa2dd50cbb78ee2b30e0de4d&to=a53d940cee6f281ef1a20d4f0fb39b23b4e98614&stat=instructions:u

I think the current uses of FoldID will now have 5 elements and as such overflow SmallVector space, each resulting in a vector allocation?

It's not great that this change was backported without approval, bypassing the required backport process, immediately after landing the change on main, without even waiting for any fallout :(

[fhahn]

In D144316#4137232, @nikic wrote:

Looks like this had a fairly significant compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=c23f29d6f05b1fe4fa2dd50cbb78ee2b30e0de4d&to=a53d940cee6f281ef1a20d4f0fb39b23b4e98614&stat=instructions:u

I think the current uses of FoldID will now have 5 elements and as such overflow SmallVector space, each resulting in a vector allocation?

Yeah looks like it. It looks like extending the size of the Bits vector should recover the regression while still retaining support for arbitrary SCEV expressions, which was the main reason for the current FoldID implementation.

[MaskRay]

llvm/include/llvm/Analysis/ScalarEvolution.h

1309

This can be replaced with a static_assert, but the point is moot now that you are going to remove this piece of code.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Return true if this loop is finite by assumption.  That is,
   /// to be infinite, it must also be undefined.
   bool loopIsFiniteByAssumption(const Loop *L);
 
   class FoldID {
     SmallVector<unsigned, 4> Bits;
 
   public:
-    void addInteger(unsigned long I) { Bits.push_back(I); }
+    void addInteger(unsigned long I) {
+      if (sizeof(long) == sizeof(int))
+        addInteger(unsigned(I));
+      else if (sizeof(long) == sizeof(long long))
+        addInteger((unsigned long long)I);
+      else
+        llvm_unreachable("unexpected sizeof(long)");
+    }
     void addInteger(unsigned I) { Bits.push_back(I); }
     void addInteger(int I) { Bits.push_back(I); }
 
     void addInteger(unsigned long long I) {
       addInteger(unsigned(I));
       addInteger(unsigned(I >> 32));
     }