From: Silviu Baranga <silviu.baranga@arm.com>
Date: Tue, 28 Jul 2015 13:44:08 +0000 (+0000)
Subject: [LAA] Add clarifying comments for the checking pointer grouping algorithm. NFC
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=c26dfdf86b442404ed2a3d209fd152e6be0f53a1

[LAA] Add clarifying comments for the checking pointer grouping algorithm. NFC

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243416 91177308-0d34-0410-b5e6-96231b3b80d8
---

diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp
index 6a6b6d4be3b..7e36a1b961f 100644
--- a/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/lib/Analysis/LoopAccessAnalysis.cpp
@@ -237,8 +237,31 @@ void RuntimePointerChecking::groupChecks(
 
   CheckingGroups.clear();
 
+  // If we need to check two pointers to the same underlying object
+  // with a non-constant difference, we shouldn't perform any pointer
+  // grouping with those pointers. This is because we can easily get
+  // into cases where the resulting check would return false, even when
+  // the accesses are safe.
+  //
+  // The following example shows this:
+  // for (i = 0; i < 1000; ++i)
+  //   a[5000 + i * m] = a[i] + a[i + 9000]
+  //
+  // Here grouping gives a check of (5000, 5000 + 1000 * m) against
+  // (0, 10000) which is always false. However, if m is 1, there is no
+  // dependence. Not grouping the checks for a[i] and a[i + 9000] allows
+  // us to perform an accurate check in this case.
+  //
+  // The above case requires that we have an UnknownDependence between
+  // accesses to the same underlying object. This cannot happen unless
+  // ShouldRetryWithRuntimeCheck is set, and therefore UseDependencies
+  // is also false. In this case we will use the fallback path and create
+  // separate checking groups for all pointers.
+ 
   // If we don't have the dependency partitions, construct a new
-  // checking pointer group for each pointer.
+  // checking pointer group for each pointer. This is also required
+  // for correctness, because in this case we can have checking between
+  // pointers to the same underlying object.
   if (!UseDependencies) {
     for (unsigned I = 0; I < Pointers.size(); ++I)
       CheckingGroups.push_back(CheckingPtrGroup(I, *this));
diff --git a/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll b/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
index ab9abd7c60a..01b3eda3e12 100644
--- a/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
+++ b/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
@@ -217,8 +217,9 @@ for.end:                                          ; preds = %for.body
   ret void
 }
 
-; Don't merge pointers if there is some other check which could be falsely
-; invalidated. For example, in the following loop:
+; Don't merge pointers if we need to perform a check against a pointer
+; to the same underlying object (doing so would emit a check that could be
+; falsely invalidated) For example, in the following loop:
 ;
 ; for (i = 0; i < 5000; ++i)
 ;   a[i + offset] = a[i] + a[i + 10000]
@@ -226,6 +227,10 @@ for.end:                                          ; preds = %for.body
 ; we should not merge the intervals associated with the reads (0,5000) and
 ; (10000, 15000) into (0, 15000) as this will pottentially fail the check
 ; against the interval associated with the write.
+;
+; We cannot have this check unless ShouldRetryWithRuntimeCheck is set,
+; and therefore the grouping algorithm would create a separate group for
+; each pointer.
 
 ; CHECK: function 'testi':
 ; CHECK: Run-time memory checks: