[GMR] Be a bit smarter about which globals alias when doing recursive lookups

[mkuper]

Summary

This should hopefully fix PR24288 even harder.

To be honest, I'm not sure this is the right condition.
Does this look sane? That is, is the zero-size check really necessary (and is the way I'm checking it correct)?

[majnemer]

lib/Analysis/IPA/GlobalsModRef.cpp

720–734

I guess a zero-sized global can never be "modified" as you would *actually* modify some other global (or commit UB if there was no other global). However, it's possible to have a global variable in one TU and a global alias in another TU with the same name which makes me think that you need to check that the linkage is not mayBeOverridden.

[mkuper]

Thanks, David!

Added the check mayBeOverwritten() check.

About the zero-size check, what if you have two consecutive zero-size globals, followed by a third (non-zero-size) global? (That sounds like nonsense, but I don't quite understand the semantics of zero-size globals to begin with.)

[chandlerc]

LGTM with nit picks below.

lib/Analysis/IPA/GlobalsModRef.cpp

720

"... never alias, unless overridden or zero-sized."

728–729

I would explicitly write "> 0" for these.

[majnemer]

lib/Analysis/IPA/GlobalsModRef.cpp

728–729

Note that the type might not be sized if it's a global variable with an opaque body. You might want to query isSized first.

lib/Analysis/IPA/GlobalsModRef.cpp

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.
+      // Distinct GlobalVariables never alias, unless zero-sized.
+      // FIXME: The condition can be refined, but be conservative for now.
+      auto *GVar = dyn_cast<GlobalVariable>(GV);
+      auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
+      
+      if (GVar && InputGVar &&
+          !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
+          !GVar->mayBeOverridden() && !InputGVar->mayBeOverridden() &&
+          DL->getTypeAllocSize(GVar->getInitializer()->getType()) &&
+          DL->getTypeAllocSize(InputGVar->getInitializer()->getType()))
+        continue;
+
+      // Conservatively return false, even though we could be smarter
+      // (e.g. look through GlobalAliases).
       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 *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.
+    // 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;
   } 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

test/Analysis/GlobalsModRef/nonescaping-noalias.ll

 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) {
+@g3 = internal global i32 1
+
+define i32 @test4(i32* %param, i32 %n, i1 %c1, i1 %c2, i1 %c3) {
 ; 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
+  %ptr3 = select i1 %c3, i32* %ptr2, i32* @g3
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %inc, %loop ]
-  %ptr = phi i32* [ %ptr2, %entry ], [ %ptr4, %loop ]
+  %ptr = phi i32* [ %ptr3, %entry ], [ %ptr5, %loop ]
   store i32 7, i32* %ptr
-  %ptr3 = load i32*, i32** @g2
-  %ptr4 = select i1 %c2, i32* %ptr3, i32* %call
+  %ptr4 = load i32*, i32** @g2
+  %ptr5 = select i1 %c2, i32* %ptr4, 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
 }