[ScalarEvolution] Enhance Predicate implication from condition

[TiehuZhang]

Summary

We can prove the scenario:

FoundLHS > FoundRHS =>
LHS = (FoundLHS + Offset) > RHS = (FoundRHS + Offset)

Or

FoundLHS < FoundRHS =>
LHS = (FoundLHS + Offset) < RHS = (FoundRHS + Offset)

This patch enhance isImpliedCondBalancedTypes with the formula.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11768

This is incorrect in case of overflow. See isKnownPredicateViaNoOverflow.

[mkazantsev]

llvm/test/Transforms/HardwareLoops/ARM/simple-do.ll

151

This is miscompile, see https://alive2.llvm.org/ce/z/ESPqU_

[TiehuZhang]

llvm/lib/Analysis/ScalarEvolution.cpp

11768

This is incorrect in case of overflow. See isKnownPredicateViaNoOverflow.

llvm/test/Transforms/HardwareLoops/ARM/simple-do.ll

151

Thanks for your review! https://alive2.llvm.org/ is really a useful tool. Sometimes, it is helpful for the performance to simplify -1,+,(-1 * %max_row_length)}<nw><%for.cond1.preheader> + ({1,+,%max_row_length}<nw><%for.cond1.preheader> smax {%max_row_length,+,%max_row_length}<nw><%for.cond1.preheader> to -1 + %max_row_length . For most cases, smax is redundant, and may hurt performance. But if overflow is considered, this check is indispensable. I'll try to restrict the condition of the patch to ensure the correctness. For the scenario, do you have any suggestions?