[AA] A global cannot escape through nocapture/nocallback call.

[vzakhari]

Summary

When an internal global is passed to a 'nocallback' call as
a 'nocapture' pointer, it cannot escape through this call and
be indirectly referenced in this module.
So it must not alias with any pointer in the module.

This may provide some remedy for Fortran module-private array descriptors
that are usually passed by address to some runtime functions
(e.g. to allocation/deallocation functions). In general, a good aliasing
information derived from Fortran language rules would solve the same issue,
but I think this change may be beneficial as-is (given that nocapture,
nocallback attributes are properly set).

[jdoerfert]

I like the idea. The tests should be augmented though. First, run sroa on the test, there is no need for such verbose IR.
Then, add a second version for all of them that calls an unknown function in the loop. As written, I can always hoist all of them, even if we don't do it yet.
I would personally use the check line script but I guess that one can check it like this too.

llvm/lib/Analysis/GlobalsModRef.cpp

367

Usually we check the call for attributes, not the function.

llvm/test/Analysis/GlobalsModRef/noescape-nocapture-nocallback.ll

5

No tripple needed.

153

Maybe write it inline, easier to read.
declare ... nocallback

[vzakhari]

Thank you for the review, Johannes!

I am not sure why the hoisting was legal in the previous version. I guess it has something to do with the fact that clobbering a part of pointer with -1 may be considering an undefined behavior, so I changed the test to store a pointer inside the loop.
I also added cases with an unknown call, but it cannot be just any unknown call. Without nosync or nocallback a call may modify a global even if it was not captured.

[jdoerfert]

LG

In D138336#3938844, @vzakhari wrote:

Thank you for the review, Johannes!

I am not sure why the hoisting was legal in the previous version. I guess it has something to do with the fact that clobbering a part of pointer with -1 may be considering an undefined behavior, so I changed the test to store a pointer inside the loop.

So, I didn't even see the UB, which was there. It was legal to hoist, and is in the versions w/o a call, because nothing in the loop can effectively alias the obj global.
The store can still not alias the obj even if we don't figure that out right now. Consequently, the obj is invariant and can be hoisted just after the function that takes obj.
The version with the unknown call are different. If obj escaped earlier, then the unknown call might have an impact on it and we cannot hoist the load.

I also added cases with an unknown call, but it cannot be just any unknown call. Without nosync or nocallback a call may modify a global even if it was not captured.

Fair point. We want to check that we know it wasn't captured, so the annotated unknown call looks good.

We could even do better in the nocapture case w/o nocallback, maybe add a TODO as this case can be handled if all uses in the module are nocapture effectively.

[vzakhari]

We could even do better in the nocapture case w/o nocallback, maybe add a TODO as this case can be handled if all uses in the module are nocapture effectively.

Good point. I will add a note.

llvm/test/Analysis/GlobalsModRef/noescape-nocapture-nocallback.ll

67

Johannes, I have hard time figuring out why this code may be optimized without the capture analysis.

Doesn't this store conflict with the above load, in general? I think it can, if somewhere inside the module I do obj0.p = obj0. So the capture analysis is required to prove that they do not conflict.

[vzakhari]

Added TODO + rebase.

