[InterleavedAccessAnalysis] Fix integer overflow in insertMember.

[fhahn]

Summary

Without checking for integer overflow, invalid members can be added
e.g. if the calculated key overflows, becomes positive and the largest key.

This fixes

https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=7560
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13128
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13229

[fhahn]

I guess it would be even safer to use fixed sized integer types here, but that would have a larger impact.

[fhahn]

ping

[efriedma]

I don't understand the implications of returning false here...

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

[fhahn]

In D55538#1336581, @efriedma wrote:

I don't understand the implications of returning false here...

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

Right, I'll take a look at that.

[fhahn]

Updated to catch more cases. This now fixes 4 fuzzer failures

[fhahn]

Sorry for the long delay....

In D55538#1336581, @efriedma wrote:

I don't understand the implications of returning false here...

It indicates to the caller that the instruction wasn't added to the interleave group. It's checked in analyzeInterleaving (in VectorUtils.cpp), to see if we should add the group to InterleaveGroupMap for the instruction. Returning false and not inserting the member should always be safe.

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

I've put up D58889, which switches to fixed size integer types. Is that along the lines you were thinking?

[efriedma]

If it's safe to conservatively return false here, and we're convinced realistic code isn't going to require larger strides/indexes, it's fine to just reject anything that won't fit into a 32-bit integer, I guess.

llvm/include/llvm/Analysis/VectorUtils.h

261 ↗

(On Diff #189113)

Not part of your patch, I guess, but do we have any particular reason to expect that Stride does not equal INT_MIN?

284 ↗

(On Diff #189113)

Not sure I understand the "-2" and "+2" here; is the issue that it collides with the default DenseMap tombstone otherwise? Can we use some map that doesn't randomly reserve certain integers? Otherwise, please add an explicit note, and check for the tombstone/empty keys separately from the overflow check.

Do we have some overflow-checked addition helper we could use instead of writing out the overflow check here?

[fhahn]

llvm/include/llvm/Analysis/VectorUtils.h

284 ↗

(On Diff #189113)

Yep it's a tombstone check. I guess we could use std::unordered_map, will that have a perf impact?

I'll check again if there are some overflow helpers anywhere, but if not then it might be worth adding some.

[fhahn]

Use helpers from CheckedArithmetic.h for overflow checks, split out tombstone issue.

[fhahn]

llvm/include/llvm/Analysis/VectorUtils.h

261 ↗

(On Diff #189113)

I don't think so, I'll check and address it separately.

284 ↗

(On Diff #189113)

I've split out the tombstone handling to D59050 and updated the code to use CheckedArithmetic.h's helper functions.

[efriedma]

LGTM

llvm/trunk/include/llvm/Analysis/VectorUtils.h

 
 #ifndef 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"
 
 namespace llvm {
 
 template <typename T> class ArrayRef;
 class DemandedBits;
 class GetElementPtrInst;
 template <typename InstTy> class InterleaveGroup;
 class Loop;
public:
   /// Try to insert a new member \p Instr with index \p Index and
   /// alignment \p NewAlign. The index is related to the leader and it could be
   /// negative if it is the new leader.
   ///
   /// \returns false if the instruction doesn't belong to the group.
   bool insertMember(InstTy *Instr, int32_t Index, uint32_t NewAlign) {
     assert(NewAlign && "The new member's alignment should be non-zero");
 
-    int32_t Key = Index + SmallestKey;
+    // Make sure the key fits in an int32_t.
+    Optional<int32_t> MaybeKey = checkedAdd(Index, SmallestKey);
+    if (!MaybeKey)
+      return false;
+    int32_t Key = *MaybeKey;
 
     // Skip if there is already a member with the same index.
     if (Members.find(Key) != Members.end())
       return false;
 
     if (Key > LargestKey) {
       // The largest index is always less than the interleave factor.
-      if (Index >= static_cast<int>(Factor))
+      if (Index >= static_cast<int32_t>(Factor))
         return false;
 
       LargestKey = Key;
     } else if (Key < SmallestKey) {
+
+      // Make sure the largest index fits in an int32_t.
+      Optional<int32_t> MaybeLargestIndex = checkedSub(LargestKey, Key);
+      if (!MaybeLargestIndex)
+        return false;
+
       // The largest index is always less than the interleave factor.
-      if (LargestKey - Key >= static_cast<int>(Factor))
+      if (*MaybeLargestIndex >= static_cast<int64_t>(Factor))
         return false;
 
       SmallestKey = Key;
     }
 
     // It's always safe to select the minimum alignment.
     Align = std::min(Align, NewAlign);
     Members[Key] = Instr;

llvm/trunk/include/llvm/Support/CheckedArithmetic.h

 /// \return Optional of sum if no signed overflow occurred,
 /// \c None otherwise.
 template <typename T>
 typename std::enable_if<std::is_signed<T>::value, llvm::Optional<T>>::type
 checkedAdd(T LHS, T RHS) {
   return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov);
 }
 
+/// Subtract two signed integers \p LHS and \p RHS.
+/// \return Optional of sum if no signed overflow occurred,
+/// \c None otherwise.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, llvm::Optional<T>>::type
+checkedSub(T LHS, T RHS) {
+  return checkedOp(LHS, RHS, &llvm::APInt::ssub_ov);
+}
+
 /// Multiply two signed integers \p LHS and \p RHS.
 /// \return Optional of product if no signed overflow occurred,
 /// \c None otherwise.
 template <typename T>
 typename std::enable_if<std::is_signed<T>::value, llvm::Optional<T>>::type
 checkedMul(T LHS, T RHS) {
   return checkedOp(LHS, RHS, &llvm::APInt::smul_ov);
 }

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

+; RUN: opt < %s  -loop-vectorize -mtriple x86_64 -S | FileCheck %s
+
+%struct.ST4 = type { i32, i32, i32, i32 }
+
+; The gaps between the memory access in this function are too large for
+; interleaving.
+
+; Test from https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=7560
+define void @test1(%struct.ST4* noalias %B) {
+; CHECK-LABEL: @test1
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %for.body
+
+; CHECK-LABEL: for.body:
+; CHECK: store i32
+; CHECK: store i32
+; CHECK: store i32
+; CHECK: store i32
+; CHECK-NOT: store
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %p1 = getelementptr inbounds %struct.ST4, %struct.ST4* %B, i64 %indvars.iv, i32 0
+  store i32 65536, i32* %p1, align 4
+  %p2 = getelementptr i32, i32* %p1, i32 -2147483648
+  store i32 65536, i32* %p2, align 4
+  %p3 = getelementptr inbounds %struct.ST4, %struct.ST4* %B, i64 %indvars.iv, i32 2
+  store i32 10, i32* %p3, align 4
+  %p4 = getelementptr inbounds %struct.ST4, %struct.ST4* %B, i64 %indvars.iv, i32 3
+  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
+}