Fix PR45371: SeparateConstOffsetFromGEP clean up bookkeeping

[jroelofs]

Summary

find() was altering the UserChain, even in cases where it subsequently
discovered that the resulting constant was a 0. This confuses
rebuildWithoutConstOffset() when it attempts to walk the chain later, since it
is expected that the chain itself be a path down the use-def edges of an
expression.

[bjope]

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

580

Coding style: You may skip the braces here.

[ajwock]

LGTM, just give the test a good name.

llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371.ll

6 ↗

(On Diff #253962)

Can we have a name for this file and this function that's a little more self explanatory? If it weren't attached to this commit I would have no idea what's being tested.

[jroelofs]

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

580

Haven't seen (m)any braceless if's with a comment inside them. Happy to reword and drop them though.

llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371.ll

6 ↗

(On Diff #253962)

It's not uncommon to name tests after their corresponding bugzilla number:

$ find llvm/test/ -name "pr[0-9]*.ll" | wc -l
     791

Suggestions on a better function name?

[jroelofs]

implement review feedback

[uabelho]

Thanks! This indeed seem to solve the problem I saw.

[jroelofs]

https://github.com/llvm/llvm-project/commit/1148f004fa35f1b74942bb1f578763d9dd79aa4a

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
   //       1       |      0       | sext(BO) == sext(A) op sext(B)
   //       1       |      1       | zext(sext(BO)) ==
   //               |              |     zext(sext(A)) op zext(sext(B))
   if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) {
     // If a + b >= 0 and (a >= 0 or b >= 0), then
     //   sext(a + b) = sext(a) + sext(b)
     // even if the addition is not marked nsw.
     //
-    // Leveraging this invarient, we can trace into an sext'ed inbound GEP
+    // Leveraging this invariant, we can trace into an sext'ed inbound GEP
     // index if the constant offset is non-negative.
     //
     // Verified in @sext_add in split-gep.ll.
     if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) {
       if (!ConstLHS->isNegative())
         return true;
     }
     if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) {
bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
   }
 
   return true;
 }
 
 APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
                                                    bool SignExtended,
                                                    bool ZeroExtended) {
+  // Save off the current height of the chain, in case we need to restore it.
+  size_t ChainLength = UserChain.size();
+
   // BO being non-negative does not shed light on whether its operands are
   // non-negative. Clear the NonNegative flag here.
   APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended,
                               /* NonNegative */ false);
   // If we found a constant offset in the left operand, stop and return that.
   // This shortcut might cause us to miss opportunities of combining the
   // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9.
   // However, such cases are probably already handled by -instcombine,
   // given this pass runs after the standard optimizations.
   if (ConstantOffset != 0) return ConstantOffset;
+
+  // Reset the chain back to where it was when we started exploring this node,
+  // since visiting the LHS didn't pan out.
+  UserChain.resize(ChainLength);
+
   ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended,
                         /* NonNegative */ false);
   // If U is a sub operator, negate the constant offset found in the right
   // operand.
   if (BO->getOpcode() == Instruction::Sub)
     ConstantOffset = -ConstantOffset;
+
+  // If RHS wasn't a suitable candidate either, reset the chain again.
+  if (ConstantOffset == 0)
+    UserChain.resize(ChainLength);
+
   return ConstantOffset;
 }
 
 APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,
                                     bool ZeroExtended, bool NonNegative) {
   // TODO(jingyue): We could trace into integer/pointer casts, such as
   // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only
   // integers because it gives good enough results for our benchmarks.

llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371-find-either-reset.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -separate-const-offset-from-gep < %s | FileCheck %s
+
+@e = external global [4000 x i8], align 1
+
+define void @find_either_reset() {
+; CHECK-LABEL: @find_either_reset(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 65536, undef
+; CHECK-NEXT:    [[TMP0:%.*]] = trunc i32 [[SUB]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[TMP0]], 96
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i8 0 to i64
+; CHECK-NEXT:    [[IDXPROM1:%.*]] = sext i8 [[TMP1]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [4000 x i8], [4000 x i8]* @e, i64 [[IDXPROM]], i64 [[IDXPROM1]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %sub = sub nsw i32 65536, undef
+  %0 = trunc i32 %sub to i8
+  %1 = add i8 %0, -4000
+  %arrayidx = getelementptr inbounds [4000 x i8], [4000 x i8]* @e, i8 0, i8 %1
+  ret void
+}