diff --git a/llvm/include/llvm/Analysis/VectorUtils.h b/llvm/include/llvm/Analysis/VectorUtils.h
--- a/llvm/include/llvm/Analysis/VectorUtils.h
+++ b/llvm/include/llvm/Analysis/VectorUtils.h
@@ -19,6 +19,8 @@
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/CheckedArithmetic.h"
 
+#include <unordered_map>
+
 namespace llvm {
 
 template <typename T> class ArrayRef;
@@ -369,7 +371,9 @@
   uint32_t Factor; // Interleave Factor.
   bool Reverse;
   uint32_t Align;
-  DenseMap<int32_t, InstTy *> Members;
+  // We are using unordered_map instead of DenseMap to avoid limiting the key range
+  // by tombstone/empty key values.
+  std::unordered_map<int32_t, InstTy *> Members;
   int32_t SmallestKey = 0;
   int32_t LargestKey = 0;
 
diff --git a/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll b/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll
--- a/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll
+++ b/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll
@@ -38,3 +38,33 @@
 for.cond.cleanup:                                 ; preds = %for.body
   ret void
 }
+
+; Test from https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11638
+define void @test2() {
+; CHECK-LABEL: @test2
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %for.body
+
+; CHECK-LABEL: for.body:
+; CHECK: store i32
+; CHECK: store i32
+; CHECK-NOT: store
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 1, %entry ], [ %0, %for.body ]
+  %0 = add nsw i64 %indvars.iv, -1
+  %arrayidx = getelementptr inbounds [3 x i32], [3 x i32]* undef, i64 0, i64 %0
+  %G2 = getelementptr i32, i32* %arrayidx, i64 %0
+  %B = sub i32 -2147483648, -2147483648
+  %G9 = getelementptr i32, i32* %G2, i32 -2147483648
+  %G1 = getelementptr i32, i32* %arrayidx, i64 %0
+  store i32 %B, i32* %G1
+  store i32 %B, i32* %G9
+  br i1 false, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+}