[InterleavedAccessAnalysis] Use unordered_map to avoid tombstone insertion.

[fhahn]

Summary

Nothing prevents a key to the Members map being a tombstone/empty
special value. By using unordered_map, we avoid limiting the keys to
exclude tombstone/empty key values. Alternatively we could avoid adding
tombstone/empty key values to interleave groups, but there should be no
performance impact by not using DenseMap.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11638

[efriedma]

unordered_map is going to be pretty inefficient given the key/value types... it might be worthwhile to add some sort of DenseMap relative to LLVM that handles tombstones differently. (This also just came up in https://reviews.llvm.org/D59016.)

[fhahn]

In D59050#1420672, @efriedma wrote:

unordered_map is going to be pretty inefficient given the key/value types... it might be worthwhile to add some sort of DenseMap relative to LLVM that handles tombstones differently. (This also just came up in https://reviews.llvm.org/D59016.)

Ok, I'll look into that.

[fhahn]

I'm currently prototyping a version of DenseMap, that uses bit vectors to mark empty/tombstone slots to circumvent the issue. There are some scenarios where this could potentially also improve runtime performance, at the cost of 2 bits per slot. What do you think?

[efriedma]

That layout generally makes sense, sure. Maybe you could get away with one bit per slot by sticking a bit to distinguish between either empty/tombstone into the main table, but I guess it's not really a big deal either way if you're talking about one or two bits per entry. I guess two bits makes failed lookups faster.

A higher-quality MapVector, which doesn't store two copies of the key, would also be generally nice to have... although the overhead is higher for small keys/values.

[fhahn]

This surfaced in more fuzzier invocations, I went ahead and submitted a fix that avoids adding empty/tombstone keys when adding new interleave group members: 83aa93e99542

llvm/include/llvm/Analysis/VectorUtils.h

 #define LLVM_ANALYSIS_VECTORUTILS_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/CheckedArithmetic.h"
 
+#include <unordered_map>
+
 namespace llvm {
 
 template <typename T> class ArrayRef;
 class DemandedBits;
 class GetElementPtrInst;
 template <typename InstTy> class InterleaveGroup;
 class Loop;
 class ScalarEvolution;
bool requiresScalarEpilogue() const {
     // This is a group of loads, with gaps, and without a last-member
     return true;
   }
 
 private:
   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;
 
   // To avoid breaking dependences, vectorized instructions of an interleave
   // group should be inserted at either the first load or the last store in
   // program order.
   //
   // E.g. %even = load i32             // Insert Position

llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-large-gap.ll

for.body:                                         ; preds = %for.body, %entry
   store i32 12, i32* %p4, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond = icmp eq i64 %indvars.iv.next, 1024
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 
 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
+}