How LLVM optimizes power sums (2019)

Resubmitting because https://xania.org/202512/24-cunning-clang was submitted recently. I remember my friend sent me the power sums article about a year ago and I think others might find it to be an interesting followup.

I verified the theory that this stuff is based on in the Rocq proof assistant, so you can read the proofs and algorithms of how this stuff works (http://github.com/bollu/scev-coq). It's based on an old but cool paper called "chains on recurrences" https://dl.acm.org/citation.cfm?id=269286, and was broadened quite a bit by Sebastian Pop in his PhD thesis