[GlobalsAA] Teach GlobalsAA about nocapture

[jmolloy]

Summary

Arguments to function calls marked "nocapture" can be marked as
non-escaping. However, nocapture is defined in terms of the lifetime
of the callee, and if the callee can directly or indirectly recurse to
the caller, the semantics of nocapture are invalid.

Therefore, we eagerly discover all known non-recursive functions and
then, in AnalyzeUsesOfPointer() we can query that set for nocapture
arguments.

This means that we can't be so optimistic in
getModRefInfo(ImmutableCallsite) - previously we assumed all call
arguments never aliased with an escaping global. Now we need to check,
because a global could now be passed as an argument but still not
escape.

This also solves a related conformance problem: MemCpyOptimizer can
turn non-escaping stores of globals into calls to intrinsics like
llvm.memcpy/llvm/memset. This confuses GlobalsAA, which knows the
global can't escape and so returns NoModRef when queried, when
obviously a memcpy/memset call does indeed reference and modify its
arguments.

This addresses PR24800, PR24801, and PR24802

[aadg]

Hi James,

See comment below.

lib/Analysis/GlobalsModRef.cpp

806–812

Shouldn't we also handle the isVolatile argument ? As anything could happen when this is a volatile operation, I think we should always return MRI_ModRef when it is set.

[hfinkel]

Actually, I wonder if the right solution here is somewhat more general. As I recall, generally speaking, GMR cannot use 'nocapture' attributes on functions parameters because:

1. It cannot use nocapture on the parent function's arguments because nocapture is a statement only about appearances to the caller, not a guarantee about what happens inside the function itself.
2. It cannot use nocapture on attributes on the call instructions because it is possible that the function is directly or indirectly recursive, and so (1) applies.

And, so, we can honor nocapture for any function calls which we can prove are not directly or indirectly recursive with the current function. This seems like something we could do given that we have a callgraph, and perhaps can assert more generally for all intrinsics?

lib/Analysis/GlobalsModRef.cpp

806–812

I agree with James's response (from the list, which is seems did not make it into Phabricator); volatility and aliasing are orthogonal concepts, and while we do imply aliasing affects to volatile operations (and atomics) in various places (for reasons that I'm sure seemed convenient at the time), it is really not a good thing, and I see no reason to do so here.

[sanjoy]

lib/Analysis/GlobalsModRef.cpp

801

I'd rather have this be a lambda that takes an argument index instead of an eagerly populated vector, given that for most intrinsics this isn't used.

806

Can we do something more precise here if the intrinsic is readonly or readnone?

[aadg]

lib/Analysis/GlobalsModRef.cpp

806–812

Ok, I agree checking the volatileness should not be done here, but at the place where the aliasing information is used.

[jmolloy]

Hi all,

Updated diff addressing Sanjoy's comments.

Cheers,

James

[jmolloy]

And update the test to specifically enable GMR in the pass pipeline now the switch has been flipped off again.

[jmolloy]

Hi Hal,

OK, what you said makes sense. I've updated this patch to handle nocapture properly, which indeed is a superset of the functionality in the previous patch.

Cheers,

James

[hfinkel]

I think that the check that you would really want to do is: are the caller and the callee in the same connected component? Can you cache enough information from the CallGraphSCC iteration to check that directly?

[jmolloy]

Hi Hal,

That makes sense, it'd be less conservative. This updated patch does that - it iterates through the SCCs, assigning a numeric ID to each and storing a map of Function -> SCC ID that we can query later.

Cheers,

James

[jmolloy]

Hi Hal,

Did you have any more comments on this?

Cheers,

James

[hfinkel]

lib/Analysis/GlobalsModRef.cpp

807

This check does not seem conservative enough. GetUnderlyingObject has a depth limit, and cannot look through PHIs/selects. Since we know that GV is not captured as a precondition of this function (which we should explicitly document), calling GetUnderlyingObjects with no depth limit might be conservatively correct, although I'm afraid of unbounded compile-time in that case, Alternatively, you can call GetUnderlyingObject (or better, GetUnderlyingObjects), but return conservatively if not all returned objects are such that isIdentifiedObject returns true.

[jmolloy]

Hi Hal,

That makes total sense. This new patch makes sure all objects were identified and if not, returns ConservativeResult.

Cheers,

James

[hfinkel]

LGTM.

[jmolloy]

Thanks, r248576.

include/llvm/Analysis/GlobalsModRef.h

class GlobalsAAResult : public AAResultBase<GlobalsAAResult> {
 
   /// AllocsForIndirectGlobals - If an instruction allocates memory for an
   /// indirect global, this map indicates which one.
   DenseMap<const Value *, const GlobalValue *> AllocsForIndirectGlobals;
 
   /// For each function, keep track of what globals are modified or read.
   DenseMap<const Function *, FunctionInfo> FunctionInfos;
 
+  /// A map of functions to SCC. The SCCs are described by a simple integer
+  /// ID that is only useful for comparing for equality (are two functions
+  /// in the same SCC or not?)
+  DenseMap<const Function *, unsigned> FunctionToSCCMap;
+  
   /// Handle to clear this analysis on deletion of values.
   struct DeletionCallbackHandle final : CallbackVH {
     GlobalsAAResult *GAR;
     std::list<DeletionCallbackHandle>::iterator I;
 
