[GMR] Teach the conservative path of GMR to catch even more easy cases.

[chandlerc]

Summary

In PR24288 it was pointed out that the easy case of a non-escaping
global and something that *obviously* required an escape sometimes is
hidden behind PHIs (or selects in theory). Because we have this binary
test, we can easily just check that all possible input values satisfy
the requirement. This is done with a (very small) recursion through PHIs
and selects. With this, the specific example from the PR is correctly
folded by GVN.

[majnemer]

lib/Analysis/IPA/GlobalsModRef.cpp

698

Where is GV used?

729–730

This comment could probably go on one line.

[mkuper]

lib/Analysis/IPA/GlobalsModRef.cpp

734

colud -> could

762

It looks like this also covers the case where we end up reaching GV itself in the recursion. Perhaps make that explicit?

819

This looks a bit confusing.
Can we turn this into the more standard "if (!GV1) swap..." pattern?

[chandlerc]

Updating patch based on reviewer comments.

[chandlerc]

Updated, and responses to review comments below...

lib/Analysis/IPA/GlobalsModRef.cpp

698

Sorry, I was trying to use GV to do some stuff that ended up with the FIXME comment instead. =] Based on Michael's comment, I'll add in the stub that uses it around the FIXME comment, which should also make it much more clear how to safely implement that FIXME.

762

Yea, that also gives me a much better place to anchor the FIXME above. Should make sure that we don't introduce a bug about the same GV when addressing that FIXME.

819

I really don't like the swap pattern... Does doing this in separate variable initializers make it more clear? (Patch updated to do that...)

[mkuper]

LGTM

lib/Analysis/IPA/GlobalsModRef.cpp

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);
+
+  bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V);
 };
 }
 
 char GlobalsModRef::ID = 0;
 INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
                          "Simple mod/ref analysis for globals", false, true,
                          false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
 
     // Finally, now that we know the full effect on this SCC, clone the
     // information to each function in the SCC.
     for (unsigned i = 1, e = SCC.size(); i != e; ++i)
       FunctionInfos[SCC[i]->getFunction()] = FI;
   }
 }
 
+// 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.
+bool GlobalsModRef::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
+                                               const Value *V) {
+  // 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. We can also
+  // recurse through PHI nodes and select nodes provided all of their inputs
+  // resolve to one of these known-escaping roots.
+  SmallPtrSet<const Value *, 8> Visited;
+  SmallVector<const Value *, 8> Inputs;
+  Visited.insert(V);
+  Inputs.push_back(V);
+  int Depth = 0;
+  do {
+    const Value *Input = Inputs.pop_back_val();
+
+    if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
+      // If one input is the very global we're querying against, then we can't
+      // conclude no-alias.
+      if (InputGV == GV)
+        return false;
+
+      // FIXME: It would be good to handle other obvious no-alias cases here, but
+      // it isn't clear how to do so reasonbly without building a small version
+      // of BasicAA into this code. We could recurse into AliasAnalysis::alias
+      // here but that seems likely to go poorly as we're inside the
+      // implementation of such a query. Until then, just conservatievly retun
+      // false.
+      return false;
+    }
+
+    if (isa<Argument>(Input) || isa<CallInst>(Input) ||
+        isa<InvokeInst>(Input)) {
+      // Arguments to functions or returns from functions are inherently
+      // escaping, so we can immediately classify those as not aliasing any
+      // non-addr-taken globals.
+      continue;
+    }
+    if (auto *LI = dyn_cast<LoadInst>(Input)) {
+      // A pointer loaded from a global would have been captured, and we know
+      // that the global is non-escaping, so no alias.
+      if (isa<GlobalValue>(LI->getPointerOperand()))
+        continue;
+
+      // Otherwise, a load could come from anywhere, so bail.
+      return false;
+    }
+
+    // Recurse through a limited number of selects and PHIs. This is an
+    // arbitrary depth of 4, lower numbers could be used to fix compile time
+    // issues if needed, but this is generally expected to be only be important
+    // for small depths.
+    if (++Depth > 4)
+      return false;
+    if (auto *SI = dyn_cast<SelectInst>(Input)) {
+      const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), *DL);
+      const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), *DL);
+      if (Visited.insert(LHS).second)
+        Inputs.push_back(LHS);
+      if (Visited.insert(RHS).second)
+        Inputs.push_back(RHS);
+      continue;
+    }
+    if (auto *PN = dyn_cast<PHINode>(Input)) {
+      for (const Value *Op : PN->incoming_values()) {
+        Op = GetUnderlyingObject(Op, *DL);
+        if (Visited.insert(Op).second)
+          Inputs.push_back(Op);
+      }
+      continue;
+    }
+
+    // Unknown instruction, bail.
+    return false;
+  } while (!Inputs.empty());
+
+  // If all the inputs to V were definitively no-alias, then V is no-alias.
+  return true;
+}
+
 /// alias - If one of the pointers is to a global that we are tracking, and the
 /// other is some random pointer, we know there cannot be an alias, because the
 /// address of the global isn't taken.
 AliasResult GlobalsModRef::alias(const MemoryLocation &LocA,
                                  const MemoryLocation &LocB) {
   // Get the base object these pointers point to.
   const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL);
   const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL);
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.
+    // Check for a special case where a non-escaping global can be used to
+    // conclude no-alias.
     if ((GV1 || GV2) && GV1 != GV2) {
+      const GlobalValue *GV = GV1 ? 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.
+      if (isNonEscapingGlobalNoAlias(GV, UV))
         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;

test/Analysis/GlobalsModRef/nonescaping-noalias.ll

 ; 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
 }
+
+define i32 @test4(i32* %param, i32 %n, i1 %c1, i1 %c2) {
+; Ensure that we can fold a store to a load of a global across a store to
+; the pointer loaded from that global even when the load is behind PHIs and
+; selects, and there is a mixture of a load and another global or argument.
+; Note that we can't eliminate the load here because it is used in a PHI and
+; GVN doesn't try to do real DCE. The store is still forwarded by GVN though.
+;
+; CHECK-LABEL: @test4(
+; CHECK: store i32 42, i32* @g1
+; CHECK: store i32 7, i32*
+; CHECK: ret i32 42
+entry:
+  %call = call i32* @f()
+  store i32 42, i32* @g1
+  %ptr1 = load i32*, i32** @g2
+  %ptr2 = select i1 %c1, i32* %ptr1, i32* %param
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %ptr = phi i32* [ %ptr2, %entry ], [ %ptr4, %loop ]
+  store i32 7, i32* %ptr
+  %ptr3 = load i32*, i32** @g2
+  %ptr4 = select i1 %c2, i32* %ptr3, i32* %call
+  %inc = add i32 %iv, 1
+  %test = icmp slt i32 %inc, %n
+  br i1 %test, label %loop, label %exit
+
+exit:
+  %v = load i32, i32* @g1
+  ret i32 %v
+}