[SeparateConstOffsetFromGEP] Fix: `b - a` matched `a - b` during reuniteExts

[Peakulorain]

Summary

During the SeparateConstOffsetFromGEP pass, a - b and b - a will be
considered equivalent in some instances.

An example- the IR contains:

BB1:
    %add = add %a, 511
    br label %BB2
BB2:
    %sub2 = sub %b,  %a
    br label %BB3
BB3:
    %sub1 = sub %add, %b
    %gep = getelementptr float, ptr %p, %sub1

Step 1 in the SeparateConstOffsetFromGEP pass, after split constant index:

BB1:
    %add = add %a, 511
    br label %BB2
BB2:
    %sub2 = sub %b,  %a
    br label %BB3
BB3:
    %sub.t = sub %a, %b
    %gep.base = getelementptr float, ptr %p, %sub.t
    %gep = getelementptr float, ptr %gep.base, 511

Step 2, after reuniteExts:

BB1:
    br label %BB2
BB2:
    %sub2 = sub %b,  %a
    br label %BB3
BB3:
    %gep.base = getelementptr float, ptr %p, %sub2
    %gep = getelementptr float, ptr %gep.base, 511

Obviously, reuniteExts treated a - b and b - a as equivalent.
This patch fixes that.

[Peakulorain]

We triggered this bug on the aarch64 target, since aarch64 has enabled LowerGEP.
Pls use command line in the case split-gep-sub.ll of my patch to trigger this problem.

[spatel]

Please upload with more context - use something like "git diff -U9999".

llvm/test/Transforms/SeparateConstOffsetFromGEP/AArch64/split-gep-sub.ll

1

It would be better to use a RUN line with opt like existing tests in this and the parent directory.
IIUC, we have a miscompile, so you can create a baseline test that shows the bug, commit that to main, and then regenerate the CHECK lines with this patch, so we show the difference in IR. Please use "utils/update_test_checks.py" to auto-generate the CHECK lines instead of manually writing them.

[Peakulorain]

In D143542#4123076, @spatel wrote:

Please upload with more context - use something like "git diff -U9999".

Your reply is appreciated. First step to show this miscompile, we should add a flag to enable LowerGEP manually.
So, see the first patch pls: https://reviews.llvm.org/D143980
I will update after the above patch is merged.

[Peakulorain]

In D143542#4123076, @spatel wrote:

Please upload with more context - use something like "git diff -U9999".

Thanks, uploaded again.

[nikic]

LGTM. Using SCEV expressions as a deduplication key seems kind of odd in the first place, but I guess for adds it does provide some value, because you get complexity canonicalization for free. Of course, for subs we don't want that, and this effectively prevents it.

llvm/test/Transforms/SeparateConstOffsetFromGEP/split-gep-sub.ll

4 ↗

(On Diff #497215)

Please include a comment on what this is testing, it's not particularly obvious.

[spatel]

More knowledgeable reviewers have approved, so just making it clear that there's no need to wait for more comments from me. :)

[Peakulorain]

In D143542#4125864, @spatel wrote:

More knowledgeable reviewers have approved, so just making it clear that there's no need to wait for more comments from me. :)

Also thanks a lot for your review. :)

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

     }
   } else if (match(I, m_Sub(m_SExt(m_Value(LHS)), m_SExt(m_Value(RHS))))) {
     if (LHS->getType() == RHS->getType()) {
-      const SCEV *Key =
-          SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
+      const SCEV *Key = SE->getAddExpr(
+          SE->getUnknown(LHS), SE->getNegativeSCEV(SE->getUnknown(RHS)));
       if (auto *Dom = findClosestMatchingDominator(Key, I, DominatingSubs)) {
         Instruction *NewSExt = new SExtInst(Dom, I->getType(), "", I);
         NewSExt->takeName(I);

     }
   } else if (match(I, m_NSWSub(m_Value(LHS), m_Value(RHS)))) {
     if (programUndefinedIfPoison(I)) {
-      const SCEV *Key =
-          SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
+      const SCEV *Key = SE->getAddExpr(
+          SE->getUnknown(LHS), SE->getNegativeSCEV(SE->getUnknown(RHS)));
       DominatingSubs[Key].push_back(I);
     }
   }

llvm/test/Transforms/SeparateConstOffsetFromGEP/AArch64/split-gep-sub.ll

+; RUN: llc --mtriple aarch64-unknown-linux -O3 -aarch64-enable-gep-opt \
+; RUN:   -start-before=separate-const-offset-from-gep \
+; RUN:   -print-after=separate-const-offset-from-gep < %s 2>&1 | FileCheck %s
+
+define void @test(ptr %p) {
+entry:
+  %0 = tail call i32 @foo()
+  %rem = srem i32 %0, 5
+  %add = add nsw i32 %rem , 511
+  br label %for.body
+
+for.body:
+  %k = phi i32 [ 0, %entry ], [ %inc, %cond.end ]
+  %mul = mul nuw nsw i32 %k, 5
+  %sub1 = sub nsw i32 %mul, %rem
+  %cmp26 = icmp ult i32 %sub1, 512
+  br i1 %cmp26, label %cond.true, label %cond.end
+
+cond.true:
+; CHECK-LABEL: cond.true:
+; CHECK-NEXT:   %1 = sext i32 %mul to i64
+; CHECK-NEXT:   %2 = sext i32 %rem to i64
+; CHECK-NEXT:   %sub22 = sub i64 %2, %1
+; CHECK-NOT:    %sub22 = sext i32 %sub1 to i64
+  %sub2 = sub nsw i32 %add, %mul
+  %idxprom = sext i32 %sub2 to i64
+  %arryidx = getelementptr inbounds float, ptr %p, i64 %idxprom
+  store float 1.0, ptr %arryidx, align 4
+  br label %cond.end
+
+cond.end:
+  %inc = add nuw nsw i32 %k, 1
+  %exitcond = icmp ne i32 %inc, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+declare i32 @foo()
 No newline at end of file