diff --git a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
--- a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
+++ b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
@@ -522,7 +522,7 @@
     //   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.
@@ -552,6 +552,9 @@
 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,
@@ -562,12 +565,22 @@
   // 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;
 }
 
diff --git a/llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371-find-either-reset.ll b/llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371-find-either-reset.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/SeparateConstOffsetFromGEP/pr45371-find-either-reset.ll
@@ -0,0 +1,23 @@
+; 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
+}