[CFLAA] Add getModRefBehavior() support to CFLAnders

[grievejia]

Summary

This patch adds several getModRefBehavior() overloads to CFLAnders.

Hopefully this patch will make CFLAnders communicate better with its clients. I'd like to commit this patch in before dong any benchmarking work since it may help me get better numbers :)

[george.burgess.iv]

Two nits, because people tend to do cleanups to llvm's range algos. Otherwise, LGTM. Thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp

873

Nit: llvm::any_of(RetParamAttributes, lambda) (and the two others below)

934

Nit: any_of(RetParamRelations, lambda) (and below, for all_of)

[grievejia]

Use llvm range API instead.

Also, fix CFLSteens that was accidentally broken in the last version of the path.

include/llvm/Analysis/CFLAndersAliasAnalysis.h

public:
 
   /// \brief Get the alias summary for the given function
   /// Return nullptr if the summary is not found or not available
   const cflaa::AliasSummary *getAliasSummary(const Function &);
 
   AliasResult query(const MemoryLocation &, const MemoryLocation &);
   AliasResult alias(const MemoryLocation &, const MemoryLocation &);
 
+  /// 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, CFLAndersAAResult *Result)
         : CallbackVH(Fn), Result(Result) {
       assert(Fn != nullptr);
       assert(Result != nullptr);
     }
 

lib/Analysis/CFLAndersAliasAnalysis.cpp

AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
 
   AliasResult QueryResult = query(LocA, LocB);
   if (QueryResult == MayAlias)
     return AAResultBase::alias(LocA, LocB);
 
   return QueryResult;
 }
 
+ModRefInfo CFLAndersAAResult::getArgModRefInfo(ImmutableCallSite CS,
+                                               unsigned ArgIdx) {
+  if (auto CalledFunc = CS.getCalledFunction()) {
+    if (!CalledFunc->hasExactDefinition())
+      return MRI_ModRef;
+
+    auto &MaybeInfo = ensureCached(*CalledFunc);
+    if (!MaybeInfo.hasValue())
+      return MRI_ModRef;
+    auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
+    auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
+
+    bool ArgAttributeIsWritten =
+        any_of(RetParamAttributes, [ArgIdx](const ExternalAttribute &ExtAttr) {
+          return ExtAttr.IValue.Index == ArgIdx + 1;
+        });
+
+    // If the argument is unknown, escaped, or alias global, be conservative.
+    // FIXME: Do we really need to be conservative for AttrGlobal?
+    if (ArgAttributeIsWritten)
+      return MRI_ModRef;
+
+    bool ArgIsRead = any_of(RetParamRelations,
+                            [ArgIdx](const ExternalRelation &ExtRelation) {
+                              return ExtRelation.From.Index == ArgIdx + 1;
+                            });
+
+    bool ArgIsWritten = any_of(RetParamRelations,
+                               [ArgIdx](const ExternalRelation &ExtRelation) {
+                                 return ExtRelation.To.Index == ArgIdx + 1;
+                               });
+
+    if (ArgIsRead)
+      return ArgIsWritten ? MRI_ModRef : MRI_Ref;
+    return ArgIsWritten ? MRI_Mod : MRI_NoModRef;
+  }
+
+  return MRI_ModRef;
+}
+
+FunctionModRefBehavior
+CFLAndersAAResult::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 CFLAndersAAResult::getModRefBehavior(const Function *F) {
+  assert(F != nullptr);
+
+  // We cannot process external functions
+  if (!F->hasExactDefinition())
+    return FMRB_UnknownModRefBehavior;
+
+  auto &MaybeInfo = ensureCached(*F);
+  if (!MaybeInfo.hasValue())
+    return FMRB_UnknownModRefBehavior;
+  auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
+  auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
+
+  // First, if any argument is marked Escpaed, Unknown or Global, anything may
+  // happen to them and thus we can't draw any conclusion.
+  // FIXME: Do we really need to be conservative for AttrGlobal?
+  if (!RetParamAttributes.empty())
+    return FMRB_UnknownModRefBehavior;
+
+  // Check if memory gets touched.
+  bool MemIsRead =
+      any_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+        return ExtRelation.From.DerefLevel > 0;
+      });
+  bool MemIsWritten =
+      any_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+        return ExtRelation.To.DerefLevel > 0;
+      });
+  if (!MemIsRead && !MemIsWritten)
+    return FMRB_DoesNotAccessMemory;
+
+  // Check if only argmem gets touched.
+  bool ArgMemIsAccessed =
+      all_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+        return ExtRelation.From.Index > 0 && ExtRelation.From.DerefLevel <= 1 &&
+               ExtRelation.To.Index > 0 && ExtRelation.To.DerefLevel <= 1;
+      });
+  if (ArgMemIsAccessed)
+    return FMRB_OnlyAccessesArgumentPointees;
+
+  if (!MemIsWritten) {
+    // Check if something beyond argmem gets read.
+    bool ArgMemReadOnly =
+        all_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+          return ExtRelation.From.Index > 0 && ExtRelation.From.DerefLevel <= 1;
+        });
+    return ArgMemReadOnly ? FMRB_OnlyReadsArgumentPointees
+                          : FMRB_OnlyReadsMemory;
+  }
+
+  if (!MemIsRead)
+    return FMRB_DoesNotReadMemory;
+
+  return FMRB_UnknownModRefBehavior;
+}
+
 char CFLAndersAA::PassID;
 
 CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager<Function> &AM) {
   return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char CFLAndersAAWrapperPass::ID = 0;
 INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",

lib/Analysis/CFLSteensAliasAnalysis.cpp

AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
   if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
     return MayAlias;
   return NoAlias;
 }
 
 ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS,
                                                unsigned ArgIdx) {
   if (auto CalledFunc = CS.getCalledFunction()) {
+    if (!CalledFunc->hasExactDefinition())
+      return MRI_ModRef;
+
     auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
     if (!MaybeInfo.hasValue())
       return MRI_ModRef;
     auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
     auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
 
     bool ArgAttributeIsWritten =
         std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(),
CFLSteensAAResult::getModRefBehavior(ImmutableCallSite CS) {
 
   // Otherwise, be conservative
   return FMRB_UnknownModRefBehavior;
 }
 
 FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) {
   assert(F != nullptr);
 
+  // We cannot process external functions
+  if (!F->hasExactDefinition())
+    return FMRB_UnknownModRefBehavior;
+
   // TODO: Remove the const_cast
   auto &MaybeInfo = ensureCached(const_cast<Function *>(F));
   if (!MaybeInfo.hasValue())
     return FMRB_UnknownModRefBehavior;
   auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
   auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
 
   // 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())
+  bool AccessNoMemory =
+      all_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+        return ExtRelation.From.DerefLevel == 0 &&
+               ExtRelation.To.DerefLevel == 0;
+      });
+  if (AccessNoMemory)
     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;
