I believe the term for this is scalar evolution.
Yep! That is it alright.
Here's a talk from an llvm conference with the details.
That is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?
Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.
https://godbolt.org/z/so6neac33
So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.