clang cannot optimize fraction `(c * a / b)` when c is a power of 2 under the condition that other fraction `(a / d)` implies

[k-arrows]

Consider the following functions. https://godbolt.org/z/KxdWKofjd

int test2(int a) {
  if (a / 5)
    return 0;
  else
    return (2 * a / 9);
}

int test3(int a) {
  if (a / 5)
    return 0;
  else
    return (3 * a / 13);
}

int test4(int a) {
  if (a / 5)
    return 0;
  else
    return (4 * a / 17);
}

int test5(int a) {
  if (a / 5)
    return 0;
  else
    return (5 * a / 21);
}

int test6(int a) {
  if (a / 5)
    return 0;
  else
    return (6 * a / 25);
}

int test7(int a) {
  if (a / 5)
    return 0;
  else
    return (7 * a / 29);
}

int test8(int a) {
  if (a / 5)
    return 0;
  else
    return (8 * a / 33);
}

All of these functions can be optimized (to the function which returns zero), but Clang cannot optimize test2, test4, and test8.

[nikic]

I think the problem here is that the shl range calculation is not sufficiently accurate if the LHS can be negative: https://llvm.godbolt.org/z/afEec9q6K

POP i32 %arg in if = constantrange<-4, 5>
  Result = constantrange<-4, 5>
[...]
POP   %shl = shl nsw i32 %arg, 1 in if = constantrange<0, -1>
  Result = constantrange<0, -1>

We're probably using this fallback case: https://github.com/llvm/llvm-project/blob/1ffcac1b077afecff4b57b2ceec73c9bcb847389/llvm/lib/IR/ConstantRange.cpp#L1489C13-L1489C13