-                  });
+      all_of(RetParamRelations, [](const ExternalRelation &ExtRelation) {
+        return ExtRelation.From.Index > 0 && ExtRelation.To.Index > 0 &&
+               ExtRelation.From.DerefLevel <= 1 &&
+               ExtRelation.To.DerefLevel <= 1;
   return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees
                              : FMRB_UnknownModRefBehavior;
 }
 
 char CFLSteensAA::PassID;
 
 CFLSteensAAResult CFLSteensAA::run(Function &F, AnalysisManager<Function> &AM) {
   return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));

test/Analysis/CFLAliasAnalysis/Andersen/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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=cfl-anders-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* %a <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
+; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
+; CHECK: NoModRef: Ptr: i32* %c <-> %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

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll

 ; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp
 ; CHECK: MayAlias: i32* %a, i32* %lp
 ; CHECK: NoAlias: i32* %b, i32* %lp
 ; CHECK: NoAlias: i32* %lp, i32** %p
 ; CHECK: NoAlias: i32* %lp, i32*** %pp
 ; CHECK: MayAlias: i32* %c, i32* %lp
 ; CHECK: NoAlias: i32* %lp, i32** %lpp
 ; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
+
+; CHECK: Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
+; CHECK: Just Ref: Ptr: i32*** %pp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
+; CHECK: Just Ref: Ptr: i32** %lpp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
+
 define void @test_return_deref_arg_multilevel() {
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %p = alloca i32*, align 8
   %pp = alloca i32**, align 8
 
   store i32* %a, i32** %p
   store i32** %p, i32*** %pp
   %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
 
   %lpp = load i32**, i32*** %pp
   %lpp_deref = load i32*, i32** %lpp
   %lp = load i32*, i32** %p
 
   ret void
 }
 No newline at end of file

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll

 ; CHECK-LABEL: Function: test_return_deref_arg
 ; CHECK: NoAlias: i32* %a, i32* %b
 ; CHECK: MayAlias: i32* %a, i32* %c
 ; CHECK: NoAlias: i32* %b, i32* %c
 ; CHECK: MayAlias: i32* %a, i32* %lp
 ; CHECK: NoAlias: i32* %b, i32* %lp
 ; CHECK: NoAlias: i32* %lp, i32** %p
 ; CHECK: MayAlias: i32* %c, i32* %lp
