[JumpThreading] Incorrect elimination of condition

[nikic]

The following test case is miscomiled by JumpThreading (https://llvm.godbolt.org/z/o9W6efoTf):

define i64 @test(i64 noundef %v) {
entry:
  %v.nonneg = icmp sgt i64 %v, -1
  br label %for.body

for.body:
  %sum = phi i64 [ 0, %entry ], [ %sum.next, %for.body ]
  %sum.next = add i64 %sum, %v
  %overflow = icmp ult i64 %sum.next, %sum
  %cmp.i5.i = xor i1 %v.nonneg, %overflow
  br i1 %cmp.i5.i, label %for.body, label %cleanup1.loopexit

cleanup1.loopexit:
  %cmp.not.lcssa.ph = phi i64 [ %sum, %for.body ]
  ret i64 %cmp.not.lcssa.ph
}

The %overflow condition is folded to false as part of processBranchOnXOR().

I believe the root cause is that computeValueKnownInPredecessorsImpl() performs phi translation of one icmp operand (the phi node), while leaving the other alone, and then trying to simplify it. This means that we are working on icmp operands from two different loop iterations.

[nikic]

On the surface, the fix here is as simple as adding a !LoopHeaders.contains(BB) check. However, LoopHeaders is currently only used for heuristics, not correctness, and there is an option to disable it's population.

[nikic]

As this is actively causing issues, let's start with the simple part of the fix: #70664