Value Range: clang cannot know `(a >> 3 == -2)` means `a` in [ -16, -9]

[k-arrows]

Test case:
https://godbolt.org/z/daYcYhxad

bool foo(int a)
{
  if ((a >> 3) + 2 == 0) return true;
  else return (a < -16 || a > -9);
}

Some generalizations will be necessary, but this is motivated from the following gcc testsuite:
https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.dg/tree-ssa/vrp76.c

Clang13 can optimize the above function foo, but it cannot the original f3. Therefore, there may be problems that differ from the value range. Sorry if my example is inappropriate.

[antoniofrighetto]

@dtcxzyw Could this in principle be solved in LVI/CVP?

[antoniofrighetto]

Uhmm, I think it's a matter of reassociating an expression in EarlyCSE.

[antoniofrighetto]

@nikic Starting from bb12ded, or of icmps get folded into icmp ult of add, whereas previously that was being folded into icmp ne of ands. The above example shows it a bit clearer.
Before:

 if.else:                                          ; preds = %entry
-  %cmp1 = icmp slt i32 %a, -16
-  %cmp2 = icmp sgt i32 %a, -9
-  %0 = select i1 %cmp1, i1 true, i1 %cmp2
+  %0 = and i32 %a, -8
+  %1 = icmp ne i32 %0, -16
br label %return

After:

 if.else:                                          ; preds = %entry
-  %cmp1 = icmp slt i32 %a, -16
-  %cmp2 = icmp sgt i32 %a, -9
-  %0 = select i1 %cmp1, i1 true, i1 %cmp2
+  %0 = add i32 %a, 8
+  %1 = icmp ult i32 %0, -8
br label %return

The commit change looks robust to me, does it sound reasonable in your opinion to let EarlyCSE catch up with InstructionCombining latest canonicalization?

[nikic]

@antoniofrighetto What do you mean by "let EarlyCSE catch up with InstructionCombining latest canonicalization"? I don't understand what EarlyCSE has to do with this.

From what you said, it sounds like there is a missing canonicalization between the and+icmp and add+icmp forms (in some direction).

[antoniofrighetto]

From what you said, it sounds like there is a missing canonicalization between the and+icmp and add+icmp forms (in some direction).

Ugh, the IR emitted by clang-13 had a redundant instruction (indeed the and) eliminated by EarlyCSE which led InstCombine again to simplify everything, but I stand corrected, as in the latest one there's really nothing to CSE. There is definitely a missing canonicalization towards and+icmp, let me open a patch for it...