[LAA] Support runtime checks for select GEP base pointers.

[fhahn]

Summary

Scaffolding support for generating runtime checks for multiple SCEV expressions
per pointer. The initial version just adds support for looking through
a single select.

The more sophisticated logic for analyzing forks is in D108699

[fhahn]

rebased on top of precommitted tests, simplified code

[fhahn]

Rebase and stripped down logic for translating pointers to bare minimum.

[fhahn]

ping :)

[huntergr]

LGTM

[vitalybuka]

This patch is causing false reports with msan. I am trying to creduce the code. It's with TensorFlow, so far it's quite complicated.

I see that before the patch the pass produced

vector.memcheck:                                  ; preds = %vector.scevcheck
  %scevgep77 = getelementptr i32, i32* %retval.0.i.sroa.sel, i64 1, !dbg !1439
  %scevgep7778 = bitcast i32* %scevgep77 to i8*, !dbg !1439
  %bound0 = icmp ult i8* %scevgep73, %scevgep7778, !dbg !1439
  %bound1 = icmp ult i8* %retval.0.i.sroa.sel76, %scevgep7475, !dbg !1439
  %found.conflict = and i1 %bound0, %bound1, !dbg !1439
  br i1 %found.conflict, label %scalar.ph, label %vector.ph

After the patch it's more complicated:

vector.memcheck:                                  ; preds = %vector.scevcheck
  %scevgep79 = getelementptr %"union.absl::container_internal::map_slot_type", %"union.absl::container_internal::map_slot_type"* %33, i64 0, i32 0, i32 1, i32 1, i32 0, i32 2, !dbg !1439
  %scevgep7980 = bitcast i32* %scevgep79 to i8*, !dbg !1439
  %scevgep81 = getelementptr %"union.absl::container_internal::map_slot_type", %"union.absl::container_internal::map_slot_type"* %33, i64 0, i32 0, i32 1, i32 2, i64 0, !dbg !1439
  %bound0 = icmp ult i8* %scevgep73, %scevgep78, !dbg !1439
  %bound1 = icmp ult i8* %scevgep7677, %scevgep7475, !dbg !1439
  %found.conflict = and i1 %bound0, %bound1, !dbg !1439
  %bound082 = icmp ult i8* %scevgep73, %scevgep81, !dbg !1439
  %bound183 = icmp ult i8* %scevgep7980, %scevgep7475, !dbg !1439
  %found.conflict84 = and i1 %bound082, %bound183, !dbg !1439
  %conflict.rdx = or i1 %found.conflict, %found.conflict84, !dbg !1439
  br i1 %conflict.rdx, label %scalar.ph, label %vector.ph

Then then when Msan instruments the code, it detects branch on uninitialized %conflict.rdx

I will continue to minimize the reproducer.
Should we revert the patch, because it breaks Msan and maybe there is a chance the bounds are calculated incorrectly?

[fhahn]

In D114487#3546674, @vitalybuka wrote:

I will continue to minimize the reproducer.
Should we revert the patch, because it breaks Msan and maybe there is a chance the bounds are calculated incorrectly?

Thanks for the report, I'll take a look. I already have suspicion of what's going wrong. Hopefully I'll be able to write up a test case & fix today. If not, we can revert tomorrow.

[vitalybuka]

In D114487#3547560, @fhahn wrote:

In D114487#3546674, @vitalybuka wrote:

I will continue to minimize the reproducer.
Should we revert the patch, because it breaks Msan and maybe there is a chance the bounds are calculated incorrectly?

Thanks for the report, I'll take a look. I already have suspicion of what's going wrong.

My current reproducer is

#include "third_party/absl/container/flat_hash_map.h"
#include "third_party/tensorflow/core/framework/tensor.h"

int main() {
  absl::flat_hash_map<std::string, int> ids_map;
  std::vector<std::string> ids = {"1405217"};
  int d = 0;
  tensorflow::Tensor tensor(tensorflow::DataTypeToEnum<float>::v(),
                            {1, 20, 50, 1});
  tensor.flat<float>().setConstant(0);

  auto tm = tensor.tensor<float, 4>();
  int i = 0;
  for (const auto& other_agent_id : ids) {
    auto it = ids_map.find(other_agent_id);
    const int& f = it != ids_map.end() ? it->second : d;
    for (int j = 0; j < 50; ++j) {
      tm(0, i, j, 0) = f;
    }
    ++i;
  }
}

Not sure if it's helpful, as it requires TF with dependencies build with msan:
-O2 -fsanitize=memory -fsanitize-memory-param-retval -fsanitize-memory-use-after-dtor