     DeletionCallbackHandle(GlobalsAAResult &GAR, Value *V)
         : CallbackVH(V), GAR(&GAR) {}
 
private:
 
   void AnalyzeGlobals(Module &M);
   void AnalyzeCallGraph(CallGraph &CG, Module &M);
   bool AnalyzeUsesOfPointer(Value *V,
                             SmallPtrSetImpl<Function *> *Readers = nullptr,
                             SmallPtrSetImpl<Function *> *Writers = nullptr,
                             GlobalValue *OkayStoreDest = nullptr);
   bool AnalyzeIndirectGlobalMemory(GlobalValue *GV);
+  void CollectSCCMembership(CallGraph &CG);
   
   bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V);
+  ModRefInfo getModRefInfoForArgument(ImmutableCallSite CS,
+                                      const GlobalValue *GV);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class GlobalsAA {
 public:
   typedef GlobalsAAResult Result;
 
   /// \brief Opaque, unique identifier for this analysis pass.

lib/Analysis/GlobalsModRef.cpp

for (Use &U : V->uses()) {
     } else if (auto CS = CallSite(I)) {
       // Make sure that this is just the function being called, not that it is
       // passing into the function.
       if (!CS.isCallee(&U)) {
         // Detect calls to free.
         if (isFreeCall(I, &TLI)) {
           if (Writers)
             Writers->insert(CS->getParent()->getParent());
+        } else if (CS.doesNotCapture(CS.getArgumentNo(&U))) {
+          Function *ParentF = CS->getParent()->getParent();
+          // A nocapture argument may be read from or written to, but does not
+          // escape unless the call can somehow recurse.
+          //
+          // nocapture "indicates that the callee does not make any copies of
+          // the pointer that outlive itself". Therefore if we directly or
+          // indirectly recurse, we must treat the pointer as escaping.
+          if (FunctionToSCCMap[ParentF] ==
+              FunctionToSCCMap[CS.getCalledFunction()])
+            return true;
+          if (Readers)
+            Readers->insert(ParentF);
+          if (Writers)
+            Writers->insert(ParentF);
         } else {
           return true; // Argument of an unknown call.
         }
       }
     } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
         return true; // Allow comparison against null.
     } else {
while (!AllocRelatedValues.empty()) {
     AllocRelatedValues.pop_back();
   }
   IndirectGlobals.insert(GV);
   Handles.emplace_front(*this, GV);
   Handles.front().I = Handles.begin();
   return true;
 }
 
+void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {  
+  // We do a bottom-up SCC traversal of the call graph.  In other words, we
+  // visit all callees before callers (leaf-first).
+  unsigned SCCID = 0;
+  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
+    const std::vector<CallGraphNode *> &SCC = *I;
+    assert(!SCC.empty() && "SCC with no functions?");
+
+    for (auto *CGN : SCC)
+      if (Function *F = CGN->getFunction())
+        FunctionToSCCMap[F] = SCCID;
+    ++SCCID;
+  }
+}
+
 /// AnalyzeCallGraph - At this point, we know the functions where globals are
 /// immediately stored to and read from.  Propagate this information up the call
 /// graph to all callers and compute the mod/ref info for all memory for each
 /// function.
 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
   // We do a bottom-up SCC traversal of the call graph.  In other words, we
   // visit all callees before callers (leaf-first).
   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA,
   // This does not appear to be a common problem in practice.
   if (EnableUnsafeGlobalsModRefAliasResults)
     if ((GV1 || GV2) && GV1 != GV2)
       return NoAlias;
 
   return AAResultBase::alias(LocA, LocB);
 }
 
