[Sink] Don't move calls to readonly functions across stores

[nhaehnle]

Summary

This is conservative because it doesn't consider the argmemonly attribute.
Perhaps somebody who knows this part of the code better can improve this
in a separate patch. For now, it fixes a real miscompilation I encountered
in the AMDGPU backend.

[• dberlin]

Doesn't AA have an existing API that gives you exactly the info you want
here (Does this call ref the memory touched the things in the store list)

[nhaehnle]

In D17279#353238, @dberlin wrote:

Doesn't AA have an existing API that gives you exactly the info you want
here (Does this call ref the memory touched the things in the store list)

I see no such interface in AAResults at least. All queries test $something against a MemoryLocation, but the Stores are instructions because they could also be call sites. There would have to be an interface to test an instruction against an instruction, or two call sites against each other.

[hfinkel]

In D17279#372215, @nhaehnle wrote:

In D17279#353238, @dberlin wrote:

Doesn't AA have an existing API that gives you exactly the info you want
here (Does this call ref the memory touched the things in the store list)

I see no such interface in AAResults at least. All queries test $something against a MemoryLocation, but the Stores are instructions because they could also be call sites. There would have to be an interface to test an instruction against an instruction, or two call sites against each other.

we have:

/// getModRefInfo (for call sites) - Return information about whether
/// a particular call site modifies or reads the specified memory location.
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);

/// getModRefInfo (for calls) - Return information about whether
/// a particular call modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
  return getModRefInfo(ImmutableCallSite(C), Loc);
}

and many others. Also, the the generic wrapper:

ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {

all in include/llvm/Analysis/AliasAnalysis.h.

[nhaehnle]

Right, and none of these test an instruction against another instruction, or (which would be sufficient) a callsite against a callsite.

A different way to think about it is that there is no existing interface to get a list of MemoryLocations from a callsite.

[hfinkel]

In D17279#373188, @nhaehnle wrote:

Right, and none of these test an instruction against another instruction, or (which would be sufficient) a callsite against a callsite.

Sure there is:

ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);

There is also this:

ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);

there is also a MemoryLocation::get(const Instruction *Inst) - which handles all of the different instruction types except calls (there are more-refined getters for calls, chiefly getForArgument).

A different way to think about it is that there is no existing interface to get a list of MemoryLocations from a callsite.

[nhaehnle]

Update and change to deal with argmemonly.

This required a subtle change to getModRefInfo(Instruction, ImmutableCallSite)
to ensure that the semantics are equal to that of getModRefInfo(CS1, CS2) when
the Instruction is a call-site.

I would consider the old behavior to be a bug, which seems to not have surfaced
because it seems the only user of that particular getModRefInfo overload is in
MemorySSA, and that user only checks the return value for != MR_NoModRef.

While the relation is non-commutative, changing the order of the call-sites
may change the result from MR_Ref to MR_Mod and vice versa, but never to
MR_NoModRef.

[nhaehnle]

Technically I guess the change in getModRefInfo isn't needed, but it seems like the Right Thing to me.

[nhaehnle]

Ping?

[nhaehnle]

Ping^2?

[• dberlin]

Please add a test for the getmodref info change and commit it separately.

lib/Analysis/AliasAnalysis.cpp

112

Please commit this separately.

[loladiro]

Please see https://llvm.org/bugs/show_bug.cgi?id=28570 for a bug reported bisected back to this revision.

lib/Analysis/AliasAnalysis.cpp

ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
 
   return Result;
 }
 
 ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
   // We may have two calls
   if (auto CS = ImmutableCallSite(I)) {
     // Check if the two calls modify the same memory
-    return getModRefInfo(Call, CS);
+    return getModRefInfo(CS, Call);
   } else {
     // Otherwise, check if the call modifies or references the
     // location this memory access defines.  The best we can say
     // is that if the call references what this instruction
     // defines, it must be clobbered by this location.
     const MemoryLocation DefLoc = MemoryLocation::get(I);
     if (getModRefInfo(Call, DefLoc) != MRI_NoModRef)
       return MRI_ModRef;

lib/Transforms/Scalar/Sink.cpp

for (Instruction *S : Stores)
       if (AA.getModRefInfo(S, Loc) & MRI_Mod)
         return false;
   }
 
   if (isa<TerminatorInst>(Inst) || isa<PHINode>(Inst) || Inst->isEHPad() ||
       Inst->mayThrow())
     return false;
 