Hopefully I'll be able to write up a test case & fix today. If not, we can revert tomorrow.

Thanks, revert will help, as out internal release is blocked on this patch.

[alexfh]

I've reverted the commit in 7aa8a678826dea86ff3e6c7df9d2a8a6ef868f5d to unblock our internal release.

[vitalybuka]

@fhahn
This is reduced reproducer:

struct c {
  int b;
};
struct e {
  int &operator*() { return ae->b; }
  bool operator!=(e) __attribute__((noinline)) { return 0; }
  c *ae;
};
int a;
float g;
int main() {
  e b, d;
  int &f = d != b ? *d : a;
  for (int h = 0; h < 50; ++h)
    g = f;
}

clang++ -cc1 -triple x86_64-grtev4-linux-gnu -emit-obj -mframe-pointer=non-leaf -relaxed-aliasing -mconstructor-aliases -O2 -fsanitize=memory -Werror -Wreturn-type -fsanitize-memory-use-after-dtor -fsanitize-memory-param-retval -vectorize-loops -o t.o -x c++ t.cc
clang++ t.o -fsanitize=memory -fuse-ld=lld -o t -g0 -s -Wl,--strip-all

./t

==350572==WARNING: MemorySanitizer: use-of-uninitialized-value
SUMMARY: MemorySanitizer: use-of-uninitialized-value

[fhahn]

In D114487#3555041, @vitalybuka wrote:

@fhahn
This is reduced reproducer:

Thanks! I think I was able to isolate the bits that caused problems:

1. Unecessarily looking through selects outside the loop
2. Introducing branches on undef/poison when looking through selects.

I recommitted the change in e9cced27390ba38eac1144aa1240281a1edadec0. I couldn't test with msan though, as it's not available on macOS. Please let me know if you see further issues.

[vitalybuka]

In D114487#3593011, @fhahn wrote:

In D114487#3555041, @vitalybuka wrote:

@fhahn
This is reduced reproducer:

Thanks! I think I was able to isolate the bits that caused problems:

1. Unecessarily looking through selects outside the loop
2. Introducing branches on undef/poison when looking through selects.

I recommitted the change in e9cced27390ba38eac1144aa1240281a1edadec0. I couldn't test with msan though, as it's not available on macOS. Please let me know if you see further issues.

Thanks! Out test works with e9cced27390ba38eac1144aa1240281a1edadec0

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

void reset() {
     Checks.clear();
   }
 
   /// Insert a pointer and calculate the start and end SCEVs.
   /// We need \p PSE in order to compute the SCEV expression of the pointer
   /// according to the assumptions that we've made during the analysis.
   /// The method might also version the pointer stride according to \p Strides,
   /// and add new predicates to \p PSE.
