[LVI] Suboptimal evaluation order

[nikic]

Consider this example:

define i1 @test(i32 %x) {
  %a = add nuw nsw i32 %x, 1
  %b = add nuw nsw i32 %a, 1
  %c = add nuw nsw i32 %a, %b
  %d = icmp ugt i32 %c, 2
  ret i1 %d
}

The comparison can be folded to true, but -passes=correlated-propagation fails to do so. The relevant LVI log looks like this:

LVI Getting block end value   %c = add nuw nsw i32 %a, %b at ''
PUSH:   %c = add nuw nsw i32 %a, %b in 
PUSH:   %a = add nuw nsw i32 %x, 1 in 
PUSH:   %b = add nuw nsw i32 %a, 1 in 
POP   %b = add nuw nsw i32 %a, 1 in  = constantrange<1, 0>
PUSH: i32 %x in 
POP i32 %x in  = overdefined
POP   %a = add nuw nsw i32 %x, 1 in  = constantrange<1, 0>
POP   %c = add nuw nsw i32 %a, %b in  = constantrange<2, 0>
  Result = constantrange<2, 0>

Notably, the values get pushed in the order %c, %a, %b, which means that %b gets evaluated before %a. But %b depends on %a, so it will use an overdefined value, rather than the more precise range we later compute.

We can get it to fold by slightly varying the input like this:

define i1 @test(i32 %x) {
  %a = add nuw nsw i32 %x, 1
  %b = add nuw i32 %a, 1
  %c = add nuw nsw i32 %a, %b
  %d = icmp ugt i32 %c, 2 
  ret i1 %d
}

Removing the nsw flag makes CVP issue a query for %a earlier, avoiding the problem.

[nikic]

Ah, I think this problem is simpler than I initially thought. We should be able to fix it by not pushing both values at the same time in

llvm-project/llvm/lib/Analysis/LazyValueInfo.cpp

Lines 978 to 979 in 734ee0e

	std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
	std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);