[GMR] Teach GlobalsModRef to distinguish an important and safe case of no-alias with non-addr-taken globals: they cannot alias a captured pointer.

[chandlerc]

Summary

If the non-global underlying object would have been a capture were it to
alias the global, we can firmly conclude no-alias. It isn't reasonable
for a transformation to introduce a capture in a way observable by an
alias analysis. Consider, even if it were to temporarily capture one
globals address into another global and then restore the other global
afterward, there would be no way for the load in the alias query to
observe that capture event correctly. If it observes it then the
temporary capturing would have changed the meaning of the program,
making it an invalid transformation. Even instrumentation passes or
a pass which is synthesizing stores to global variables to expose race
conditions in programs could not trigger this unless it queried the
alias analysis infrastructure mid-transform, in which case it seems
reasonable to return results from before the transform started.

See the comments in the change for a more detailed outlining of the
theory here.

This should address the primary performance regression found when the
non-conservatively-correct path of the alias query was disabled.

I haven't yet written a specific test case, but wanted to share the idea
of the technique with others to see if this is sufficiently promising to
be the preferred path forward.

[chandlerc]

Replace some ugly and unnecessary code with a cleaner approach.

[chandlerc]

Rebase to ToT

[mzolotukhin]

Hi Chandler,

I did some preliminary testing again, and it seems that this patch resolves the biggest regressions we saw:

More than 0.5% changes:
=========================================
Benchmark       Old     New     Delta
-----------------------------------------
403.gcc         435.53  415.91  -4.50%
445.gobmk       875.12  866.1   -1.03%
458.sjeng       1045.91 1035.76 -0.97%
=========================================

We observed some other smaller regressions too, but I think my setup is too noisy to detect an effect on them.

Overall the change seems reasonable to me, one question though:

lib/Analysis/IPA/GlobalsModRef.cpp

716–721 ↗

