[BasicAA] Take attributes into account when requesting modref info for a call site

[igor-laevsky]

Summary

When requesting modref information between call site and memory location we will bailout with MRI_ModRef result if one of the nocapture, byval or operand bundle attributes aliases target location. However we can improve this decision by taking into account operand attributes. If for example we know that aliasing operand is readonly we should only infer MRI_Ref.

This is important for targets with heavy use of the deopt operand bundles since they imply readonly attribute for their pointers.

@davide, after this change llvm successfully compiles NewGVN/readattrs.ll test case. Overall this looks like a desired effect but I'm not completely certain. Can you take a look please?

[• dberlin]

lib/Analysis/BasicAliasAnalysis.cpp

884

Uh?

[davide]

test/Transforms/NewGVN/readattrs.ll

1–3

The fact this test passes now is actually good, but I'd like to understand why it was failing before and now it's not. Can you please elaborate?

[igor-laevsky]

lib/Analysis/BasicAliasAnalysis.cpp

884

Idea here is to intersect smarts from AAResultBase with the result we've received in this function. I'm actually not certain if this is needed since "AAResults" does intersect results from all alias analyses. Plus AAResultBase currently doesn't have any smarts. So, yes, I'm not sure if we need this operation.

test/Transforms/NewGVN/readattrs.ll

1–3

This test passes local non-escaping object as a readonly nocapture function argument. Before my change alias analysis would have ignored readonly argument and concluded that call modifies "%a". I suspect that old GVN might use some internal smarts to determine that "%a" is unmodified by the call, while NewGVN relies on the alias analysis.

[• dberlin]

I see what is happening.
Memdep gets a modref answer from AA, so it uses callCapturesBefore and then uses that instead.

I'm fine with having AA do this in modref, or using callCapturesBefore in MemorySSA.

Given that the related code says:
"/ FIXME: this is really just shoring-up a deficiency in alias analysis.
/ BasicAA isn't willing to spend linear time determining whether an alloca
/ was captured before or after this particular call, while we are. However,
/ with a smarter AA in place, this test is just wasting compile time."

we may just want to go ahead with basicaa ;)

[• dberlin]

lib/Analysis/BasicAliasAnalysis.cpp

784

Can you explain why you need static casts here and below?

[igor-laevsky]

lib/Analysis/BasicAliasAnalysis.cpp

784

This is to be in sync with similar places in this file. I don't really have a preference on how to convert this values.

[reames]

This change looks entirely correct, but I think it could simplify greatly by removing the merging logic. Unless that's needed (test case required), we should simplify.

... actually, after think a bit longer, I'm pretty sure the merging is required for the DSE case. I'll let you find the test case and explanation to justify why. :)

lib/Analysis/BasicAliasAnalysis.cpp

747

Given we don't refine this (after suggested change described below) outside of the block we should sink this into the if block.

768

It looks like most of the merging here is only needed for the fall through logic? If we remove that, doesn't this simplify greatly.

884

I believe this can be removed. Or at least, if it can't, it definitely warrants a patch of it's own. :)

[igor-laevsky]

I had removed confusing merging logic. It was there only to assist with possible improvements of the mod ref info during execution of the 'getModRefInfo' function. But since there are no known examples of when this is valuable, adding extra complexity doesn't worth it.

[reames]

LGTM

include/llvm/IR/CallSite.h

bool doesNotAccessMemory(unsigned OpNo) const {
     return dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
   }
 
   bool onlyReadsMemory(unsigned OpNo) const {
     return dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadOnly) ||
            dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
   }
 
+  bool doesNotReadMemory(unsigned OpNo) const {
+    return dataOperandHasImpliedAttr(OpNo + 1, Attribute::WriteOnly) ||
+           dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
+  }
+
   /// Return true if the return value is known to be not null.
   /// This may be because it has the nonnull attribute, or because at least
   /// one byte is dereferenceable and the pointer is in addrspace(0).
   bool isReturnNonNull() const {
     if (paramHasAttr(0, Attribute::NonNull))
       return true;
     else if (getDereferenceableBytes(0) > 0 &&
              getType()->getPointerAddressSpace() == 0)

lib/Analysis/BasicAliasAnalysis.cpp

ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
   // We cannot exclude byval arguments here; these belong to the caller of
   // the current function not to the current function, and a tail callee
   // may reference them.
   if (isa<AllocaInst>(Object))
     if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
       if (CI->isTailCall())
         return MRI_NoModRef;
 
   // If the pointer is to a locally allocated object that does not escape,
   // then the call can not mod/ref the pointer unless the call takes the pointer
   // as an argument, and itself doesn't capture it.
   if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
       isNonEscapingLocalObject(Object)) {
-    bool PassedAsArg = false;
+
+    // Optimistically assume that call doesn't touch Object and check this
+    // assumption in the following loop.
+    ModRefInfo Result = MRI_NoModRef;
+
     unsigned OperandNo = 0;
     for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
          CI != CE; ++CI, ++OperandNo) {
       // Only look at the no-capture or byval pointer arguments.  If this
       // pointer were passed to arguments that were neither of these, then it
       // couldn't be no-capture.
       if (!(*CI)->getType()->isPointerTy() ||
           (!CS.doesNotCapture(OperandNo) &&
            OperandNo < CS.getNumArgOperands() && !CS.isByValArgument(OperandNo)))
         continue;
 
+      // Call doesn't access memory through this operand, so we don't care
+      // if it aliases with Object.
+      if (CS.doesNotAccessMemory(OperandNo))
+        continue;
+
       // If this is a no-capture pointer argument, see if we can tell that it
-      // is impossible to alias the pointer we're checking.  If not, we have to
-      // assume that the call could touch the pointer, even though it doesn't
-      // escape.
+      // is impossible to alias the pointer we're checking.
       AliasResult AR =
           getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object));
