[AST] Generalize argument specific aliasing

[reames]

Summary

AliasSetTracker has special case handling for memset, memcpy and memmove which pre-existed argmemonly on functions and readonly and writeonly on arguments. This patch generalizes it using the AA infrastructure to any call correctly annotated.

The motivation here is to cut down on confusion, not performance per se. For most instructions, there is a direct mapping to alias set. However, this is not guaranteed by the interface and was not in fact true for these three intrinsics *and only these three intrinsics*. I kept getting myself confused about this invariant, so I figured it would be good to clearly distinguish between a instructions and alias sets. Calls happened to be an easy target.

The nice side effect is that custom implementations of memset/memcpy/memmove - including wrappers discovered by IPO - can now be optimized the same as builts by LICM.

[mkazantsev]

I am concerned that these changes didn't change anything in behavior of dedicated tests in test/Analysis/AliasSet. I think we should commit some of those as NFC and then show how this patch changes behavior of these tests.

lib/Analysis/AliasSetTracker.cpp

485

Aren't we supposed to return some value here?

[mkazantsev]

lib/Analysis/AliasSetTracker.cpp

478

How about

if (!isRefSet(ArgMask))
  Access = isModSet(ArgMask) ? AliasSet::ModAccess : AliasSet::NoAccess;

480

Looks more logical to set NoAccess as default and set ModRefAccess if both Ref and Mod are set, but it's up to you.

[hiraditya]

Thanks for the patch.

include/llvm/Analysis/MemoryLocation.h

113

Maybe just remove this function?

lib/Analysis/AliasSetTracker.cpp

485

the function returns void...

lib/Analysis/MemoryLocation.cpp

166–168

TLI && CS.getCalledFunction() && ....

[reames]

include/llvm/Analysis/MemoryLocation.h

113

I would prefer not to. There are a bunch of callers and I'd like to eventually pipe TLI though here as well. I consider this a temporary step.

[reames]

rebase and incorporate suggestions.

There are a couple of key changes here:

1. I'm intentionally leaving in the redundant memset, and memtransfer pieces. I'll remove this in a following NFC, but the code changes were contributing to rebase problems and weren't strictly needed. Same with removing the invariant_start from addUnknown.
2. I removed the AA change in favour of doing this directly in the caller. This turned out to be needed for invariant_start handling (added in the rebase), and the docs for the function I was modifying contradicted my change anyway. This is much better isolated.
3. All of the tests have landed, so only the updates are shown.

In general, I'm really unhappy with how the write-for-control-flow-only handling (guards, assumes, invariant_starts) is leaking out into more places. For the moment, I'd like to land this as is, but I plan to take a closer look at the framing there and see if we can better abstract this.

[reames]

with the right patch this time

For the record, using ">>" instead of ">" when replacing an existing patch diff leads to a (surprisingly) valid patch, just not with any sensible contents.

[reames]

lib/Analysis/AliasSetTracker.cpp

472

I noticed there's a much better way to get a ModRefInfo from a FuncitonModRefBehavior. I'll replace this stretch of code with a call to createModRefInfo(MRB);

[reames]

rebase for minor issue I commented on, also ping?

[anna]

LGTM.

lib/Analysis/AliasSetTracker.cpp

457

which two family of intrinsics? Are these the memset and memtransfer calls? They are handled above. Maybe move the comment to above line 451.

[reames]

lib/Analysis/AliasSetTracker.cpp

457

The volatile comment is stale and will be removed before landing. AST no longer has a notion of volatile at all.

include/llvm/Analysis/MemoryLocation.h

public:
   /// Return a location representing the destination of a memory set or
   /// transfer.
   static MemoryLocation getForDest(const MemIntrinsic *MI);
   static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
   static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
 
   /// Return a location representing a particular argument of a call.
   static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
