[GVN] If zext X == N or sext X == N, then X == trunc N.

[wecing]

Summary

As discussed in https://reviews.llvm.org/D93850, this seems to be a bug
of GVN.

[wecing]

I am very confused why NewGVN doesn't seem to propagate switch condition values: https://godbolt.org/z/9a9P51. Some guidance on porting this to NewGVN would be appreciated!

[nikic]

I'm not convinced that GVN is really the right place to address this, because it is not the only place that would have to understand this pattern. For example LVI does the inverse reasoning (X == C to zext X == zext C), but not this one. For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

The InstCombine patch that moves the zext into the switch seems like the more promising direction to me. Generally, if we have switch (f(x)) case C it makes sense to convert it to switch (x) case f^{-1}(C) for invertible f.

[wecing]

For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

[lebedev.ri]

In D93888#2483368, @wecing wrote:

For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

I'm not yet convinced we can do this in instcombine,
because why can we do this without a profitability check,
like the fold just below that one does?

[nikic]

In D93888#2483368, @wecing wrote:

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

Handling it in NewGVN and IPSCCP requires handling it in PredicateInfo, by introducing new SSA variables and performing SSA renaming in relevant branches not just for comparison operands, but also for operands-of-operands. That is, for br icmp (zext X), C we currently introduce up to two new variables for (zext X) and rename to them in the relevant branch. Handling the pattern here would require introducing a new variable for X as well. Of course it's possible to do this, but, but it leads to a collection of special cases rather than a principled approach. Especially as we have to deal with this in multiple passes, it's better to avoid it if we can.

In D93888#2483911, @lebedev.ri wrote:

I'm not yet convinced we can do this in instcombine,
because why can we do this without a profitability check,
like the fold just below that one does?

The profitability check is there to avoid creating illegal types that did not exist in the original IR. If we are simply dropping a zext, we're using a type that already existed in the IR, and would generally consider that to be fine. We could be even more conservative and require the zext-ed from type to be legal (doesn't make much diff in practice). Dropping a zext i32 to i64 to switch over an i32 is quite different from inserting a trunc to i3 and switching over i3. The former seems like an unambiguous improvement, while the latter will regress more likely than not.

[wecing]

@lebedev.ri do you think we could go with D93850?

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Scalar/GVN.cpp

if (!LHS->hasOneUse()) {
 
       Changed |= NumReplacements > 0;
       NumGVNEqProp += NumReplacements;
       // Cached information for anything that uses LHS will be invalid.
       if (MD)
         MD->invalidateCachedPointerInfo(LHS);
     }
 
+    // If (zext X) == N or (sext X) == N, then X == (trunc N).
+    Value *X;
+    if (match(LHS, m_ZExtOrSExt(m_Value(X)))) {
+      unsigned Width = X->getType()->getIntegerBitWidth();
+      ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
+      if (CI) {
+        Value *NewRHS =
+            ConstantInt::get(IntegerType::get(X->getContext(), Width),
+                             CI->getValue().trunc(Width));
+        Worklist.push_back(std::make_pair(X, NewRHS));
+        continue;
+      }
+    }
+
     // Now try to deduce additional equalities from this one. For example, if
     // the known equality was "(A != B)" == "false" then it follows that A and B
     // are equal in the scope. Only boolean equalities with an explicit true or
     // false RHS are currently supported.
     if (!RHS->getType()->isIntegerTy(1))
       // Not a boolean equality - bail out.
       continue;
     ConstantInt *CI = dyn_cast<ConstantInt>(RHS);

llvm/test/Transforms/GVN/zext-eq-const-int.ll

+; RUN: opt -gvn -S < %s | FileCheck %s
+
+define i32 @zext-eq-const-int(i32 %x) {
+; CHECK-LABEL: @zext-eq-const-int(
+; CHECK:       bb9:
+; CHECK-NEXT:    br i1 true, label %t
+;
+entry:
+  %_x = zext i32 %x to i64
+  switch i64 %_x, label %bb.end [
+    i64 3, label %bb9
+  ]
+
+bb9:
+  %cond = icmp eq i32 %x, 3
+  br i1 %cond, label %t, label %bb.end
+
+t:
+  ret i32 42
+
+bb.end:
+  ret i32 9999
+}
+
+define i32 @sext-eq-const-int(i32 %x) {
+; CHECK-LABEL: @sext-eq-const-int(
+; CHECK:       bb9:
+; CHECK-NEXT:    br i1 true, label %t
+;
+entry:
+  %_x = sext i32 %x to i64
+  switch i64 %_x, label %bb.end [
+    i64 4294967299, label %bb9 ; 0x1_0000_0003
+  ]
+
+bb9:
+  %cond = icmp eq i32 %x, 3
+  br i1 %cond, label %t, label %bb.end
+
+t:
+  ret i32 42
+
+bb.end:
+  ret i32 9999
+}