performance regression in LoopStrengthReduce

Hi all,

I am investigating a performance (quality of code) regression that was introduced on June 2, 2016
(See https://llvm.org/bugs/show_bug.cgi?id=31629 )

The change on its own just cleans up phi nodes that were introduced by LCSSA (instructionSimplifierPass).
This cleanup allows IVUsers and LoopStrengthReduce to come up with more complex SCEV expressions, but it seems that LoopStrengthReduce
is in certain cases allowing too complex expressions to survive, resulting in more variables staying alive in the loop body and more
complex computations being done outside the loop body.

As SCEV became smarter since that change, the expressions that it allowed also became more complex.
The end result is that the issue was introduced in 3.9 and will be worse in 4.0

I am trying to find out the right place to fix this, but I am not sure if it should be fixed in IVUsers or in LoopStrengthReduce (or maybe somewhere else).

Greetings,

Jeroen Dobbelaere