From 7a6f54545fcb0688018820289338fd30ee72f1fa Mon Sep 17 00:00:00 2001
From: Adam Nemet <anemet@apple.com>
Date: Wed, 8 Jul 2015 22:58:48 +0000
Subject: [PATCH] [LAA] Revert a small part of r239295

This commit ([LAA] Fix estimation of number of memchecks) regressed the
logic a bit.  We shouldn't quit the analysis if we encounter a pointer
without known bounds *unless* we actually need to emit a memcheck for
it.

The original code was using NumComparisons which is now computed
differently.  Instead I compute NeedRTCheck from NumReadPtrChecks and
NumWritePtrChecks.

As side note, I find the separation of NeedRTCheck and CanDoRT
confusing, so I will try to merge them in a follow-up patch.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@241756 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LoopAccessAnalysis.cpp           | 26 +++++++++---
 .../pointer-with-unknown-bounds.ll            | 42 +++++++++++++++++++
 2 files changed, 62 insertions(+), 6 deletions(-)
 create mode 100644 test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll

diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp
index 3c5e4d96602..093becf1829 100644
--- a/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/lib/Analysis/LoopAccessAnalysis.cpp
@@ -479,6 +479,9 @@ bool AccessAnalysis::canCheckPtrAtRT(
   // Accesses between different groups doesn't need to be checked.
   unsigned ASId = 1;
   for (auto &AS : AST) {
+    int NumReadPtrChecks = 0;
+    int NumWritePtrChecks = 0;
+
     // We assign consecutive id to access from different dependence sets.
     // Accesses within the same set don't need a runtime check.
     unsigned RunningDepId = 1;
@@ -489,6 +492,11 @@ bool AccessAnalysis::canCheckPtrAtRT(
       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
       MemAccessInfo Access(Ptr, IsWrite);
 
+      if (IsWrite)
+        ++NumWritePtrChecks;
+      else
+        ++NumReadPtrChecks;
+
       if (hasComputableBounds(SE, StridesMap, Ptr) &&
           // When we run after a failing dependency check we have to make sure
           // we don't have wrapping pointers.
@@ -516,15 +524,21 @@ bool AccessAnalysis::canCheckPtrAtRT(
       }
     }
 
+    // If we have at least two writes or one write and a read then we need to
+    // check them.  But there is no need to checks if there is only one
+    // dependence set for this alias set.
+    //
+    // Note that this function computes CanDoRT and NeedRTCheck independently.
+    // For example CanDoRT=false, NeedRTCheck=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.
+    if (!(IsDepCheckNeeded && CanDoRT && RunningDepId == 2))
+      NeedRTCheck |= (NumWritePtrChecks >= 2 || (NumReadPtrChecks >= 1 &&
+                                                 NumWritePtrChecks >= 1));
+
     ++ASId;
   }
 
-  // We need a runtime check if there are any accesses that need checking.
-  // However, some accesses cannot be checked (for example because we
-  // can't determine their bounds). In these cases we would need a check
-  // but wouldn't be able to add it.
-  NeedRTCheck = !CanDoRT || RtCheck.needsAnyChecking(nullptr);
-
   // If the pointers that we would use for the bounds comparison have different
   // address spaces, assume the values aren't directly comparable, so we can't
   // use them for the runtime check. We also have to assume they could
diff --git a/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll b/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll
new file mode 100644
index 00000000000..d05849e2be2
--- /dev/null
+++ b/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll
@@ -0,0 +1,42 @@
+; RUN: opt -loop-accesses -analyze < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; We shouldn't quit the analysis if we encounter a pointer without known
+; bounds *unless* we actually need to emit a memcheck for it.  (We only
+; compute bounds for SCEVAddRecs so A[i*I] is deemed not having known bounds.)
+;
+; for (i = 0; i < 20; ++i)
+;   A[i*i] *= 2;
+
+; CHECK: for.body:
+; CHECK:     Report: unsafe dependent memory operations in loop
+; CHECK-NOT: Report: cannot identify array bounds
+; CHECK:     Interesting Dependences:
+; CHECK:       Unknown:
+; CHECK:           %loadA = load i16, i16* %arrayidxA, align 2 ->
+; CHECK:           store i16 %mul, i16* %arrayidxA, align 2
+
+define void @f(i16* %a) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
+
+  %access_ind = mul i64 %ind, %ind
+
+  %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %access_ind
+  %loadA = load i16, i16* %arrayidxA, align 2
+
+  %mul = mul i16 %loadA, 2
+
+  store i16 %mul, i16* %arrayidxA, align 2
+
+  %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
+}
-- 
2.34.1