-  void insert(Loop *Lp, Value *Ptr, Type *AccessTy, bool WritePtr,
-              unsigned DepSetId, unsigned ASId, const ValueToValueMap &Strides,
+  void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
+              bool WritePtr, unsigned DepSetId, unsigned ASId,
               PredicatedScalarEvolution &PSE);
 
   /// No run-time memory checking is necessary.
   bool empty() const { return Pointers.empty(); }
 
   /// Generate the checks and store it.  This also performs the grouping
   /// of pointers to reduce the number of memchecks necessary.
   void generateChecks(MemoryDepChecker::DepCandidates &DepCands,

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
+using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "loop-accesses"
 
 static cl::opt<unsigned, true>
 VectorizationFactor("force-vector-width", cl::Hidden,
                     cl::desc("Sets the SIMD width. Zero is autoselect."),
                     cl::location(VectorizerParams::VectorizationFactor));
 unsigned VectorizerParams::VectorizationFactor;

 /// N is a calculated back-edge taken count:
 ///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
 /// Start and End points are calculated in the following way:
 /// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
 /// where SizeOfElt is the size of single memory access in bytes.
 ///
 /// There is no conflict when the intervals are disjoint:
 /// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
-void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, Type *AccessTy,
-                                    bool WritePtr, unsigned DepSetId,
-                                    unsigned ASId,
-                                    const ValueToValueMap &Strides,
+void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
+                                    Type *AccessTy, bool WritePtr,
+                                    unsigned DepSetId, unsigned ASId,
                                     PredicatedScalarEvolution &PSE) {
-  // Get the stride replaced scev.
-  const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
   ScalarEvolution *SE = PSE.getSE();
 
   const SCEV *ScStart;
   const SCEV *ScEnd;
 
-  if (SE->isLoopInvariant(Sc, Lp)) {
-    ScStart = ScEnd = Sc;
+  if (SE->isLoopInvariant(PtrExpr, Lp)) {
+    ScStart = ScEnd = PtrExpr;
   } else {
-    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
+    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrExpr);
     assert(AR && "Invalid addrec expression");
     const SCEV *Ex = PSE.getBackedgeTakenCount();
 
     ScStart = AR->getStart();
     ScEnd = AR->evaluateAtIteration(Ex, *SE);
     const SCEV *Step = AR->getStepRecurrence(*SE);
 
     // For expressions with negative step, the upper bound is ScStart and the
if (SE->isLoopInvariant(PtrExpr, Lp)) {
     }
   }
   // Add the size of the pointed element to ScEnd.
   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
   Type *IdxTy = DL.getIndexType(Ptr->getType());
   const SCEV *EltSizeSCEV = SE->getStoreSizeOfExpr(IdxTy, AccessTy);
   ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
 
-  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
+  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr);
 }
 
 SmallVector<RuntimePointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
   SmallVector<RuntimePointerCheck, 4> Checks;
 
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
void RuntimePointerChecking::groupChecks(
   if (!UseDependencies) {
     for (unsigned I = 0; I < Pointers.size(); ++I)
       CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
     return;
   }
 
   unsigned TotalComparisons = 0;
 
-  DenseMap<Value *, unsigned> PositionMap;
-  for (unsigned Index = 0; Index < Pointers.size(); ++Index)
-    PositionMap[Pointers[Index].PointerValue] = Index;
+  DenseMap<Value *, SmallVector<unsigned>> PositionMap;
+  for (unsigned Index = 0; Index < Pointers.size(); ++Index) {
+    auto Iter = PositionMap.insert({Pointers[Index].PointerValue, {}});
+    Iter.first->second.push_back(Index);
+  }
 
   // We need to keep track of what pointers we've already seen so we
   // don't process them twice.
   SmallSet<unsigned, 2> Seen;
 
   // Go through all equivalence classes, get the "pointer check groups"
   // and add them to the overall solution. We use the order in which accesses
   // appear in 'Pointers' to enforce determinism.
for (unsigned I = 0; I < Pointers.size(); ++I) {
     // iteration order within an equivalence class member is only dependent on
     // the order in which unions and insertions are performed on the
     // equivalence class, the iteration order is deterministic.
     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
          MI != ME; ++MI) {
       auto PointerI = PositionMap.find(MI->getPointer());
       assert(PointerI != PositionMap.end() &&
              "pointer in equivalence class not found in PositionMap");
-      unsigned Pointer = PointerI->second;
+      for (unsigned Pointer : PointerI->second) {
         bool Merged = false;
         // Mark this pointer as seen.
         Seen.insert(Pointer);
 
         // Go through all the existing sets and see if we can find one
         // which can include this pointer.
         for (RuntimeCheckingPtrGroup &Group : Groups) {
           // Don't perform more than a certain amount of comparisons.
           // This should limit the cost of grouping the pointers to something
           // reasonable.  If we do end up hitting this threshold, the algorithm
           // will create separate groups for all remaining pointers.
           if (TotalComparisons > MemoryCheckMergeThreshold)
             break;
 
           TotalComparisons++;
 
           if (Group.addPointer(Pointer, *this)) {
             Merged = true;
             break;
           }
         }
 
         if (!Merged)
           // We couldn't add this pointer to any existing set or the threshold
           // for the number of comparisons has been reached. Create a new group
           // to hold the current pointer.
           Groups.push_back(RuntimeCheckingPtrGroup(Pointer, *this));
       }
+    }
 
     // We've computed the grouped checks for this partition.
     // Save the results and continue with the next one.
     llvm::copy(Groups, std::back_inserter(CheckingGroups));
   }
 }
 
 bool RuntimePointerChecking::arePointersInSamePartition(
private:
   PredicatedScalarEvolution &PSE;
 };
 
 } // end anonymous namespace
 
 /// Check whether a pointer can participate in a runtime bounds check.
 /// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
 /// by adding run-time checks (overflow checks) if necessary.
