llvm dev - Jun 2016 - [MemorySSA] Potential bug in MemoryUse defining access calculation

Hey All,

I've come across what I believe to be a bug in MemorySSA. George, I 
wasn't sure if this was a known issue that you'll be addressing in your 
upcoming walker caching changes or not, so I haven't investigated it 
very much.  The test case is attached. The bug is that the defining 
access for the second load is set to the loop MemoryPhi node instead of 
being liveOnEntry as it should be as I understand things.

-- 
Geoff Berry
Employee of Qualcomm Innovation Center, Inc.
  Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
diff --git a/test/Transforms/Util/MemorySSA/optimize-use.ll
b/test/Transforms/Util/MemorySSA/optimize-use.ll
index 0ac07b0..45a5097 100644
--- a/test/Transforms/Util/MemorySSA/optimize-use.ll
+++ b/test/Transforms/Util/MemorySSA/optimize-use.ll
@@ -4,6 +4,7 @@
 ; Function Attrs: ssp uwtable
 define i32 @main() {
 entry:
+; CHECK-LABEL: @main
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT:   %call = call noalias i8* @_Znwm(i64 4)
   %call = call noalias i8* @_Znwm(i64 4)
@@ -35,3 +36,40 @@ entry:
 }
 
 declare noalias i8* @_Znwm(i64)
+
+ at G1 = global i16 zeroinitializer
+ at G2 = global i16 zeroinitializer
+
+define void @loop(i32 %N) {
+; CHECK-LABEL: @loop
+entry:
+  br label %for.cond
+
+for.cond:
+; CHECK: 3 = MemoryPhi
+; CHECK-NEXT: %i.0 = phi i32
+  %i.0 = phi i32 [ 0, %entry ], [ %i.1, %for.body ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %cleanup
+
+for.body:
+; this load doesn't alias either of the stores, so should have a defining
access of LiveOnEntry
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %loadG1_1 = load
+  %loadG1_1 = load i16, i16* @G1, align 2
+; CHECK: 1 = MemoryDef(3)
+; CHECK-NEXT: store i16 0
+  store i16 0, i16* @G2, align 2
+  ; ditto for this identical load
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %loadG1_2 = load
+  %loadG1_2 = load i16, i16* @G1, align 2
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i16 1
+  store i16 1, i16* @G2, align 2
+  %i.1 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+cleanup:
+  ret void
+}

This is definitely a caching bug related to this code:
   1038    // Don't try to optimize this phi again if we've already
tried
to do so.
   1039    if (!Q.Visited.insert(PHIPair).second) {
   1040      ModifyingAccess = CurrAccess;
   1041      break;
   1042    }


We don't differentiate elsewhere between having stopped at a phi because we
were path walking and discovered that path has no conflicts, and having
stopped at a phi because that was the clobbering access.

Because of this, we cache the result as if it was a clobbering access, when
it really means "you can ignore this path".

The logic in the code that handles the former case only exists after the
cache lookups, and so the first use properly detects that it can ignore
this phi, and the second use , which just hits the cache, cannot.



On Mon, Jun 27, 2016 at 10:27 AM, Geoff Berry <gberry at codeaurora.org>
wrote:
> Hey All,
>
> I've come across what I believe to be a bug in MemorySSA. George, I
wasn't
> sure if this was a known issue that you'll be addressing in your
upcoming
> walker caching changes or not, so I haven't investigated it very much. 
The
> test case is attached. The bug is that the defining access for the second
> load is set to the loop MemoryPhi node instead of being liveOnEntry as it
> should be as I understand things.
>
> --
> Geoff Berry
> Employee of Qualcomm Innovation Center, Inc.
>  Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
> Linux Foundation Collaborative Project
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160627/c053964f/attachment.html>

Danny's right; the "we need to cache everything immediately"
behavior
doesn't play very nicely with loops.

The new walker (which should be out for review later today) correctly
optimizes %loadG1_1 and %loadG1_2 to liveOnEntry. :)

George

On Mon, Jun 27, 2016 at 11:14 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> This is definitely a caching bug related to this code:
>    1038    // Don't try to optimize this phi again if we've already
tried
> to do so.
>    1039    if (!Q.Visited.insert(PHIPair).second) {
>    1040      ModifyingAccess = CurrAccess;
>    1041      break;
>    1042    }
>
>
> We don't differentiate elsewhere between having stopped at a phi
because
> we were path walking and discovered that path has no conflicts, and having
> stopped at a phi because that was the clobbering access.
>
> Because of this, we cache the result as if it was a clobbering access,
> when it really means "you can ignore this path".
>
> The logic in the code that handles the former case only exists after the
> cache lookups, and so the first use properly detects that it can ignore
> this phi, and the second use , which just hits the cache, cannot.
>
>
>
> On Mon, Jun 27, 2016 at 10:27 AM, Geoff Berry <gberry at
codeaurora.org>
> wrote:
>
>> Hey All,
>>
>> I've come across what I believe to be a bug in MemorySSA. George, I
>> wasn't sure if this was a known issue that you'll be addressing
in your
>> upcoming walker caching changes or not, so I haven't investigated
it very
>> much.  The test case is attached. The bug is that the defining access
for
>> the second load is set to the loop MemoryPhi node instead of being
>> liveOnEntry as it should be as I understand things.
>>
>> --
>> Geoff Berry
>> Employee of Qualcomm Innovation Center, Inc.
>>  Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
>> Linux Foundation Collaborative Project
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160627/488bff56/attachment-0001.html>