[LAA] Support looking through pointer selects (WIP).

[fhahn]

Summary

This patch extends visitPointes to look through GEPs. If the base
pointer is a select, construct 2 pointer SCEVs, one with each incoming
value and call AddPointer on both.

This effectively allows us to generate runtime checks for pointers
involving selects, by creating 2 MemAccessInfos for such pointers.

[Allen]

hi @fhahn, should this PR try to fix the scene showed https://gcc.godbolt.org/z/6sq4KGKfM ?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

if (CI->getOperand(0)->getType()->isIntegerTy())
       return CI->getOperand(0);
   return V;
 }
 
 const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
                                             const ValueToValueMap &PtrToStride,
                                             Value *Ptr) {
   const SCEV *OrigSCEV = PSE.getSCEV(Ptr);
-
   // If there is an entry in the map return the SCEV of the pointer with the
   // symbolic stride replaced by one.
   ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);
   if (SI == PtrToStride.end())
     // For a non-symbolic stride, just return the original expression.
     return OrigSCEV;
 
   Value *StrideVal = stripIntegerCast(SI->second);

 visitPointers(Value *StartPtr, const Loop &InnermostLoop,
               PredicatedScalarEvolution &PSE,
               const ValueToValueMap &SymbolicStrides,
               function_ref<void(Value *, const SCEV *)> AddPointer) {
   SmallPtrSet<Value *, 8> Visited;
   SmallVector<Value *> WorkList;
   WorkList.push_back(StartPtr);
 
+  ScalarEvolution &SE = *PSE.getSE();
   while (!WorkList.empty()) {
     Value *Ptr = WorkList.pop_back_val();
     if (!Visited.insert(Ptr).second)
       continue;
     auto *PN = dyn_cast<PHINode>(Ptr);
     // SCEV does not look through non-header PHIs inside the loop. Such phis
     // can be analyzed by adding separate accesses for each incoming pointer
     // value.
     if (PN && InnermostLoop.contains(PN->getParent()) &&
         PN->getParent() != InnermostLoop.getHeader()) {
       for (const Use &Inc : PN->incoming_values())
         WorkList.push_back(Inc);
-    } else
+    } else {
+      auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
+      if (GEP && GEP->getNumOperands() == 2) {
+        if (auto *SI = dyn_cast<SelectInst>(GEP->getOperand(0))) {
+          const SCEV *BaseA = SE.getSCEV(SI->getOperand(1));
+          const SCEV *BaseB = SE.getSCEV(SI->getOperand(2));
+          const SCEV *Offset = SE.getSCEV(GEP->getOperand(1));
+          if (SE.getTypeSizeInBits(Offset->getType()) <
+              SE.getTypeSizeInBits(BaseA->getType()))
+            Offset = SE.getSignExtendExpr(
+                Offset, SE.getEffectiveSCEVType(BaseA->getType()));
+          auto *PtrA = SE.getAddExpr(BaseA, Offset, SCEV::FlagNUW);
+          auto *PtrB = SE.getAddExpr(BaseB, Offset, SCEV::FlagNUW);
+          AddPointer(Ptr, PtrA);
+          AddPointer(Ptr, PtrB);
+          continue;
+        }
+      }
       AddPointer(Ptr, replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr));
     }
   }
+}
 
 bool AccessAnalysis::createCheckForAccess(
     RuntimePointerChecking &RtCheck, MemAccessInfo Access,
     DenseMap<const SCEV *, unsigned> &DepSetId, Loop *TheLoop,
     unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, bool Assume) {
   Value *Ptr = Access.getPointer();
   const SCEV *PtrScev =
       hasComputableBounds(PSE, Ptr, Access.getPtrExpr(), TheLoop, Assume);
for (auto &AS : AST) {
 
     SmallVector<MemAccessInfo, 4> Retries;
 
     // First, count how many write and read accesses are in the alias set. Also
     // collect MemAccessInfos for later.
     SmallVector<MemAccessInfo, 4> AccessInfos;
     for (const auto &A : AS) {
       Value *Ptr = A.getValue();
-      const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
-      bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true, PtrScev));
+      SmallVector<MemAccessInfo> Infos;
+      visitPointers(Ptr, *TheLoop, PSE, StridesMap,
+                    [&Infos](Value *Ptr, const SCEV *PtrExpr) {
+                      Infos.emplace_back(Ptr, true, PtrExpr);
+                    });
+      for (auto &Tmp : Infos) {
+        bool IsWrite = Accesses.count(Tmp);
 
         if (IsWrite)
           ++NumWritePtrChecks;
         else
           ++NumReadPtrChecks;
-      AccessInfos.emplace_back(Ptr, IsWrite, PtrScev);
+        AccessInfos.emplace_back(Ptr, IsWrite, Tmp.getPtrExpr());
+      }
     }
 
     // We do not need runtime checks for this alias set, if there are no writes
     // or a single write and no reads.
     if (NumWritePtrChecks == 0 ||
         (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
       assert((AS.size() <= 1 || all_of(AccessInfos,
                                        [](const MemAccessInfo &Info) {
for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
           bool IsWrite = AC.isWrite();
 
           // If we're using the deferred access set, then it contains only
           // reads.
           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
           if (UseDeferred && !IsReadOnlyPtr)
             continue;
 
-          const SCEV *PtrExpr =
-              replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr);
-          // Otherwise, the pointer must be in the PtrAccessSet, either as a
-          // read or a write.
+          visitPointers(
+              Ptr, *TheLoop, PSE, SymbolicStrides,
+              [&](Value *Ptr, const SCEV *PtrExpr) {
+                MemAccessInfo Access(Ptr, IsWrite, PtrExpr);
+                // Otherwise, the pointer must be in the PtrAccessSet, either as
+                // a read or a write.
                 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
-                  S.count(MemAccessInfo(Ptr, false, PtrExpr))) &&
+                        S.count(Access)) &&
                        "Alias-set pointer not in the access set?");
 
-          MemAccessInfo Access(Ptr, IsWrite, PtrExpr);
                 DepCands.insert(Access);
 
-          // Memorize read-only pointers for later processing and skip them in
-          // the first round (they need to be checked after we have seen all
-          // write pointers). Note: we also mark pointer that are not
-          // consecutive as "read-only" pointers (so that we check
-          // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
+                // Memorize read-only pointers for later processing and skip
+                // them in the first round (they need to be checked after we
+                // have seen all write pointers). Note: we also mark pointer
+                // that are not consecutive as "read-only" pointers (so that we
+                // check "a[b[i]] +="). Hence, we need the second check for
+                // "!IsWrite".
                 if (!UseDeferred && IsReadOnlyPtr) {
                   DeferredAccesses.insert(Access);
-            continue;
+                  return;
                 }
 
-          // If this is a write - check other reads and writes for conflicts. If
-          // this is a read only check other writes for conflicts (but only if
-          // there is no other write to the ptr - this is an optimization to
-          // catch "a[i] = a[i] + " without having to do a dependence check).
+                // If this is a write - check other reads and writes for
+                // conflicts. If this is a read only check other writes for
+                // conflicts (but only if there is no other write to the ptr -
+                // this is an optimization to catch "a[i] = a[i] + " without
+                // having to do a dependence check).
                 if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
                   CheckDeps.push_back(Access);
                   IsRTCheckAnalysisNeeded = true;
                 }
 
                 if (IsWrite)
                   SetHasWrite = true;
 
                 // Create sets of pointers connected by a shared alias set and
                 // underlying object.
                 typedef SmallVector<const Value *, 16> ValueVector;
                 ValueVector TempObjects;
 
                 getUnderlyingObjects(Ptr, TempObjects, LI);
-          LLVM_DEBUG(dbgs()
-                     << "Underlying objects for pointer " << *Ptr << "\n");
+                LLVM_DEBUG(dbgs() << "Underlying objects for pointer " << *Ptr
+                                  << "\n");
                 for (const Value *UnderlyingObj : TempObjects) {
-            // nullptr never alias, don't join sets for pointer that have "null"
-            // in their UnderlyingObjects list.
+                  // nullptr never alias, don't join sets for pointer that have
+                  // "null" in their UnderlyingObjects list.
                   if (isa<ConstantPointerNull>(UnderlyingObj) &&
                       !NullPointerIsDefined(
                           TheLoop->getHeader()->getParent(),
                           UnderlyingObj->getType()->getPointerAddressSpace()))
                     continue;
 
                   UnderlyingObjToAccessMap::iterator Prev =
                       ObjToLastAccess.find(UnderlyingObj);
                   if (Prev != ObjToLastAccess.end())
                     DepCands.unionSets(Access, Prev->second);
 
                   ObjToLastAccess[UnderlyingObj] = Access;
                   LLVM_DEBUG(dbgs() << "  " << *UnderlyingObj << "\n");
                 }
+              });
         }
       }
     }
   }
 }
 
 static bool isInBoundsGep(Value *Ptr) {
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))

llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll

 ;  i64 {(4 + %b),+,4}<%for.body>
 
 ; CHECK-LABEL: test1
 ; CHECK:         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
-; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
-; CHECK-NEXT:      Against group
 ; CHECK-NEXT:        %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11
+; CHECK-NEXT:      Against group
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-NEXT:      Group
-; CHECK-NEXT:        (Low: (4 + %a) High: (4 + (4 * (1 umax %x)) + %a))
-; CHECK-NEXT:          Member: {(4 + %a),+,4}<%for.body>
-; CHECK-NEXT:      Group
 ; CHECK-NEXT:        (Low: %b High: ((4 * (1 umax %x)) + %b))
 ; CHECK-NEXT:          Member: {%b,+,4}<%for.body>
+; CHECK-NEXT:      Group
+; CHECK-NEXT:        (Low: (4 + %a) High: (4 + (4 * (1 umax %x)) + %a))
+; CHECK-NEXT:          Member: {(4 + %a),+,4}<%for.body>
 ; CHECK:         Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-NEXT:    {1,+,1}<%for.body> Added Flags: <nusw>
 ; CHECK-NEXT:    {0,+,1}<%for.body> Added Flags: <nusw>
 ; CHECK:         Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom:
 ; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nuw>
 ; CHECK-NEXT:      --> {(4 + %a),+,4}<%for.body>