+  if (auto CS = CallSite(Inst)) {
     // Convergent operations cannot be made control-dependent on additional
     // values.
-  if (auto CS = CallSite(Inst)) {
     if (CS.hasFnAttr(Attribute::Convergent))
       return false;
+
+    for (Instruction *S : Stores)
+      if (AA.getModRefInfo(S, CS) & MRI_Mod)
+        return false;
   }
 
   return true;
 }
 
 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
 /// in the specified basic block.
 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,

test/Transforms/Sink/call.ll

+; RUN: opt < %s -basicaa -sink -S | FileCheck %s
+
+declare i32 @f_load_global() nounwind readonly
+declare i32 @f_load_arg(i32*) nounwind readonly argmemonly
+declare void @f_store_global(i32) nounwind
+declare void @f_store_arg(i32*) nounwind argmemonly
+declare void @f_readonly_arg(i32* readonly, i32*) nounwind argmemonly
+declare i32 @f_readnone(i32) nounwind readnone
+
+@A = external global i32
+@B = external global i32
+
+; Sink readonly call if no stores are in the way.
+;
+; CHECK-LABEL: @test_sink_no_stores(
+; CHECK: true:
+; CHECK-NEXT: %l = call i32 @f_load_global
+; CHECK-NEXT: ret i32 %l
+define i32 @test_sink_no_stores(i1 %z) {
+  %l = call i32 @f_load_global()
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; CHECK-LABEL: @test_sink_argmem_store(
+; CHECK: true:
+; CHECK-NEXT: %l = call i32 @f_load_arg
+; CHECK-NEXT: ret i32 %l
+define i32 @test_sink_argmem_store(i1 %z) {
+  %l = call i32 @f_load_arg(i32* @A)
+  store i32 0, i32* @B
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; CHECK-LABEL: @test_sink_argmem_call(
+; CHECK: true:
+; CHECK-NEXT: %l = call i32 @f_load_arg
+; CHECK-NEXT: ret i32 %l
+define i32 @test_sink_argmem_call(i1 %z) {
+  %l = call i32 @f_load_arg(i32* @A)
+  call void @f_store_arg(i32* @B)
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; CHECK-LABEL: @test_sink_argmem_multiple(
+; CHECK: true:
+; CHECK-NEXT: %l = call i32 @f_load_arg
+; CHECK-NEXT: ret i32 %l
+define i32 @test_sink_argmem_multiple(i1 %z) {
+  %l = call i32 @f_load_arg(i32* @A)
+  call void @f_readonly_arg(i32* @A, i32* @B)
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; But don't sink if there is a store.
+;
+; CHECK-LABEL: @test_nosink_store(
+; CHECK: call i32 @f_load_global
+; CHECK-NEXT: store i32
+define i32 @test_nosink_store(i1 %z) {
+  %l = call i32 @f_load_global()
+  store i32 0, i32* @A
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; CHECK-LABEL: @test_nosink_call(
+; CHECK: call i32 @f_load_global
+; CHECK-NEXT: call void @f_store_global
+define i32 @test_nosink_call(i1 %z) {
+  %l = call i32 @f_load_global()
+  call void @f_store_global(i32 0)
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}
+
+; readnone calls are sunk across stores.
+;
+; CHECK-LABEL: @test_sink_readnone(
+; CHECK: true:
+; CHECK-NEXT: %l = call i32 @f_readnone(
+; CHECK-NEXT: ret i32 %l
+define i32 @test_sink_readnone(i1 %z) {
+  %l = call i32 @f_readnone(i32 0)
+  store i32 0, i32* @A
+  br i1 %z, label %true, label %false
+true:
+  ret i32 %l
+false:
+  ret i32 0
+}