[GlobalsAA] Loosen an overly conservative bailout

[jmolloy]

Summary

When checking if a Value can alias a non-addr-taken global, if the Value is a LoadInst, then it cannot alias the global.

In order for the two to alias, the Value must be a pointer within the
global object. If that pointer has just been loaded from memory, it
cannot possibly alias the global as we know the global's address could
never have ended up in memory in the first place.

I've thrown all the testing I have at this, and it hasn't triggered any miscompares anywhere... but that's no evidence that there isn't a counterexample to my logic above.

Hal and Chandler - I've thought about this a *lot* and I think my logic is correct, but would you guys mind validating it? Thanks!

[chandlerc]

I don't understand your comment.

How does this not break in the face of reg2mem?

[jmolloy]

Hi Chandler,

You're right, the previous patch was utter utter nonsense.

This updated patch covers all the cases I cared about and seems far more sound. Simply: instead of bailing out, recurse. If a captured value is found while following a chain of loads, all those loads are also captured.

This lets us hit the case I care about which is something like:

static int a;
static int **b;

alias? (a, b[1][2]);

Cheers,

James

[chandlerc]

My brain hurts from thinking about this. ;] Sorry for delays though. I *think* I've got my head wrapped around it.

lib/Analysis/GlobalsModRef.cpp

682

However we end up with this, please minimize the number of calls to GetUnderlyingObject. That is actually the expensive part, and its redundant with the above code.

684–687

So, pushing this onto the worklist isn't quite what we want. And whatever we want, we shouldn't have the one-off check above, because whatever we want should work for the immediate pointer operand as well as N-deep pointer operands.

The loop we want for loads is substantially simpler than the one we are currently inside of, because we don't need to handle overridable global variables, the original global variable, whether things are sized, etc etc.

Once we are looking through a load, we can simply check for globals, calls, invokes, and arguments; and recurse through phis, selects, and subsequent loads. However, this also means we can't re-use the visited set. I think we should have a dedicated helper for recursing on load pointer operands, and pass the depth parameter into it. This will remove the need for some of the shuffling here.

Also, as a minor point, the issue is not capture, but escape. Even if the escape does not outlive a particular function, it can break this. However, as is mentioned above, we are relying on it being unreasonable for a transformation to introduce an escape of a global variable. This includes a direct escape (which the existing code relies upon) and an indirect escape (which your new logic relies upon).

[jmolloy]

Hi Chandler,

Thanks for getting around to this. I agree with everything you've said and have updated the patch.

Hopefully the comments should be correct this time - I did have trouble wording the comments correctly as it's easy to give the wrong impression (as you caught).

James

[chandlerc]

lib/Analysis/GlobalsModRef.cpp

613

GlobalValue is repeated here. I would keep a single if, and merge the two comments. Your comment above is excellent.

730

Add vertical space before here?

741

Just call the function? This is the first test it does.

747

No need for else after a continue.

[chandlerc]

And as James pointed out, my last round of comment sare completely stylistic. LGTM with these changes.

lib/Analysis/GlobalsModRef.cpp

   }
 }
 
+// GV is a non-escaping global. V is a pointer address that has been loaded from.
+// If we can prove that V must escape, we can conclude that a load from V cannot
+// alias GV.
+static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV,
+                                               const Value *V,
+                                               int &Depth,
+                                               const DataLayout &DL) {
+  SmallPtrSet<const Value *, 8> Visited;
+  SmallVector<const Value *, 8> Inputs;
+  Visited.insert(V);
+  Inputs.push_back(V);
+  do {
+    const Value *Input = Inputs.pop_back_val();
+    
+    if (isa<GlobalValue>(Input))
+      // This is a load (transitively) from a global. If this aliased another global,
+      // its address would escape, so no alias.
+      continue;
+    if (isa<GlobalValue>(Input) || 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;
+    
+    // Recurse through a limited number of selects, loads 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 *LI = dyn_cast<LoadInst>(Input)) {
+      Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
+      continue;
+    }  
+    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;
+    }
+    
+    return false;
+  } while (!Inputs.empty());
+
+  // All inputs were known to be no-alias.
+  return true;
+}
+
 // 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

       // non-addr-taken globals.
       continue;
     }
+    // Recurse through a limited number of selects, loads 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 *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>(GetUnderlyingObject(LI->getPointerOperand(), DL)))
+      const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
+      if (isa<GlobalValue>(Ptr))
         continue;
 
-      // Otherwise, a load could come from anywhere, so bail.
-      return false;
+      if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL)) {
+        // The load does not alias with GV.
+        continue;
+      } else {
+        // 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);

test/Analysis/GlobalsModRef/nonescaping-noalias.ll

   %v = load i32, i32* @g1
   ret i32 %v
 }
+
+define i32 @test5(i32** %param) {
+; Ensure that we can fold a store to a load of a global across a store to
+; a parameter that has been dereferenced when the global is non-escaping.
+;
+; CHECK-LABEL: @test5(
+; CHECK: %p = load i32*
+; CHECK: store i32 42, i32* @g1
+; CHECK-NOT: load i32
+; CHECK: ret i32 42
+entry:
+  %p = load i32*, i32** %param
+  store i32 42, i32* @g1
+  store i32 7, i32* %p
+  %v = load i32, i32* @g1
+  ret i32 %v
+}