-      if (AR) {
-        PassedAsArg = true;
-        break;
+
+      // Operand doesnt alias 'Object', continue looking for other aliases
+      if (AR == NoAlias)
+        continue;
+      // Operand aliases 'Object', but call doesn't modify it. Strengthen
+      // initial assumption and keep looking in case if there are more aliases.
+      if (CS.onlyReadsMemory(OperandNo)) {
+        Result = static_cast<ModRefInfo>(Result | MRI_Ref);
+        continue;
+      }
+      // Operand aliases 'Object' but call only writes into it.
+      if (CS.doesNotReadMemory(OperandNo)) {
+        Result = static_cast<ModRefInfo>(Result | MRI_Mod);
+        continue;
       }
+      // This operand aliases 'Object' and call reads and writes into it.
+      Result = MRI_ModRef;
+      break;
     }
 
-    if (!PassedAsArg)
-      return MRI_NoModRef;
+    // Early return if we improved mod ref information
+    if (Result != MRI_ModRef)
+      return Result;
   }
 
   // If the CallSite is to malloc or calloc, we can assume that it doesn't
   // modify any IR visible value.  This is only valid because we assume these
   // routines do not read values visible in the IR.  TODO: Consider special
   // casing realloc and strdup routines which access only their arguments as
   // well.  Or alternatively, replace all of this with inaccessiblememonly once
   // that's implemented fully. 
ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
   //
   // The transformation will cause the second store to be ignored (based on
   // rules of invariant.start)  and print 40, while the first program always
   // prints 50.
   if (isIntrinsicCall(CS, Intrinsic::invariant_start))
     return MRI_Ref;
 
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(CS, Loc);
 }
 
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
                                         ImmutableCallSite CS2) {
   // While the assume intrinsic is marked as arbitrarily writing so that
   // proper control dependencies will be maintained, it never aliases any
   // particular memory location.
   if (isIntrinsicCall(CS1, Intrinsic::assume) ||

test/Analysis/BasicAA/call-attrs.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare void @readonly_attr(i8* readonly nocapture)
+declare void @writeonly_attr(i8* writeonly nocapture)
+declare void @readnone_attr(i8* readnone nocapture)
+
+declare void @readonly_func(i8* nocapture) readonly
+declare void @writeonly_func(i8* nocapture) writeonly
+declare void @readnone_func(i8* nocapture) readnone
+
+declare void @read_write(i8* writeonly nocapture, i8* readonly nocapture, i8* readnone nocapture)
+
+declare void @func()
+
+define void @test(i8* noalias %p) {
+entry:
+  call void @readonly_attr(i8* %p)
+  call void @readonly_func(i8* %p)
+
+  call void @writeonly_attr(i8* %p)
+  call void @writeonly_func(i8* %p)
+
+  call void @readnone_attr(i8* %p)
+  call void @readnone_func(i8* %p)
+
+  call void @read_write(i8* %p, i8* %p, i8* %p)
+
+  call void @func() ["deopt" (i8* %p)]
+  call void @writeonly_attr(i8* %p) ["deopt" (i8* %p)]
+
+  ret void
+}
+
+; CHECK:  Just Ref:  Ptr: i8* %p  <->  call void @readonly_attr(i8* %p)
+; CHECK:  Just Ref:  Ptr: i8* %p  <->  call void @readonly_func(i8* %p)
+; CHECK:  Just Mod:  Ptr: i8* %p  <->  call void @writeonly_attr(i8* %p)
+; CHECK:  Just Mod:  Ptr: i8* %p  <->  call void @writeonly_func(i8* %p)
+; CHECK:  NoModRef:  Ptr: i8* %p  <->  call void @readnone_attr(i8* %p)
+; CHECK:  NoModRef:  Ptr: i8* %p  <->  call void @readnone_func(i8* %p)
+; CHECK:  Both ModRef:  Ptr: i8* %p <->  call void @read_write(i8* %p, i8* %p, i8* %p)
+; CHECK:  Just Ref:  Ptr: i8* %p  <->  call void @func() [ "deopt"(i8* %p) ]
+; CHECK:  Both ModRef:  Ptr: i8* %p <->  call void @writeonly_attr(i8* %p) [ "deopt"(i8* %p) ]

test/Transforms/NewGVN/readattrs.ll

-; XFAIL: *
 ; RUN: opt -newgvn -S -o - < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @use(i8* readonly nocapture)
 
 define i8 @test() {
   %a = alloca i8
   store i8 1, i8* %a
   call void @use(i8* %a)
   %b = load i8, i8* %a
   ret i8 %b
 ; CHECK-LABEL: define i8 @test(
 ; CHECK: call void @use(i8* %a)
 ; CHECK-NEXT: ret i8 1
 }