Vtable aliasing improvement: makes obj->vtable noalias obj and modref(obj->virt_call, obj->vtable) = REF

[andrew.zhogin]

Summary

This patch contains two improvements for basicaa alias analysis:

• Knowledge that object pointer can't be aliased with vtable loaded from this object (obj->vtable noalias obj).
• Knowledge that virtual call to object can't change this object's vtable. modrefinfo(obj->virt_call, obj->vtable) = REF; modrefinfo(obj->virt_call, obj->vtable->fn) = REF;

Vtable is identified by TBAA metadata (isTBAAVtableAccess - already existing function).

Combined with this patch (http://reviews.llvm.org/D11547) it makes very simple in-loop devirtualization works. This bug's example is fixed: https://llvm.org/bugs/show_bug.cgi?id=20801

But just a bit more complex samples require AliasSetTracker's merge sets problem to be fixed.
"alias set collapse and LICM": https://groups.google.com/forum/#!topic/llvm-dev/Qy66vhi5NaY

[rsmith]

Your assumption that the vptr for an object cannot change during a virtual call to that object is not correct; the rules here are more subtle. See the recent "Clang devirtualization proposal" thread on llvm-dev / cfe-dev for an approach that handles the cases where the vptr actually cannot change; Piotr Padlewski is currently working on implementing that approach.

lib/Analysis/BasicAliasAnalysis.cpp

1462–1464

This is redundant in many cases (we can already deduce this if the load from the object has TBAA metadata, or if we can see the pointers are distinct), and wrong in other cases (for instance, using memcpy to write over the storage for an object that had a vptr).

include/llvm/Analysis/AliasAnalysis.h

bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
                                  const ModRefInfo Mode);
 
   /// A convenience wrapper synthesizing a memory location.
   bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
                                  const Value *Ptr, uint64_t Size,
                                  const ModRefInfo Mode) {
     return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
   }
+  /// isVtableLoadFrom - Return true if Vtable is vtable load from Obj
+  bool isVtableLoadFrom(const Value *Vtable, const Value *Obj);
 };
 
 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 /// function.
 bool isNoAliasCall(const Value *V);
 
 /// isNoAliasArgument - Return true if this is an argument with the noalias
 /// attribute.

lib/Analysis/AliasAnalysis.cpp

bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1,
   ++E;  // Convert from inclusive to exclusive range.
 
   for (; I != E; ++I) // Check every instruction in range
     if (getModRefInfo(I, Loc) & Mode)
       return true;
   return false;
 }
 
+/// isVtableLoadFrom - Return true if Vtable is vtable load from Obj
+bool AliasAnalysis::isVtableLoadFrom(const Value *Vtable, const Value *Obj) {
+  if (const auto *VtableLd = dyn_cast<LoadInst>(Vtable)) {
+    AAMDNodes AAInfo;
+    VtableLd->getAAMetadata(AAInfo);
+    if (AAInfo.TBAA && AAInfo.TBAA->isTBAAVtableAccess())
+      return GetUnderlyingObject(VtableLd->getOperand(0), *DL) == Obj;
+  }
+  return false;
+}
+
 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 /// function.
 bool llvm::isNoAliasCall(const Value *V) {
   if (isa<CallInst>(V) || isa<InvokeInst>(V))
     return ImmutableCallSite(cast<Instruction>(V))
       .paramHasAttr(0, Attribute::NoAlias);
   return false;
 }

lib/Analysis/BasicAliasAnalysis.cpp

ModRefInfo BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
   // We cannot exclude byval arguments here; these belong to the caller of
   // the current function not to the current function, and a tail callee
   // may reference them.
   if (isa<AllocaInst>(Object))
     if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
       if (CI->isTailCall())
         return MRI_NoModRef;
 
+  // If this is virtual call to obj, considering obj->vtable and obj->vtable->fn as not modifiable
+  if (CS.getNumArgOperands() > 0) {
+    const auto *CalleeVal = CS.getCalledValue(); // must be load vtable + offset
+    const auto *CallObj = CS.getArgOperand(0); // must be obj
+
+    if (const auto *CalleeLd = dyn_cast<LoadInst>(CalleeVal)) {
+      const auto *VtableVal = CalleeLd->getOperand(0);
+      const auto *VtableValUnder = GetUnderlyingObject(VtableVal, *DL);
+      if (const auto *VtableLd = dyn_cast<LoadInst>(VtableValUnder)) {
+        AAMDNodes AAInfo;
+        VtableLd->getAAMetadata(AAInfo);
+        if (AAInfo.TBAA) {
+          if (AAInfo.TBAA->isTBAAVtableAccess()) {
+            const auto *ObjForVtable = VtableLd->getOperand(0);
+
+            if (isMustAlias(GetUnderlyingObject(ObjForVtable, *DL), CallObj))
+              if (isMustAlias(VtableValUnder, Object)
+                || isMustAlias(ObjForVtable, Object))
+                return MRI_Ref;
+          }
+        }
+      }
+    }
+  }
+
   // If the pointer is to a locally allocated object that does not escape,
   // then the call can not mod/ref the pointer unless the call takes the pointer
   // as an argument, and itself doesn't capture it.
   if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
       isNonEscapingLocalObject(Object)) {
     bool PassedAsArg = false;
     unsigned ArgNo = 0;
     for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
if (O1 != O2) {
     // variety of complications. A call with a nocapture argument may still
     // temporary store the nocapture argument's value in a temporary memory
     // location if that memory location doesn't escape. Or it may pass a
     // nocapture value to other functions as long as they don't capture it.
     if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
       return NoAlias;
     if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
       return NoAlias;
+
+    // Considering Object's Vtable can't alias Object
+    if (isVtableLoadFrom(O1, O2) || isVtableLoadFrom(O2, O1))
+      return NoAlias;
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
   if (DL)
     if ((V1Size != MemoryLocation::UnknownSize &&
          isObjectSmallerThan(O2, V1Size, *DL, *TLI)) ||
         (V2Size != MemoryLocation::UnknownSize &&