[CFLAA] Add support for getModRefInfo() in CFL-AA

[grievejia]

Summary

Previously, CFL-AA always says "ModRef" to any getModRefInfo() queries. This patch makes CFL-AA returns slightly better answers.

The precision increase is less than I originally expected. The biggest problem here is that we don't distinguish reads from writes in our analysis (it's also useless to make the distinction, since the value we read from and the value we write to are very likely to be merged together anyway, if there's a direct/indirect assignment). Therefore, all I can do here is to return NoModRef in certain special cases, and try to be conservative otherwise.

[george.burgess.iv]

LGTM -- thanks for the patch!

llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.h

AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
 
     AliasResult QueryResult = query(LocA, LocB);
     if (QueryResult == MayAlias)
       return AAResultBase::alias(LocA, LocB);
 
     return QueryResult;
   }
 
+  /// Get the location associated with a pointer argument of a callsite.
+  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
+
+  /// Returns the behavior when calling the given call site.
+  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
+
+  /// Returns the behavior when calling the given function. For use when the
+  /// call site is not known.
+  FunctionModRefBehavior getModRefBehavior(const Function *F);
+
 private:
   struct FunctionHandle final : public CallbackVH {
     FunctionHandle(Function *Fn, CFLAAResult *Result)
         : CallbackVH(Fn), Result(Result) {
       assert(Fn != nullptr);
       assert(Result != nullptr);
     }
 

llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp

if (AttrsA.none() || AttrsB.none())
     return NoAlias;
   if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB))
     return MayAlias;
   if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
     return MayAlias;
   return NoAlias;
 }
 
+ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS,
+                                         unsigned ArgIdx) {
+  if (auto CalledFunc = CS.getCalledFunction()) {
+    auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
+    if (!MaybeInfo.hasValue())
+      return MRI_ModRef;
+    auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
+    auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+
+    bool ArgAttributeIsWritten =
+        std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(),
+                    [ArgIdx](const ExternalAttribute &ExtAttr) {
+                      return ExtAttr.IValue.Index == ArgIdx + 1;
+                    });
+    bool ArgIsAccessed =
+        std::any_of(RetParamRelations.begin(), RetParamRelations.end(),
+                    [ArgIdx](const ExternalRelation &ExtRelation) {
+                      return ExtRelation.To.Index == ArgIdx + 1 ||
+                             ExtRelation.From.Index == ArgIdx + 1;
+                    });
+
+    return (!ArgIsAccessed && !ArgAttributeIsWritten) ? MRI_NoModRef
+                                                      : MRI_ModRef;
+  }
+
+  return MRI_ModRef;
+}
+
+FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) {
+  // If we know the callee, try analyzing it
+  if (auto CalledFunc = CS.getCalledFunction())
+    return getModRefBehavior(CalledFunc);
+
+  // Otherwise, be conservative
+  return FMRB_UnknownModRefBehavior;
+}
+
+FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) {
+  assert(F != nullptr);
+
+  // TODO: Remove the const_cast
+  auto &MaybeInfo = ensureCached(const_cast<Function *>(F));
+  if (!MaybeInfo.hasValue())
+    return FMRB_UnknownModRefBehavior;
+  auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
+  auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+
+  // First, if any argument is marked Escpaed, Unknown or Global, anything may
+  // happen to them and thus we can't draw any conclusion.
+  if (!RetParamAttributes.empty())
+    return FMRB_UnknownModRefBehavior;
+
+  // Currently we don't (and can't) distinguish reads from writes in
+  // RetParamRelations. All we can say is whether there may be memory access or
+  // not.
+  if (RetParamRelations.empty())
+    return FMRB_DoesNotAccessMemory;
+
+  // Check if something beyond argmem gets touched.
+  bool AccessArgMemoryOnly =
+      std::all_of(RetParamRelations.begin(), RetParamRelations.end(),
+                  [](const ExternalRelation &ExtRelation) {
+                    // Both DerefLevels has to be 0, since we don't know which
+                    // one is a read and which is a write.
+                    return ExtRelation.From.DerefLevel == 0 &&
+                           ExtRelation.To.DerefLevel == 0;
+                  });
+  return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees
+                             : FMRB_UnknownModRefBehavior;
+}
+
 char CFLAA::PassID;
 
 CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) {
   return CFLAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char CFLAAWrapperPass::ID = 0;
 INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false,

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll

 ; This testcase ensures that CFL AA answers queries soundly when callee tries 
 ; to return one of its parameters
 
 ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 
 define i32* @return_arg_callee(i32* %arg1, i32* %arg2) {
   ret i32* %arg1
 }
 ; CHECK-LABEL: Function: test_return_arg
 ; CHECK: NoAlias: i32* %a, i32* %b
 ; CHECK: MayAlias: i32* %a, i32* %c
 ; CHECK: NoAlias: i32* %b, i32* %c
+
+; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
 define void @test_return_arg() {
   %a = alloca i32, align 4
   %b = alloca i32, align 4
 
   %c = call i32* @return_arg_callee(i32* %a, i32* %b)
 
   ret void
 }
 No newline at end of file