-static bool hasComputableBounds(PredicatedScalarEvolution &PSE,
-                                const ValueToValueMap &Strides, Value *Ptr,
-                                Loop *L, bool Assume) {
-  const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
-
+static bool hasComputableBounds(PredicatedScalarEvolution &PSE, Value *Ptr,
+                                const SCEV *PtrScev, Loop *L, bool Assume) {
   // The bounds for loop-invariant pointer is trivial.
   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     return true;
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 
   if (!AR && Assume)
     AR = PSE.getAsAddRec(Ptr);
bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
                                           MemAccessInfo Access, Type *AccessTy,
                                           const ValueToValueMap &StridesMap,
                                           DenseMap<Value *, unsigned> &DepSetId,
                                           Loop *TheLoop, unsigned &RunningDepId,
                                           unsigned ASId, bool ShouldCheckWrap,
                                           bool Assume) {
   Value *Ptr = Access.getPointer();
 
-  if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume))
+  ScalarEvolution &SE = *PSE.getSE();
+  SmallVector<const SCEV *> TranslatedPtrs;
+  if (auto *SI = dyn_cast<SelectInst>(Ptr))
+    TranslatedPtrs = {SE.getSCEV(SI->getOperand(1)),
+                      SE.getSCEV(SI->getOperand(2))};
+  else
+    TranslatedPtrs = {replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr)};
+
+  for (const SCEV *PtrExpr : TranslatedPtrs) {
+    if (!hasComputableBounds(PSE, Ptr, PtrExpr, TheLoop, Assume))
       return false;
 
     // When we run after a failing dependency check we have to make sure
     // we don't have wrapping pointers.
-  if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, AccessTy, TheLoop)) {
+    if (ShouldCheckWrap) {
+      // Skip wrap checking when translating pointers.
+      if (TranslatedPtrs.size() > 1)
+        return false;
+
+      if (!isNoWrap(PSE, StridesMap, Ptr, AccessTy, TheLoop)) {
         auto *Expr = PSE.getSCEV(Ptr);
         if (!Assume || !isa<SCEVAddRecExpr>(Expr))
           return false;
         PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
       }
+    }
+    // If there's only one option for Ptr, look it up after bounds and wrap
+    // checking, because assumptions might have been added to PSE.
+    if (TranslatedPtrs.size() == 1)
+      TranslatedPtrs[0] = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
+  }
 
+  for (const SCEV *PtrExpr : TranslatedPtrs) {
     // The id of the dependence set.
     unsigned DepId;
 
     if (isDependencyCheckNeeded()) {
       Value *Leader = DepCands.getLeaderValue(Access).getPointer();
       unsigned &LeaderId = DepSetId[Leader];
       if (!LeaderId)
         LeaderId = RunningDepId++;
       DepId = LeaderId;
     } else
       // Each access has its own dependence set.
       DepId = RunningDepId++;
 
     bool IsWrite = Access.getInt();
-  RtCheck.insert(TheLoop, Ptr, AccessTy, IsWrite, DepId, ASId, StridesMap, PSE);
+    RtCheck.insert(TheLoop, Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE);
     LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
+  }
 
   return true;
 }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,
                                      const ValueToValueMap &StridesMap,
                                      Value *&UncomputablePtr, bool ShouldCheckWrap) {

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

 ; RUN: opt -disable-output -passes='print-access-info' %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 ; CHECK-LABEL: function 'forked_ptrs_simple':
 ; CHECK-NEXT:  loop:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe with run-time checks
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:    Check 0:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %gep.Dest = getelementptr inbounds float, float* %Dest, i64 %iv
+; CHECK-NEXT:        %gep.Dest = getelementptr inbounds float, float* %Dest, i64 %iv
+; CHECK-NEXT:      Against group ([[G2:.+]]):
+; CHECK-NEXT:        %select = select i1 %cmp, float* %gep.1, float* %gep.2
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[G1]]):
+; CHECK-NEXT:        %gep.Dest = getelementptr inbounds float, float* %Dest, i64 %iv
+; CHECK-NEXT:        %gep.Dest = getelementptr inbounds float, float* %Dest, i64 %iv
+; CHECK-NEXT:      Against group ([[G3:.+]]):
+; CHECK-NEXT:        %select = select i1 %cmp, float* %gep.1, float* %gep.2
 ; CHECK-NEXT:    Grouped accesses:
+; CHECK-NEXT:      Group [[G1]]
+; CHECK-NEXT:        (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%loop>
+; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%loop>
+; CHECK-NEXT:      Group [[G2]]:
+; CHECK-NEXT:        (Low: %Base1 High: (400 + %Base1))
+; CHECK-NEXT:          Member: {%Base1,+,4}<nw><%loop>
+; CHECK-NEXT:      Group [[G3]]:
+; CHECK-NEXT:        (Low: %Base2 High: (400 + %Base2))
+; CHECK-NEXT:          Member: {%Base2,+,4}<nw><%loop>
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 
 define void @forked_ptrs_simple(float* nocapture readonly %Base1, float* nocapture readonly %Base2, float* %Dest) {
 entry: