[LAA] Always compute DepId, even for uncomputable bounds.

[fhahn]

Summary

We can compute the dependency set id before checking for computable
bounds in createCheckForAccess. This allows us to rely on RunningDepId
only to check if runtime checks are required.

Uncomputable bounds are only an issue if runtime memory checks need to
be generated and with this change. Hence we can continue further with
the analysis, if there are uncomputable bounds, but not memchecks are
required.

[fhahn]

ping :)

[fhahn]

Rebase and ping :)

The updated tests show 2 improvements by the patch. In both cases, the base pointers are noalias, so

1. whether the pointers have computable bounds should not matter, as only the dependency check in the alias sets are relevant,
2. scev-inserted-runtime-check.ll incorrectly added !alias.scope metadata; the runtime check is for a SCEV predicate, not noaliasing.

[fhahn]

ping :)

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
                                           DenseMap<Value *, unsigned> &DepSetId,
                                           Loop *TheLoop, unsigned &RunningDepId,
                                           unsigned ASId, bool ShouldCheckWrap,
                                           bool Assume) {
   Value *Ptr = Access.getPointer();
 
   SmallVector<std::pair<const SCEV *, bool>> TranslatedPtrs =
       findForkedPointer(PSE, StridesMap, Ptr, TheLoop);
+  SmallVector<unsigned> DepIds;
+  for (unsigned I = 0, E = TranslatedPtrs.size(); I != E; ++I) {
+    // 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++;
+
+    DepIds.push_back(DepId);
+  }
 
   for (auto &P : TranslatedPtrs) {
     const SCEV *PtrExpr = P.first;
     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.
for (auto &P : TranslatedPtrs) {
     }
     // 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] = std::make_pair(
           replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false);
   }
 
-  for (auto &P : TranslatedPtrs) {
-    const SCEV *PtrExpr = P.first;
-
-    // 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++;
-
+  for (auto P : zip(TranslatedPtrs, DepIds)) {
+    const SCEV *PtrExpr = std::get<0>(P).first;
+    unsigned DepId = std::get<1>(P);
     bool IsWrite = Access.getInt();
     RtCheck.insert(TheLoop, Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE,
-                   P.second);
+                   std::get<0>(P).second);
     LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
   }
 
   return true;
 }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,
for (auto &AS : AST) {
     // independently. For example CanDoRT=false, MayNeedRTCheck=false means that
     // we have a pointer for which we couldn't find the bounds but we don't
     // actually need to emit any checks so it does not matter.
     //
     // We need runtime checks for this alias set, if there are at least 2
     // dependence sets (in which case RunningDepId > 2) or if we need to re-try
     // any bound checks (because in that case the number of dependence sets is
     // incomplete).
-    bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.empty();
+    bool NeedsAliasSetRTCheck = RunningDepId > 2;
 
     // We need to perform run-time alias checks, but some pointers had bounds
     // that couldn't be checked.
     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
       // Reset the CanDoSetRt flag and retry all accesses that have failed.
       // We know that we need these checks, so we can now be more aggressive
       // and add further checks if required (overflow checks).
       CanDoAliasSetRT = true;

llvm/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll

for.body:                                         ; preds = %for.body, %entry
   %add = add nuw nsw i64 %ind, 1
   %exitcond = icmp eq i64 %add, 20
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
-; TODO: We cannot compute the bound for %arrayidxA_ub, because the index is
+; We cannot compute the bound for %arrayidxA_ub, because the index is
 ; loaded on each iteration. As %a and %b are no-alias, no memchecks are required
 ; and unknown bounds should not prevent further analysis.
 define void @loaded_bound(i16* noalias %a, i16* noalias %b) {
 ; CHECK-LABEL: loaded_bound
 ; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Report: unsafe dependent memory operations in loop
+; CHECK-NEXT:    Unknown data dependence.
 ; CHECK-NEXT:    Dependences:
-; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:       Unknown:
+; CHECK-NEXT:         %loadA_ub = load i16, i16* %arrayidxA_ub, align 2 ->
+; CHECK-NEXT:         store i16 %mul, i16* %arrayidxA, align 2
+; CHECK:       Run-time memory checks:
+; CHECK-NEXT:  Grouped accesses:
 
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
 
   %iv.next = add nuw nsw i64 %iv, 1

llvm/test/Transforms/LoopDistribute/scev-inserted-runtime-check.ll

 ; CHECK:       for.body.ph.ldist1:
 ; CHECK-NEXT:    br label [[FOR_BODY_LDIST1:%.*]]
 ; CHECK:       for.body.ldist1:
 ; CHECK-NEXT:    [[IND_LDIST1:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[ADD_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[IND1_LDIST1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[INC1_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[MUL_LDIST1:%.*]] = mul i32 [[IND1_LDIST1]], 2
 ; CHECK-NEXT:    [[MUL_EXT_LDIST1:%.*]] = zext i32 [[MUL_LDIST1]] to i64
 ; CHECK-NEXT:    [[ARRAYIDXA_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[MUL_EXT_LDIST1]]
-; CHECK-NEXT:    [[LOADA_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXA_LDIST1]], align 4, !alias.scope !0
+; CHECK-NEXT:    [[LOADA_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXA_LDIST1]], align 4
 ; CHECK-NEXT:    [[ARRAYIDXB_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[MUL_EXT_LDIST1]]
 ; CHECK-NEXT:    [[LOADB_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXB_LDIST1]], align 4
 ; CHECK-NEXT:    [[MULA_LDIST1:%.*]] = mul i32 [[LOADB_LDIST1]], [[LOADA_LDIST1]]
 ; CHECK-NEXT:    [[ADD_LDIST1]] = add nuw nsw i64 [[IND_LDIST1]], 1
 ; CHECK-NEXT:    [[INC1_LDIST1]] = add i32 [[IND1_LDIST1]], 1
 ; CHECK-NEXT:    [[ARRAYIDXA_PLUS_4_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[ADD_LDIST1]]
-; CHECK-NEXT:    store i32 [[MULA_LDIST1]], i32* [[ARRAYIDXA_PLUS_4_LDIST1]], align 4, !alias.scope !3
+; CHECK-NEXT:    store i32 [[MULA_LDIST1]], i32* [[ARRAYIDXA_PLUS_4_LDIST1]], align 4
 ; CHECK-NEXT:    [[EXITCOND_LDIST1:%.*]] = icmp eq i64 [[ADD_LDIST1]], [[N]]
 ; CHECK-NEXT:    br i1 [[EXITCOND_LDIST1]], label [[FOR_BODY_PH:%.*]], label [[FOR_BODY_LDIST1]]
 ; CHECK:       for.body.ph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[IND1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH]] ], [ [[INC1:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2

 ; CHECK:       for.body.ph.ldist1:
 ; CHECK-NEXT:    br label [[FOR_BODY_LDIST1:%.*]]
 ; CHECK:       for.body.ldist1:
 ; CHECK-NEXT:    [[IND_LDIST1:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[ADD_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[IND1_LDIST1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[INC1_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[MUL_LDIST1:%.*]] = mul i32 [[IND1_LDIST1]], 2
 ; CHECK-NEXT:    [[MUL_EXT_LDIST1:%.*]] = zext i32 [[MUL_LDIST1]] to i64
 ; CHECK-NEXT:    [[ARRAYIDXA_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[MUL_EXT_LDIST1]]
-; CHECK-NEXT:    [[LOADA_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXA_LDIST1]], align 4, !alias.scope !5
+; CHECK-NEXT:    [[LOADA_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXA_LDIST1]], align 4
 ; CHECK-NEXT:    [[ARRAYIDXB_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[MUL_EXT_LDIST1]]
 ; CHECK-NEXT:    [[LOADB_LDIST1:%.*]] = load i32, i32* [[ARRAYIDXB_LDIST1]], align 4
 ; CHECK-NEXT:    [[MULA_LDIST1:%.*]] = mul i32 [[LOADB_LDIST1]], [[LOADA_LDIST1]]
 ; CHECK-NEXT:    [[ADD_LDIST1]] = add nuw nsw i64 [[IND_LDIST1]], 1
 ; CHECK-NEXT:    [[INC1_LDIST1]] = add i32 [[IND1_LDIST1]], 1
 ; CHECK-NEXT:    [[ARRAYIDXA_PLUS_4_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[ADD_LDIST1]]
-; CHECK-NEXT:    store i32 [[MULA_LDIST1]], i32* [[ARRAYIDXA_PLUS_4_LDIST1]], align 4, !alias.scope !8
+; CHECK-NEXT:    store i32 [[MULA_LDIST1]], i32* [[ARRAYIDXA_PLUS_4_LDIST1]], align 4
 ; CHECK-NEXT:    [[EXITCOND_LDIST1:%.*]] = icmp eq i64 [[ADD_LDIST1]], [[N]]
 ; CHECK-NEXT:    br i1 [[EXITCOND_LDIST1]], label [[FOR_BODY_PH:%.*]], label [[FOR_BODY_LDIST1]]
 ; CHECK:       for.body.ph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[IND1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH]] ], [ [[INC1:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2