From 83aa93e99542dbbfc5223130482ad6d7744d9a78 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Mon, 18 Jan 2021 10:34:21 +0000
Subject: [PATCH] [VectorUtils] Do not try to add indices matching
 tombstone/empty values.

Keys matching the tombstone/empty special values cannot be inserted in a
DenseMap. Under some circumstances, LV tries to add members to an
interleave group that match the special values. Skip adding such
members. This is unlikely to have any impact in practice, because
interleave groups with such indices are very likely to not be
vectorized, due to gaps.

This issue has been surfaced by fuzzing, see
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11638
---
 llvm/include/llvm/Analysis/VectorUtils.h           |  5 ++
 .../X86/interleaved-accesses-large-gap.ll          | 60 ++++++++++++++++++++++
 2 files changed, 65 insertions(+)

diff --git a/llvm/include/llvm/Analysis/VectorUtils.h b/llvm/include/llvm/Analysis/VectorUtils.h
index d8fb970..ce3cb22 100644
--- a/llvm/include/llvm/Analysis/VectorUtils.h
+++ b/llvm/include/llvm/Analysis/VectorUtils.h
@@ -620,6 +620,11 @@ public:
       return false;
     int32_t Key = *MaybeKey;
 
+    // Skip if the key is used for either the tombstone or empty special values.
+    if (DenseMapInfo<int32_t>::getTombstoneKey() == Key ||
+        DenseMapInfo<int32_t>::getEmptyKey() == Key)
+      return false;
+
     // Skip if there is already a member with the same index.
     if (Members.find(Key) != Members.end())
       return false;
diff --git a/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll b/llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll
index 15ec344..b1d56e3 100644
--- 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,63 @@ for.body:                                         ; preds = %for.body, %entry
 for.cond.cleanup:                                 ; preds = %for.body
   ret void
 }
+
+; Make sure interleave groups with a key being the special 'empty' value for
+; the map do not cause a crash.
+define void @test_gap_empty_key() {
+; CHECK-LABEL: @test_gap_empty_key()
+; 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:
+  %iv = phi i64 [ 1, %entry ], [ %iv.next, %for.body ]
+  %iv.next = add nsw i64 %iv, 1
+  %arrayidx = getelementptr inbounds [3 x i32], [3 x i32]* undef, i64 0, i64 %iv.next
+  %G2 = getelementptr i32, i32* %arrayidx, i64 %iv.next
+  %G9 = getelementptr i32, i32* %G2, i32 -2147483647
+  store i32 0, i32* %G2
+  store i32 1, i32* %G9
+  %cmp = icmp ule i64 %iv, 1000
+  br i1 false, label %for.body, label %exit
+
+exit:
+  ret void
+}
+
+; Make sure interleave groups with a key being the special 'tombstone' value for
+; the map do not cause a crash.
+define void @test_tombstone_key() {
+; CHECK-LABEL: @test_tombstone_key()
+; 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:
+  %iv = phi i64 [ 1, %entry ], [ %iv.next, %for.body ]
+  %iv.next = add nsw i64 %iv, 1
+  %arrayidx = getelementptr inbounds [3 x i32], [3 x i32]* undef, i64 0, i64 %iv.next
+  %G2 = getelementptr i32, i32* %arrayidx, i64 %iv.next
+  %G9 = getelementptr i32, i32* %G2, i32 -2147483648
+  store i32 0, i32* %G2
+  store i32 1, i32* %G9
+  %cmp = icmp ule i64 %iv, 1000
+  br i1 false, label %for.body, label %exit
+
+exit:
+  ret void
+}
-- 
2.7.4