(On Diff #30555)

Could you please give an example of how a load from non-global could alias with non-addr-taken global?

[mzolotukhin]

I also tested clean compiler with "" and got following results:

More than 0.5% changes:
=========================================
Benchmark       Old     New     Delta
-----------------------------------------
403.gcc         415.91  413.33  -0.62%
429.mcf         388.97  385.67  -0.85%
445.gobmk       866.1   860.82  -0.61%
458.sjeng       1035.76 1071.71  3.47%    <-- probably noisy run
483.xalancbmk   528.78  525.81  -0.56%
=========================================

It means that there are some regressions which didn't recover even with this patch. I think we can investigate them later, after the patch is committed, and they are verified by regular testing.

[chandlerc]

Thanks for the measurements.

Anyone want to take a look at the code? I'd love an LGTM from someone before submitting.

lib/Analysis/IPA/GlobalsModRef.cpp

716–721 ↗

(On Diff #30555)

reg2mem, or spilling an SSA register for some ABI exception handling and then reloading, or any other transformation that uses memory within a function without impacting any other function.

[hfinkel]

LGTM, but can we have a test case please?

[hfinkel]

lib/Analysis/IPA/GlobalsModRef.cpp

713 ↗

(On Diff #30555)

Also, while I don't think the code here is wrong, the word 'capturing' in the comment could be a bit misleading. The argument in question, for example, could have the 'nocapture' attribute. This is okay, however, because we consider any global's address being passed to a function as having its address taken (even via a nocapture argument).

I think it would be nice for the comment to explain this.

[chandlerc]

As discussed on IRC, I switched the wording to "escaping" as I think that is much more accurate. Sadly, I failed to fully update my change description. Sorry about that.

I did add the basic functional testing that this works. This also should address PR24288 which is another regression reduced out of the change to GMR.

Thanks again for the review!

llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp

if (GV1 || GV2) {
 
     // If one is and the other isn't, it isn't strictly safe but we can fake
     // this result if necessary for performance. This does not appear to be
     // a common problem in practice.
     if (EnableUnsafeGlobalsModRefAliasResults)
       if ((GV1 || GV2) && GV1 != GV2)
         return NoAlias;
 
+    // There are particular cases where we can conclude no-alias between
+    // a non-addr-taken global and some other underlying object. Specifically,
+    // a non-addr-taken global is known to not be escaped from any function. It
+    // is also incorrect for a transformation to introduce an escape of
+    // a global in a way that is observable when it was not there previously.
+    // One function being transformed to introduce an escape which could
+    // possibly be observed (via loading from a global or the return value for
+    // example) within another function is never safe. If the observation is
+    // made through non-atomic operations on different threads, it is
+    // a data-race and UB. If the observation is well defined, by being
+    // observed the transformation would have changed program behavior by
+    // introducing the observed escape, making it an invalid transform.
+    //
+    // This property does require that transformations which *temporarily*
+    // escape a global that was not previously escaped, prior to restoring
+    // it, cannot rely on the results of GMR::alias. This seems a reasonable
+    // restriction, although currently there is no way to enforce it. There is
+    // also no realistic optimization pass that would make this mistake. The
+    // closest example is a transformation pass which does reg2mem of SSA
+    // values but stores them into global variables temporarily before
+    // restoring the global variable's value. This could be useful to expose
+    // "benign" races for example. However, it seems reasonable to require that
+    // a pass which introduces escapes of global variables in this way to
+    // either not trust AA results while the escape is active, or to be forced
+    // to operate as a module pass that cannot co-exist with an alias analysis
+    // such as GMR.
+    if ((GV1 || GV2) && GV1 != GV2) {
+      const Value *UV = GV1 ? UV2 : UV1;
+
+      // In order to know that the underlying object cannot alias the
+      // non-addr-taken global, we must know that it would have to be an
+      // escape. Thus if the underlying object is a function argument, a load
+      // from a global, or the return of a function, it cannot alias.
+      if (isa<Argument>(UV) || isa<CallInst>(UV) || isa<InvokeInst>(UV)) {
+        // Arguments to functions or returns from functions are inherently
+        // escaping, so we can immediately classify those as not aliasing any
+        // non-addr-taken globals.
+        return NoAlias;
+      } else if (auto *LI = dyn_cast<LoadInst>(UV)) {
+        // A pointer loaded from a global would have been captured, and we know
+        // that GV is non-addr-taken, so no alias.
+        if (isa<GlobalValue>(LI->getPointerOperand()))
+          return NoAlias;
+      }
+    }
+
     // Otherwise if they are both derived from the same addr-taken global, we
     // can't know the two accesses don't overlap.
   }
 
   // These pointers may be based on the memory owned by an indirect global.  If
   // so, we may be able to handle this.  First check to see if the base pointer
   // is a direct load from an indirect global.
   GV1 = GV2 = nullptr;

llvm/trunk/test/Analysis/GlobalsModRef/nonescaping-noalias.ll

+; RUN: opt < %s -globalsmodref-aa -gvn -S | FileCheck %s
+;
+; This tests the safe no-alias conclusions of GMR -- when there is
+; a non-escaping global as one indentified underlying object and some pointer
+; that would inherently have escaped any other function as the other underlying
+; pointer of an alias query.
+
+@g1 = internal global i32 0
+
+define i32 @test1(i32* %param) {
+; Ensure that we can fold a store to a load of a global across a store to
+; a parameter when the global is non-escaping.
+;
+; CHECK-LABEL: @test1(
+; CHECK: store i32 42, i32* @g1
+; CHECK-NOT: load i32
+; CHECK: ret i32 42
+entry:
+  store i32 42, i32* @g1
+  store i32 7, i32* %param
+  %v = load i32, i32* @g1
+  ret i32 %v
+}
+
+declare i32* @f()
+
+define i32 @test2() {
+; Ensure that we can fold a store to a load of a global across a store to
+; the pointer returned by a function call. Since the global could not escape,
+; this function cannot be returning its address.
+;
+; CHECK-LABEL: @test2(
+; CHECK: store i32 42, i32* @g1
+; CHECK-NOT: load i32
+; CHECK: ret i32 42
+entry:
+  %ptr = call i32* @f() readnone
+  store i32 42, i32* @g1
+  store i32 7, i32* %ptr
+  %v = load i32, i32* @g1
+  ret i32 %v
+}
+
+@g2 = external global i32*
+
+define i32 @test3() {
+; Ensure that we can fold a store to a load of a global across a store to
+; the pointer loaded from that global. Because the global does not escape, it
+; cannot alias a pointer loaded out of a global.
+;
+; CHECK-LABEL: @test3(
+; CHECK: store i32 42, i32* @g1
+; CHECK: store i32 7, i32*
+; CHECK-NOT: load i32
+; CHECK: ret i32 42
+entry:
+  store i32 42, i32* @g1
+  %ptr1 = load i32*, i32** @g2
+  store i32 7, i32* %ptr1
+  %v = load i32, i32* @g1
+  ret i32 %v
+}