llvm/lib/Analysis/GlobalsModRef.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
       // passing into the function.
       if (Call->isDataOperand(&U)) {
         // Detect calls to free.
         if (Call->isArgOperand(&U) &&
             getFreedOperand(Call, &GetTLI(*Call->getFunction())) == U) {
           if (Writers)
             Writers->insert(Call->getParent()->getParent());
         } else {
-          return true; // Argument of an unknown call.
+          // In general, we return true for unknown calls, but there are
+          // some simple checks that we can do for functions that
+          // will never call back into the module.
+          auto *F = Call->getCalledFunction();
+          // TODO: we should be able to remove isDeclaration() check
+          // and let the function body analysis check for captures,
+          // and collect the mod-ref effects. This information will
+          // be later propagated via the call graph.
+          if (!F || !F->isDeclaration())
+            return true;
+          // Note that the NoCallback check here is a little bit too
+          // conservative. If there are no captures of the global
+          // in the module, then this call may not be a capture even
+          // if it does not have NoCallback.
+          if (!Call->hasFnAttr(Attribute::NoCallback) ||
+              !Call->isArgOperand(&U) ||
+              !Call->doesNotCapture(Call->getArgOperandNo(&U)))
+            return true;
+
+          // Conservatively, assume the call reads and writes the global.
+          // We could use memory attributes to make it more precise.
+          if (Readers)
+            Readers->insert(Call->getParent()->getParent());
+          if (Writers)
+            Writers->insert(Call->getParent()->getParent());
         }
       }
     } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
         return true; // Allow comparison against null.
     } else if (Constant *C = dyn_cast<Constant>(I)) {
       // Ignore constants which don't have any live uses.
       if (isa<GlobalValue>(C) || C->isConstantUsed())

llvm/test/Analysis/GlobalsModRef/noescape-nocapture-nocallback.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -aa-pipeline=basic-aa,globals-aa -S -passes='require<globals-aa>,function(loop-mssa(licm))' | FileCheck %s
+
+;Reference C code:
+;struct str {
+;  void **p;
+;};
+;static struct str obj;
+;extern void nocapture_nocallback_func(struct str *);
+;void test(void *p) {
+;  nocapture_nocallback_func(&obj);
+;  for (int i = 0; i < 1000; ++i) {
+;    unknown_call(); // optional
+;    obj.p[i] = p;
+;  }
+;}
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.str = type { ptr }
+
+@obj0 = internal global %struct.str zeroinitializer, align 8
+@obj1 = internal global %struct.str zeroinitializer, align 8
+@obj2 = internal global %struct.str zeroinitializer, align 8
+@obj3 = internal global %struct.str zeroinitializer, align 8
+@obj4 = internal global %struct.str zeroinitializer, align 8
+@obj5 = internal global %struct.str zeroinitializer, align 8
+
+define dso_local void @test0(ptr %p) {
+; Check that load from @obj0 is hoisted from the loop, meaning
+; that it does not conflict with the store inside the loop:
+; CHECK-LABEL: @test0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocapture_nocallback_func(ptr @obj0)
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj0, align 8
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocapture_nocallback_func(ptr @obj0)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj0, align 8
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define dso_local void @test1(ptr %p) {
+; Check that load from @obj1 is not hoisted from the loop,
+; because 'nocallback' is missing:
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocapture_func(ptr @obj1)
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj1, align 8
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocapture_func(ptr @obj1)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj1, align 8
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define dso_local void @test2(ptr %p) {
+; Check that load from @obj2 is not hoisted from the loop,
+; because 'nocapture' is missing:
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocallback_func(ptr @obj2)
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj2, align 8
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocallback_func(ptr @obj2)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj2, align 8
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define dso_local void @test3(ptr %p) {
+; Check that load from @obj3 is hoisted from the loop, even though
+; there is unknown call in the loop.
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocapture_nocallback_func(ptr @obj3)
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj3, align 8
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    call void @unknown_call()
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocapture_nocallback_func(ptr @obj3)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj3, align 8
+  call void @unknown_call()
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define dso_local void @test4(ptr %p) {
+; Check that load from @obj4 is not hoisted from the loop,
+; because 'nocallback' is missing:
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocapture_func(ptr @obj4)
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj4, align 8
+; CHECK-NEXT:    call void @unknown_call()
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocapture_func(ptr @obj4)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj4, align 8
+  call void @unknown_call()
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define dso_local void @test5(ptr %p) {
+; Check that load from @obj5 is not hoisted from the loop,
+; because 'nocapture' is missing:
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @nocallback_func(ptr @obj5)
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 1000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr @obj5, align 8
+; CHECK-NEXT:    call void @unknown_call()
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store ptr [[P:%.*]], ptr [[ARRAYIDX]], align 8
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  call void @nocallback_func(ptr @obj5)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = load ptr, ptr @obj5, align 8
+  call void @unknown_call()
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds ptr, ptr %0, i64 %idxprom
+  store ptr %p, ptr %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @nocapture_nocallback_func(ptr nocapture) nocallback
+declare void @nocapture_func(ptr nocapture)
+declare void @nocallback_func(ptr) nocallback
+; nosync and nocallback are required, otherwise the call
+; will by ModRef for any global:
+declare void @unknown_call() nosync nocallback