LazyValueInfo::getConstantRangeAtUse returns incorrect range for shift instruction

[d-makogon]

Reproducer: https://godbolt.org/z/ez4xncxs8
Recently CorrelatedValuePropagation pass started using LVI::getConstantRangeAtUse which is expected to return more precise result than the previously used LVI::getConstantRange. This was introduced in 5c38c6a by @nikic.
With this patch applied, I get a miscompilation on the above reproducer.
Unfortunately, alive2 was unable to prove that this is a miscompilation.

So I'll explain here why the transform perfomed is incorrect. So in the test function we have a loop which takes backedge exactly one time.
It executes ashr %iv, %arg on 1st iteration, so it actually is ashr 127, %arg. Let's assume that the %arg value is 1. Then %shift is equal to 63. The second time we enter the loop block, shifted.iv would be equal to shift which is 63. Then we'd have %iv equal to 128 and %loop_cond would be false, so we'd branch to exit and return retval which is equal to shifted.iv which is 63.

In the IR after CVP pass, we replace the shifted.iv input which was shift with its first operand (which is iv) and erases the shift instruction. Now let's analyze the return value of the function - it would still be shifted.iv, but it would be equal to 128 because no shift would be done.

So we get a different return value from the function.

The faulting transform is made in the following piece of code in CorrelatedValuePropagation.cpp:

static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
  ...
  ConstantRange LRange = LVI->getConstantRangeAtUse(SDI->getOperandUse(0));
  unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
  ConstantRange NegOneOrZero =
      ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
  if (NegOneOrZero.contains(LRange)) {
    // ashr of -1 or 0 never changes the value, so drop the whole instruction
    ++NumAShrsRemoved;
    SDI->replaceAllUsesWith(SDI->getOperand(0));
    SDI->eraseFromParent();
    return true;
  }

So it calculates the range of the first operand of the shift, which is iv, using LVI::getConstantRangeAtUse. And this function returns empty-set for iv and this is incorrect. Then we check whether [-1, 1) contains the operand range which is empty and we obviously get a positive result and thus erase the shift.

So I tried debugging LVI::getConstantRangeAtUse, but couldn't quickly figure out how to solve it.
Here is what I got:

1. When called on iv use in shift, it calls LVI::getConstantRange which returns [-2147483648,128).
2. It traverses transitive uses of the value and tries to infer more precise range based on where the value is used. In the example we only have PHI users of the value, for which we call getEdgeValueLocal to get the value range on the edge from loop block to exit and it returns [128,-2147483648).
3. It then intersects [-2147483648,128) with [128,-2147483648) and this is why we get empty set.

[d-makogon]

@nikic could you please take a look? Seems like your patches (4f772b0 and 5c38c6a) cause a miscompilation.

[nikic]

Thanks for the report. I think the problem here is that we're effectively reasoning about values from different loop iteration, and the proper fix for this is probably to not look through phi nodes (i.e. use condition from the first encountered phi, but don't traverse past it).

I'm currently on PTO, so I'll only be able to look into this next Tuesday. If you need a quick fix for this, I'd suggest landing a change to set

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

Line 1665 in 0cabe38

const unsigned MaxUsesToInspect = 3;

to zero to disable the transform. That would be easier than a revert, as there are many commits involved here.

[d-makogon]

Thanks for the quick response @nikic!
I landed your suggested fix in c77c186. Also committed a test that checks that a shift is not removed - https://github.com/llvm/llvm-project/blob/main/llvm/test/Analysis/LazyValueAnalysis/pr60629.ll.

[nikic]

I've landed bfbfbd8 to fix the problem and re-enable the transform.

Keeping this open for 16.x backport.

[nikic]

I've combined the three relevant patches into one for the backport, as it's hard to understand what is actually being changed otherwise, with the diffs going back and forth. This should make it clear that only the position of the isSafeToSpeculativelyExecute() check actually changes here.

/branch nikic/llvm-project/lvi-fix-backport

[llvmbot]

/pull-request llvm/llvm-project-release-prs#301