[SeparateConstOffsetFromGEP] Fix bug handling negative offsets

[tstellar]

Summary

Fix bug constants and sub instructions

When finding constants in a chain starting with the RHS operator of
sub instructions, we were negating the constant before zero extending
it, which is incorrect.

Unfortunately, I was unable to find a simple way to implement this
transformation correctly, so for now I just disabled this optimization
for constants that feed into the RHS of a sub.

Resolves #62379

Transformation from alive2.llvm.org:

define i16 @src(i8 %a, i8 %b, i8 %c) {
entry:
%0 = sub nuw nsw i8 %c, %a
%1 = sub nuw nsw i8 %b, %0
%2 = zext i8 %1 to i16
ret i16 %2
}

Before/Bad:

define i16 @tgt(i8 %a, i8 %b, i8 %c) {
entry:
%0 = zext i8 %a to i16
%1 = zext i8 %b to i16
%c_neg = sub i8 0, %c
%c_zext = zext i8 %c_neg to i16
%2 = sub i16 0, %0
%3 = sub i16 %1, %2
%4 = add i16 %3, %c_zext
ret i16 %4
}

Correct:

define i16 @tgt(i8 %a, i8 %b, i8 %c) {
entry:
%0 = zext i8 %a to i16
%1 = zext i8 %b to i16
%c_zext = zext i8 %c to i16
%c_neg = sub i16 0, %c_zext
%2 = sub i16 0, %0
%3 = sub i16 %1, %2
%4 = add i16 %3, %c_neg
ret i16 %4
}

[nikic]

Haven't looked at the code change yet, but I'm pretty sure the test can use -passes='separate-const-offset-from-gep<lower-gep>' instead of adding a new opt flag.

[Peakulorain]

Transforming zext(A op B) to zext(A) op zext(B) should guarantee that A and B are non-negative. I think it would be better to do this fix during ConstantOffsetExtractor::CanTraceInto.

[tstellar]

In D149507#4307404, @Peakulorain wrote:

Transforming zext(A op B) to zext(A) op zext(B) should guarantee that A and B are non-negative. I think it would be better to do this fix during ConstantOffsetExtractor::CanTraceInto.

The problem I'm running into is that it's very difficult to to prove a value is non-negative, so adding those kinds of checks into CanTraceInto more or less disables the pass. The pass also makes an incorrect assumption that operands to an inbounds GEP are always non-negative. And it's not just assuming that direct operands to inbounds GEPS are non-negative, it assumes that any operands in the tree of values feeding into the GEP are non-negative.

[tstellar]

With some help from @nikic, I discovered that the bug is much more narrow in scope than I thought initially, so I should be able to do a more targeted fix.

[tstellar]

Use a more targetted fix.

[nikic]

This looks reasonable to me, but maybe wait a bit in case @Peakulorain has a better suggestion.

https://github.com/llvm/llvm-project/blob/1d0ccebcd725309399262af346494242b064e2ed/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp#L590-L593 is the code negating the offset.

[Peakulorain]

Since more knowledgeable people gived professional advice, it is also ok for me. :)

[tstellar]

Delete now dead code that was negating the constant.

[tstellar]

In D149507#4312067, @nikic wrote:

This looks reasonable to me, but maybe wait a bit in case @Peakulorain has a better suggestion.

https://github.com/llvm/llvm-project/blob/1d0ccebcd725309399262af346494242b064e2ed/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp#L590-L593 is the code negating the offset.

I actually meant to delete that code in this patch, so I've updated the patch to take it out.

[nikic]

In D149507#4312220, @tstellar wrote:

In D149507#4312067, @nikic wrote:

This looks reasonable to me, but maybe wait a bit in case @Peakulorain has a better suggestion.

https://github.com/llvm/llvm-project/blob/1d0ccebcd725309399262af346494242b064e2ed/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp#L590-L593 is the code negating the offset.

I actually meant to delete that code in this patch, so I've updated the patch to take it out.

Hm, why is it safe to delete that code? Don't we still need it in the case where we have no extension or a sign extension?

[tstellar]

Add back negation code.

[tstellar]

In D149507#4312221, @nikic wrote:

In D149507#4312220, @tstellar wrote:

In D149507#4312067, @nikic wrote:

This looks reasonable to me, but maybe wait a bit in case @Peakulorain has a better suggestion.

https://github.com/llvm/llvm-project/blob/1d0ccebcd725309399262af346494242b064e2ed/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp#L590-L593 is the code negating the offset.

I actually meant to delete that code in this patch, so I've updated the patch to take it out.

Hm, why is it safe to delete that code? Don't we still need it in the case where we have no extension or a sign extension?

Yes, I've added it back.

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
   // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS
   // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS).
   // FIXME: this does not appear to be covered by any tests
   //        (with x86/aarch64 backends at least)
   if (BO->getOpcode() == Instruction::Or &&
       !haveNoCommonBitsSet(LHS, RHS, DL, nullptr, BO, DT))
     return false;
 
+  // FIXME: We don't currently support constants from the RHS of subs,
+  // when we are zero-extended, because we need a way to zero-extended
+  // them before they are negated.
+  if (ZeroExtended && !SignExtended && BO->getOpcode() == Instruction::Sub)
+    return false;
+
   // In addition, tracing into BO requires that its surrounding s/zext (if
   // any) is distributable to both operands.
   //
   // Suppose BO = A op B.
   //  SignExtended | ZeroExtended | Distributable?
   // --------------+--------------+----------------------------------
   //       0       |      0       | true because no s/zext exists
   //       0       |      1       | zext(BO) == zext(A) op zext(B)

llvm/test/Transforms/SeparateConstOffsetFromGEP/pr62379-zeroext-negative.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -S '-passes=separate-const-offset-from-gep<lower-gep>' < %s | FileCheck %s
+
+; These tests check that this pass does not incorrectly handle negative offsets.
+
+@c = internal constant [4 x i32] [i32 0, i32 1, i32 2, i32 3]
+
+; FIXME: We could optimize this case, but we don't currently.  This test just
+; checks that we don't miscompile it.
+define i32 @sub_positive(i32 %a, i32 %b, ptr %ptr) {
+; CHECK-LABEL: define i32 @sub_positive
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], ptr [[PTR:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw nsw i32 15, [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub nuw nsw i32 [[B]], [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [4 x i32], ptr [[PTR]], i64 0, i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr [[TMP3]], align 4
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+entry:
+  %0 = sub nuw nsw i32 15, %a
+  %1 = sub nuw nsw i32 %b, %0
+  %2 = zext i32 %1 to i64
+  %3 = getelementptr inbounds [4 x i32], ptr %ptr, i64 0, i64 %2
+  %4 = load i32, ptr %3
+  ret i32 %4
+}