+ModRefInfo GlobalsAAResult::getModRefInfoForArgument(ImmutableCallSite CS,
+                                                     const GlobalValue *GV) {
+  if (CS.doesNotAccessMemory())
+    return MRI_NoModRef;
+  ModRefInfo ConservativeResult = CS.onlyReadsMemory() ? MRI_Ref : MRI_ModRef;
+  
+  // Iterate through all the arguments to the called function. If any argument
+  // is based on GV, return the conservative result.
+  for (auto &A : CS.args()) {
+    SmallVector<Value*, 4> Objects;
+    GetUnderlyingObjects(A, Objects, DL);
+    
+    // All objects must be identified.
+    if (!std::all_of(Objects.begin(), Objects.end(), [&GV](const Value *V) {
+          return isIdentifiedObject(V);
+        }))
+      return ConservativeResult;
+
+    if (std::find(Objects.begin(), Objects.end(), GV) != Objects.end())
+      return ConservativeResult;
+  }
+
+  // We identified all objects in the argument list, and none of them were GV.
+  return MRI_NoModRef;
+}
+
 ModRefInfo GlobalsAAResult::getModRefInfo(ImmutableCallSite CS,
                                           const MemoryLocation &Loc) {
   unsigned Known = MRI_ModRef;
 
   // If we are asking for mod/ref info of a direct call with a pointer to a
   // global we are tracking, return information if we have it.
   if (const GlobalValue *GV =
           dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
     if (GV->hasLocalLinkage())
       if (const Function *F = CS.getCalledFunction())
         if (NonAddressTakenGlobals.count(GV))
           if (const FunctionInfo *FI = getFunctionInfo(F))
-            Known = FI->getModRefInfoForGlobal(*GV);
+            Known = FI->getModRefInfoForGlobal(*GV) |
+              getModRefInfoForArgument(CS, GV);
 
   if (Known == MRI_NoModRef)
     return MRI_NoModRef; // No need to query other mod/ref analyses
   return ModRefInfo(Known & AAResultBase::getModRefInfo(CS, Loc));
 }
 
 GlobalsAAResult::GlobalsAAResult(const DataLayout &DL,
                                  const TargetLibraryInfo &TLI)
GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
   }
 }
 
 /*static*/ GlobalsAAResult
 GlobalsAAResult::analyzeModule(Module &M, const TargetLibraryInfo &TLI,
                                CallGraph &CG) {
   GlobalsAAResult Result(M.getDataLayout(), TLI);
 
+  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
+  Result.CollectSCCMembership(CG);
+
   // Find non-addr taken globals.
   Result.AnalyzeGlobals(M);
 
   // Propagate on CG.
   Result.AnalyzeCallGraph(CG, M);
 
   return Result;
 }

test/Analysis/GlobalsModRef/memset-escape.ll

+; RUN: opt < %s -O1 -S -enable-non-lto-gmr=true | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+@a = internal global [3 x i32] zeroinitializer, align 4
+@b = common global i32 0, align 4
+
+; The important thing we're checking for here is the reload of (some element of)
+; @a after the memset.
+
+; CHECK-LABEL: @main
+; CHECK: call void @llvm.memset.p0i8.i64{{.*}} @a
+; CHECK: store i32 3
+; CHECK: load i32, i32* getelementptr {{.*}} @a
+; CHECK: icmp eq i32
+; CHECK: br i1
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  %c = alloca [1 x i32], align 4
+  store i32 0, i32* %retval, align 4
+  %0 = bitcast [1 x i32]* %c to i8*
+  call void @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 4, i32 4, i1 false)
+  store i32 1, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 2), align 4
+  store i32 0, i32* @b, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %1 = load i32, i32* @b, align 4
+  %cmp = icmp slt i32 %1, 3
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %2 = load i32, i32* @b, align 4
+  %idxprom = sext i32 %2 to i64
+  %arrayidx = getelementptr inbounds [3 x i32], [3 x i32]* @a, i64 0, i64 %idxprom
+  store i32 0, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %3 = load i32, i32* @b, align 4
+  %inc = add nsw i32 %3, 1
+  store i32 %inc, i32* @b, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %4 = load i32, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 2), align 4
+  %cmp1 = icmp ne i32 %4, 0
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.end
+  call void @abort() #3
+  unreachable
+
+if.end:                                           ; preds = %for.end
+  ret i32 0
+}
+
+; Function Attrs: nounwind argmemonly
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind argmemonly
+
+; Function Attrs: noreturn nounwind
+declare void @abort() noreturn nounwind

test/Analysis/GlobalsModRef/nocapture.ll

+; RUN: opt < %s -globals-aa -aa-eval -print-all-alias-modref-info -S 2>&1 | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+@a = internal global i32 0, align 4
+@b = internal global i32 0, align 4
+
+define void @g(i32* %p, void (i32*)* nocapture %ptr) {
+entry:
+  tail call void %ptr(i32* %p) #1
+  ret void
+}
+
+; CHECK-LABEL: Function: f
+; CHECK: MayAlias: i32* %p, i32* @a
+; CHECK: MayAlias: i32* %q, i32* @a
+define i32 @f(i32 %n, i32* nocapture readonly %p, i32* nocapture %q, void (i32*)* nocapture %ptr) {
+entry:
+  tail call void @g(i32* nonnull @a, void (i32*)* %ptr)
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 0
+  %z1 = load i32, i32* %arrayidx, align 4
+  %z2 = load i32, i32* %q, align 4
+  %add = add nsw i32 %z2, %z1
+  store i32 %add, i32* %q, align 4
+  ret i32 4
+}
+
+define void @g2(i32* nocapture %p, void (i32*)* nocapture %ptr) {
+entry:
+  tail call void %ptr(i32* %p) #1
+  ret void
+}
+
+; CHECK-LABEL: Function: f2
+; CHECK: NoAlias: i32* %p, i32* @b
+; CHECK: NoAlias: i32* %q, i32* @b
+define i32 @f2(i32 %n, i32* nocapture readonly %p, i32* nocapture %q, void (i32*)* nocapture %ptr) {
+entry:
+  tail call void @g2(i32* nonnull @b, void (i32*)* %ptr)
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 0
+  %z1 = load i32, i32* %arrayidx, align 4
+  %z2 = load i32, i32* %q, align 4
+  %add = add nsw i32 %z2, %z1
+  store i32 %add, i32* %q, align 4
+  ret i32 4
+}