+
+; CHECK: NoModRef: Ptr: i32* %a <-> %c = call i32* @return_deref_arg_callee(i32** %p)
+; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_deref_arg_callee(i32** %p)
+; CHECK: Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_callee(i32** %p)
+; CHECK: NoModRef: Ptr: i32* %c <-> %c = call i32* @return_deref_arg_callee(i32** %p)
+; CHECK: NoModRef: Ptr: i32* %lp <-> %c = call i32* @return_deref_arg_callee(i32** %p)
 define void @test_return_deref_arg() {
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %p = alloca i32*, align 8
 
   store i32* %a, i32** %p
   %c = call i32* @return_deref_arg_callee(i32** %p)
 
   %lp = load i32*, i32** %p
 
   ret void
 }
 No newline at end of file

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll

 ; CHECK: NoAlias: i32** %lb, i32*** %b
 ; CHECK: MayAlias: i32* %a, i32* %lb_deref
 ; CHECK: NoAlias: i32* %lb_deref, i32** %lpp
 ; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref
 ; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp
 ; CHECK: MayAlias: i32* %lb_deref, i32* %lp
 ; CHECK: NoAlias: i32* %lp, i32** %lpp
 ; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
+
+; CHECK: Just Mod: Ptr: i32*** %b <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
+; CHECK: Just Mod: Ptr: i32** %lb <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
 define void @test_return_ref_arg_multilevel() {
   %a = alloca i32, align 4
   %p = alloca i32*, align 8
   %pp = alloca i32**, align 8
 
   store i32* %a, i32** %p
   store i32** %p, i32*** %pp
   %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
 
   %lb = load i32**, i32*** %b
   %lb_deref = load i32*, i32** %lb
   %lpp = load i32**, i32*** %pp
   %lpp_deref = load i32*, i32** %lpp
   %lp = load i32*, i32** %p
 
   ret void
 }
 No newline at end of file

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll

 ; CHECK-LABEL: Function: test_return_ref_arg
 ; CHECK: NoAlias: i32** %b, i32** %p
 ; CHECK: MayAlias: i32* %a, i32* %lb
 ; CHECK: NoAlias: i32* %lb, i32** %p
 ; CHECK: NoAlias: i32* %lb, i32** %b
 ; CHECK: NoAlias: i32* %lp, i32** %p
 ; CHECK: NoAlias: i32* %lp, i32** %b
 ; CHECK: MayAlias: i32* %lb, i32* %lp
+
+; CHECK: Just Mod: Ptr: i32** %b <-> %b = call i32** @return_ref_arg_callee(i32* %a)
 define void @test_return_ref_arg() {
   %a = alloca i32, align 4
   %p = alloca i32*, align 8
 
   store i32* %a, i32** %p
   %b = call i32** @return_ref_arg_callee(i32* %a)
 
   %lb = load i32*, i32** %b
   %lp = load i32*, i32** %p
 
   ret void
 }
 No newline at end of file

test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.ll

 ; CHECK: NoAlias: i32* %a, i32* %b
 ; CHECK: NoAlias: i32* %a, i32** %p
 ; CHECK: NoAlias: i32* %b, i32** %p
 ; CHECK: MayAlias: i32* %a, i32* %lp
 ; CHECK: MayAlias: i32* %b, i32* %lp
 ; CHECK: NoAlias: i32* %a, i32* %lq
 ; CHECK: MayAlias: i32* %b, i32* %lq
 ; CHECK: MayAlias: i32* %lp, i32* %lq
+
+; CHECK: NoModRef: Ptr: i32* %a <-> call void @store_arg_callee(i32** %p, i32* %b)
+; CHECK: Just Ref: Ptr: i32* %b <-> call void @store_arg_callee(i32** %p, i32* %b)
+; CHECK: Just Mod: Ptr: i32** %p  <-> call void @store_arg_callee(i32** %p, i32* %b)
+; CHECK: NoModRef: Ptr: i32** %q  <-> call void @store_arg_callee(i32** %p, i32* %b)
 define void @test_store_arg() {
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %p = alloca i32*, align 8
   %q = alloca i32*, align 8
 
   store i32* %a, i32** %p
   store i32* %b, i32** %q
   call void @store_arg_callee(i32** %p, i32* %b)
 
   %lp = load i32*, i32** %p
   %lq = load i32*, i32** %q
 
   ret void
 }
 No newline at end of file