-                                       const TargetLibraryInfo &TLI);
+                                       const TargetLibraryInfo *TLI);
+  static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
+                                       const TargetLibraryInfo &TLI) {
+    return getForArgument(CS, ArgIdx, &TLI);
+  }
 
   explicit MemoryLocation(const Value *Ptr = nullptr,
                           LocationSize Size = UnknownSize,
                           const AAMDNodes &AATags = AAMDNodes())
       : Ptr(Ptr), Size(Size), AATags(AATags) {}
 
   MemoryLocation getWithNewPtr(const Value *NewPtr) const {
     MemoryLocation Copy(*this);

lib/Analysis/AliasSetTracker.cpp

void AliasSetTracker::add(Instruction *I) {
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return add(SI);
   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
     return add(VAAI);
   if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
     return add(MSI);
   if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
     return add(MTI);
+
+  // Handle all calls with known mod/ref sets generically, but special case the
+  // two family of intrinsics which can involve volatile access.
+  CallSite CS(I);
+  if (CS && CS.onlyAccessesArgMemory()) {
+    auto getAccessFromModRef = [](ModRefInfo MRI) {
+      if (isRefSet(MRI) && isModSet(MRI))
+        return AliasSet::ModRefAccess;
+      else if (isModSet(MRI))
+        return AliasSet::ModAccess;
+      else if (isRefSet(MRI))
+        return AliasSet::RefAccess;
+      else
+        return AliasSet::NoAccess;
+     
+    };
+    
+    ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(CS));
+
+    // Some intrinsics are marked as modifying memory for control flow
+    // modelling purposes, but don't actually modify any specific memory
+    // location. 
+    using namespace PatternMatch;
+    if (I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()))
+      CallMask = clearMod(CallMask);
+
+    for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
+      const Value *Arg = *AI;
+      if (!Arg->getType()->isPointerTy())
+        continue;
+      unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
+      MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx,
+                                                             nullptr);
+      ModRefInfo ArgMask = AA.getArgModRefInfo(CS, ArgIdx);
+      ArgMask = intersectModRef(CallMask, ArgMask);
+      if (!isNoModRef(ArgMask))
+        addPointer(ArgLoc, getAccessFromModRef(ArgMask));
+    }
+    return;
+  }
+  
   return addUnknown(I);
 }
 
 void AliasSetTracker::add(BasicBlock &BB) {
   for (auto &I : BB)
     add(&I);
 }
 

lib/Analysis/MemoryLocation.cpp

MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) {
   AAMDNodes AATags;
   MI->getAAMetadata(AATags);
 
   return MemoryLocation(MI->getRawDest(), Size, AATags);
 }
 
 MemoryLocation MemoryLocation::getForArgument(ImmutableCallSite CS,
                                               unsigned ArgIdx,
-                                              const TargetLibraryInfo &TLI) {
+                                              const TargetLibraryInfo *TLI) {
   AAMDNodes AATags;
   CS->getAAMetadata(AATags);
   const Value *Arg = CS.getArgument(ArgIdx);
 
   // We may be able to produce an exact size for known intrinsics.
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     const DataLayout &DL = II->getModule()->getDataLayout();
 
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     }
   }
 
   // We can bound the aliasing properties of memset_pattern16 just as we can
   // for memcpy/memset.  This is particularly important because the
   // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
   // whenever possible.
   LibFunc F;
-  if (CS.getCalledFunction() && TLI.getLibFunc(*CS.getCalledFunction(), F) &&
-      F == LibFunc_memset_pattern16 && TLI.has(F)) {
+  if (TLI && CS.getCalledFunction() &&
+      TLI->getLibFunc(*CS.getCalledFunction(), F) &&
+      F == LibFunc_memset_pattern16 && TLI->has(F)) {
     assert((ArgIdx == 0 || ArgIdx == 1) &&
            "Invalid argument index for memset_pattern16");
     if (ArgIdx == 1)
       return MemoryLocation(Arg, 16, AATags);
     if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2)))
       return MemoryLocation(Arg, LenCI->getZExtValue(), AATags);
   }
   // FIXME: Handle memset_pattern4 and memset_pattern8 also.
 
   return MemoryLocation(CS.getArgument(ArgIdx), UnknownSize, AATags);
 }

test/Analysis/AliasSet/argmemonly.ll

 ; RUN: opt -basicaa -print-alias-sets -S -o - < %s 2>&1 | FileCheck %s
 
 @s = global i8 1, align 1
 @d = global i8 2, align 1
 
 ; CHECK: Alias sets for function 'test_alloca_argmemonly':
-; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 1 pointer values.
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 3 pointer values.
 ; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref   
-; CHECK-NEXT: 1 Unknown instructions:   call void @my_memcpy(i8* %d, i8* %s, i64 1)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref    Pointers: (i8* %d, unknown), (i8* %s, unknown)   
 define void @test_alloca_argmemonly(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @my_memcpy(i8* %d, i8* %s, i64 1)
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_readonly_arg'
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 1 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref       Pointers: (i8* %s, 1)
-; CHECK-NEXT: 1 Unknown instructions:   call void @my_memcpy(i8* %d, i8* %s, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %d, unknown)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Ref       Pointers: (i8* %s, unknown)
 define i8 @test_readonly_arg(i8* noalias %s, i8* noalias %d) {
 entry:
   call void @my_memcpy(i8* %d, i8* %s, i64 1)
   %ret = load i8, i8* %s
   ret i8 %ret
 }
 
 ; CHECK: Alias sets for function 'test_noalias_argmemonly':
-; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 1 pointer values.
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 3 pointer values.
 ; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref   
-; CHECK-NEXT:  Unknown instructions:   call void @my_memmove(i8* %d, i8* %s, i64 1)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref    Pointers: (i8* %d, unknown), (i8* %s, unknown)   
 define void @test_noalias_argmemonly(i8* noalias %a, i8* %s, i8* %d) {
 entry:
   store i8 1, i8* %a, align 1
   call void @my_memmove(i8* %d, i8* %s, i64 1)
   ret void
 }
 
 ; CHECK: Alias sets for function 'test5':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 2 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 3] may alias, Mod/Ref Pointers: (i8* %a, 1), (i8* %b, 1)
-; CHECK-NEXT: 1 Unknown instructions: call void @my_memcpy(i8* %b, i8* %a, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref Pointers: (i8* %a, unknown)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod Pointers: (i8* %b, unknown)
 define void @test5(i8* noalias %a, i8* noalias %b) {
 entry:
   store i8 1, i8* %a, align 1
   call void @my_memcpy(i8* %b, i8* %a, i64 1)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_argcollapse':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 2 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 3] may alias, Mod/Ref Pointers: (i8* %a, 1), (i8* %b, 1)
-; CHECK-NEXT: 1 Unknown instructions: call void @my_memmove(i8* %b, i8* %a, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref Pointers: (i8* %a, unknown)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref Pointers: (i8* %b, unknown)
 define void @test_argcollapse(i8* noalias %a, i8* noalias %b) {
 entry:
   store i8 1, i8* %a, align 1
   call void @my_memmove(i8* %b, i8* %a, i64 1)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_memcpy1':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 0 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref 
-; CHECK-NEXT: 2 Unknown instructions: call void @my_memcpy(i8* %b, i8* %a, i64 1),   call void @my_memcpy(i8* %a, i8* %b, i64 1)
-
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref Pointers: (i8* %b, unknown)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref Pointers: (i8* %a, unknown)
 define void @test_memcpy1(i8* noalias %a, i8* noalias %b) {
 entry:
   call void @my_memcpy(i8* %b, i8* %a, i64 1)
   call void @my_memcpy(i8* %a, i8* %b, i64 1)
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_memset1':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 0 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 1 Unknown instructions: call void @my_memset(i8* %a, i8 0, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 1 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod Pointers: (i8* %a, unknown)
 define void @test_memset1() {
 entry:
   %a = alloca i8, align 1
   call void @my_memset(i8* %a, i8 0, i64 1)
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_memset2':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 0 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 1 Unknown instructions: call void @my_memset(i8* %a, i8 0, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 1 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod Pointers: (i8* %a, unknown)
 define void @test_memset2(i8* %a) {
 entry:
   call void @my_memset(i8* %a, i8 0, i64 1)
   ret void
 }
 
 ; CHECK: Alias sets for function 'test_memset3':
-; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 0 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 2 Unknown instructions:   call void @my_memset(i8* %a, i8 0, i64 1),   call void @my_memset(i8* %b, i8 0, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod Pointers: (i8* %a, unknown), (i8* %b, unknown)
 define void @test_memset3(i8* %a, i8* %b) {
 entry:
   call void @my_memset(i8* %a, i8 0, i64 1)
   call void @my_memset(i8* %b, i8 0, i64 1)
   ret void
 }
 
+;; PICKUP HERE
+
 ; CHECK: Alias sets for function 'test_memset4':
-; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 0 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 1 Unknown instructions:   call void @my_memset(i8* %a, i8 0, i64 1)
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 1 Unknown instructions:   call void @my_memset(i8* %b, i8 0, i64 1)
+; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod Pointers: (i8* %a, unknown)
+; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod Pointers: (i8* %b, unknown)
 define void @test_memset4(i8* noalias %a, i8* noalias %b) {
 entry:
   call void @my_memset(i8* %a, i8 0, i64 1)
   call void @my_memset(i8* %b, i8 0, i64 1)
   ret void
 }
 
 declare void @my_memset(i8* nocapture writeonly, i8, i64) argmemonly
 declare void @my_memcpy(i8* nocapture writeonly, i8* nocapture readonly, i64) argmemonly
 declare void @my_memmove(i8* nocapture, i8* nocapture readonly, i64) argmemonly
 
 
 ; CHECK: Alias sets for function 'test_attribute_intersect':
-; CHECK-NEXT: Alias Set Tracker: 2 alias sets for 1 pointer values.
-; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Mod/Ref
-; CHECK-NEXT: 1 Unknown instructions:   call void @attribute_intersect(i8* %a)
+; CHECK-NEXT: Alias Set Tracker: 1 alias sets for 1 pointer values.
 ; CHECK-NEXT: AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Ref       Pointers: (i8* %a, 1)
 define i8 @test_attribute_intersect(i8* noalias %a) {
 entry:
   ;; This call is effectively readnone since the argument is readonly
   ;; and the function is declared writeonly.  
   call void @attribute_intersect(i8* %a)
   %val = load i8, i8* %a
   ret i8 %val
 }
 
 declare void @attribute_intersect(i8* readonly) argmemonly writeonly
 

test/Transforms/LICM/argmemonly-call.ll

loop:
   %val = load i32, i32* %loc2
   store i32 %val, i32* %loc
   %dest = bitcast i32* %loc to i8*
   %src = bitcast i32* %loc2 to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 8, i1 false)
   br label %loop
 }
 
-; FIXME: argument aliasing should let us do this transform
 define void @test7(i32* noalias %loc, i32* noalias %loc2) {
 ; CHECK-LABEL: @test7
-; CHECK-LABEL: loop:
 ; CHECK: %val = load i32, i32* %loc2
+; CHECK-LABEL: loop:
 ; CHECK: @custom_memcpy
   br label %loop
 
 loop:
   %val = load i32, i32* %loc2
   store i32 %val, i32* %loc
   %dest = bitcast i32* %loc to i8*
   %src = bitcast i32* %loc2 to i8*
   call void @custom_memcpy(i8* %dest, i8* %src)
   br label %loop
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1)
 declare void @custom_memcpy(i8* nocapture writeonly, i8* nocapture readonly) argmemonly nounwind