[Attributor] Deduce memory location function attributes

[jdoerfert]

Summary

Deduce the memory location attributes, i.a., "inaccessiblememonly",
"argmemonly", and "inaccessible_or_argmemonly", for functions. This
also improves earlier memory behavior deductions, for example D59980, as
we can now identify and ignore accesses to local and constant memory.

Impact on the statistics (-stats) for LLVM-TS + Spec2006,

CHANGED: attributor                   NumAttributesManifested                87205 ->      88546 (    +1.538%)
CHANGED: attributor                   NumAttributesValidFixpoint            118598 ->     119936 (    +1.128%)
  ADDED: attributor                   NumFnArgMemOnly                          n/a ->       5115
CHANGED: attributor                   NumFnReadNone                           2930 ->       3086 (    +5.324%)
CHANGED: attributor                   NumFnReadOnly                           4380 ->       4243 (    -3.128%)
CHANGED: attributor                   NumFnWriteOnly                          1960 ->       1987 (    +1.378%)
CHANGED: functionattrs                NumReadNone                              165 ->         12 (   -92.727%)
CHANGED: functionattrs                NumReadOnly                              134 ->        120 (   -10.448%)
CHANGED: functionattrs                NumWriteOnly                              52 ->         25 (   -51.923%)
CHANGED: memdep                       NumCacheNonLocalPtr                  7731531 ->    7837481 (    +1.370%)

Note: Some ofthe remaining readnone/readonly/writeonly functionattrs

deductions are a result of a bug, see: http://llvm.org/PR41328

[jdoerfert]

D73426 replaced this.

llvm/include/llvm/Transforms/IPO/Attributor.h

struct AAMemoryBehavior : public AbstractAttribute {
   /// Return true if we know that the underlying value is not read in its
   /// respective scope.
   virtual bool isKnownWriteOnly() const = 0;
 
   /// Return true if we assume that the underlying value is not read in its
   /// respective scope.
   virtual bool isAssumedWriteOnly() const = 0;
 
+  /// Return true if we know that the underlying value will only access
+  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
+  virtual bool isKnownInaccessibleMemOnly() const = 0;
+
+  /// Return true if we assume that the underlying value will only access
+  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
+  virtual bool isAssumedInaccessibleMemOnly() const = 0;
+
+  /// Return true if we know that the underlying value will only access
+  /// argument pointees (see Attribute::ArgMemOnly).
+  virtual bool isKnownArgMemOnly() const = 0;
+
+  /// Return true if we assume that the underlying value will only access
+  /// argument pointees (see Attribute::ArgMemOnly).
+  virtual bool isAssumedArgMemOnly() const = 0;
+
+  /// Return true if we know that the underlying value will only access
+  /// inaccesible memory or argument pointees (see
+  /// Attribute::InaccessibleOrArgMemOnly).
+  virtual bool isKnownInaccessibleOrArgMemOnly() const = 0;
+
+  /// Return true if we assume that the underlying value will only access
+  /// inaccesible memory or argument pointees (see
+  /// Attribute::InaccessibleOrArgMemOnly).
+  virtual bool isAssumedInaccessibleOrArgMemOnly() const = 0;
+
   /// See AbstractState::getAttrKind().
   Attribute::AttrKind getAttrKind() const override { return ID; }
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::ReadNone;
 };
 
 /// ----------------------------------------------------------------------------

llvm/lib/Transforms/IPO/Attributor.cpp

 STATISTIC(NumFnArgumentReadOnly,
           "Number of function arguments marked read-only");
 STATISTIC(NumFnArgumentWriteOnly,
           "Number of function arguments marked write-only");
 
 STATISTIC(NumFnReadNone, "Number of functions marked read-none");
 STATISTIC(NumFnReadOnly, "Number of functions marked read-only");
 STATISTIC(NumFnWriteOnly, "Number of functions marked write-only");
+STATISTIC(NumFnArgMemOnly, "Number of functions marked argumen-pointee-only");
+STATISTIC(NumFnInaccessibleMemOnly,
+          "Number of functions marked inaccessible-memory-only");
+STATISTIC(NumFnInaccessibleOrArgMemOnly,
+          "Number of functions marked inaccessible-or-argument-pointee-only");
 
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint
static void bookkeeping(AbstractAttribute::ManifestPosition MP,
   case Attribute::ReadOnly:
     MP == AbstractAttribute::MP_ARGUMENT ? NumFnArgumentReadOnly++
                                          : NumFnReadOnly++;
     return;
   case Attribute::WriteOnly:
     MP == AbstractAttribute::MP_ARGUMENT ? NumFnArgumentWriteOnly++
                                          : NumFnWriteOnly++;
     return;
+  case Attribute::InaccessibleMemOnly:
+    NumFnInaccessibleMemOnly++;
+    return;
+  case Attribute::ArgMemOnly:
+    NumFnArgMemOnly++;
+    return;
+  case Attribute::InaccessibleMemOrArgMemOnly:
+    NumFnInaccessibleOrArgMemOnly++;
+    return;
   default:
     return;
   }
 }
 
 template <typename StateTy>
 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
 template <typename StateTy>
ChangeStatus AANoCaptureArgument::updateImpl(Attributor &A) {
   while (isAssumedNoCaptureMaybeReturned() && Idx < PotentialCopies.size())
     Tracker.valueMayBeCaptured(PotentialCopies[Idx++]);
 
   return (AssumedState == getAssumed()) ? ChangeStatus::UNCHANGED
                                         : ChangeStatus::CHANGED;
 }
 
 /// -------------------- Memory Behavior Attributes ----------------------------
-/// Includes read-none, read-only, and write-only.
+/// Includes read-none, read-only, and write-only, as well as their combination
+/// with inaccessible-mem-only, arg-mem-only, and inaccessible-or-arg-mem-only.
 /// ----------------------------------------------------------------------------
 
 /// A class to hold the state of for memory behaviour attributes.
 ///
 /// The state is encoded in the bits of the "char" variables known and assumed
 /// as defined by the encoding bits.
 struct AAMemoryBehaviorImpl : public AAMemoryBehavior, IntegerState {
 
   AAMemoryBehaviorImpl(Value &V, AAResults &AAR)
       : AAMemoryBehavior(V), IntegerState(BEST_STATE), AAR(AAR) {
     assert(getAssumed() == BEST_STATE && "Expected optimistic initialization!");
   }
 
   /// State encoding bits. A set bit in the state means the property holds.
   /// BEST_STATE is the best possible state, 0 the worst possible state.
   enum {
     NO_READS = 1 << 0,
     NO_WRITES = 1 << 1,
     NO_ACCESSES = NO_READS | NO_WRITES,
 
-    BEST_STATE = NO_ACCESSES,
+    ONLY_ARGUMENT_MEM = 1 << 2,
+    ONLY_INACCESSIBLE_MEM = 1 << 3,
+    ONLY_INACCESSIBLE_OR_ARGUMENT_MEM = 1 << 4,
+    NO_LOCATIONS = ONLY_ARGUMENT_MEM | ONLY_INACCESSIBLE_MEM |
+                   ONLY_INACCESSIBLE_OR_ARGUMENT_MEM,
+
+    BEST_STATE = NO_ACCESSES | NO_LOCATIONS,
   };
 
   /// See AAMemoryBehavior::isKnownReadNone();
   virtual bool isKnownReadNone() const override { return isKnown(NO_ACCESSES); }
 
   /// See AAMemoryBehavior::isAssumedReadNone();
   virtual bool isAssumedReadNone() const override {
     return isAssumed(NO_ACCESSES);
struct AAMemoryBehaviorImpl : public AAMemoryBehavior, IntegerState {
   /// See AAMemoryBehavior::isKnownWriteOnly();
   virtual bool isKnownWriteOnly() const override { return isKnown(NO_READS); }
 
   /// See AAMemoryBehavior::isAssumedWriteOnly();
   virtual bool isAssumedWriteOnly() const override {
     return isAssumed(NO_READS);
   }
 
+  /// See AAMemoryBehavior::isKnownInaccessibleMemOnly();
+  virtual bool isKnownInaccessibleMemOnly() const override {
+    return getKnown() & ONLY_INACCESSIBLE_MEM;
+  }
+
+  /// See AAMemoryBehavior::isAssumedInaccessibleMemOnly();
+  virtual bool isAssumedInaccessibleMemOnly() const override {
+    return getAssumed() & ONLY_INACCESSIBLE_MEM;
+  }
+
+  /// See AAMemoryBehavior::isKnownArgMemOnly();
+  virtual bool isKnownArgMemOnly() const override {
+    return getKnown() & ONLY_ARGUMENT_MEM;
+  }
+
+  /// See AAMemoryBehavior::isAssumedArgMemOnly();
+  virtual bool isAssumedArgMemOnly() const override {
+    return getAssumed() & ONLY_ARGUMENT_MEM;
+  }
+
+  /// See AAMemoryBehavior::isKnownInaccessibleOrArgMemOnly();
+  virtual bool isKnownInaccessibleOrArgMemOnly() const override {
+    return getKnown() & ONLY_INACCESSIBLE_OR_ARGUMENT_MEM;
+  }
+
+  /// See AAMemoryBehavior::isAssumedInaccessibleOrArgMemOnly();
+  virtual bool isAssumedInaccessibleOrArgMemOnly() const override {
+    return getAssumed() & ONLY_INACCESSIBLE_OR_ARGUMENT_MEM;
+  }
+
   /// See AbstractState::getAsStr().
   const std::string getAsStr() const override {
     std::string S = "";
     if (isAssumedReadNone())
       S = "readnone";
     else if (isAssumedReadOnly())
       S = "readonly";
     else if (isAssumedWriteOnly())
       S = "writeonly";
     else
       S = "may-read/write";
 
+    if (isAssumedInaccessibleMemOnly())
+      S += " inaccessible memory";
+    else if (isAssumedArgMemOnly())
+      S += " argument pointee memory";
+    else if (isAssumedInaccessibleOrArgMemOnly())
+      S += " inaccessible or argument pointee memory";
+
     return S;
   }
 
   /// Return the memory behavior information of \p V encoded in the IR.
   static void getKnownStateFromValue(const Value &V, IntegerState &State,
                                      bool ValueOnly, AAResults *AAR = nullptr);
 
   /// See AbstractAttribute::getDeducedAttributes(Attributor &A).
if (!ValueOnly)
       getKnownStateFromValue(*Arg->getParent(), State, ValueOnly, AAR);
   } else if (const Function *Fn = dyn_cast<Function>(&V)) {
     if (AAR) {
       auto ModRef = AAR->getModRefBehavior(Fn);
       if (AAResults::onlyReadsMemory(ModRef))
         State.addKnownBits(NO_WRITES);
       if (AAResults::doesNotReadMemory(ModRef))
         State.addKnownBits(NO_READS);
+      if (AAResults::onlyAccessesInaccessibleMem(ModRef))
+        State.addKnownBits(ONLY_INACCESSIBLE_MEM);
+      if (AAResults::onlyAccessesArgPointees(ModRef))
+        State.addKnownBits(ONLY_ARGUMENT_MEM);
+      if (AAResults::onlyAccessesInaccessibleOrArgMem(ModRef))
+        State.addKnownBits(ONLY_INACCESSIBLE_OR_ARGUMENT_MEM);
     } else {
       if (Fn->hasFnAttribute(Attribute::ReadNone))
         State.addKnownBits(NO_ACCESSES);
       else if (Fn->hasFnAttribute(Attribute::ReadOnly))
         State.addKnownBits(NO_WRITES);
       else if (Fn->hasFnAttribute(Attribute::WriteOnly))
         State.addKnownBits(NO_READS);
+      if (Fn->hasFnAttribute(Attribute::InaccessibleMemOnly))
+        State.addKnownBits(ONLY_INACCESSIBLE_MEM);
+      else if (Fn->hasFnAttribute(Attribute::ArgMemOnly))
+        State.addKnownBits(ONLY_ARGUMENT_MEM);
+      else if (Fn->hasFnAttribute(Attribute::InaccessibleMemOrArgMemOnly))
+        State.addKnownBits(ONLY_INACCESSIBLE_OR_ARGUMENT_MEM);
     }
   }
 }
 
 void AAMemoryBehaviorImpl::getDeducedAttributes(
     SmallVectorImpl<Attribute> &Attrs) const {
   LLVMContext &Ctx = getAnchoredValue().getContext();
   assert(Attrs.size() == 0);
   if (isAssumedReadNone()) {
     Attrs.push_back(Attribute::get(Ctx, Attribute::ReadNone));
     return;
   }
 
   if (isAssumedReadOnly())
     Attrs.push_back(Attribute::get(Ctx, Attribute::ReadOnly));
   else if (isAssumedWriteOnly())
     Attrs.push_back(Attribute::get(Ctx, Attribute::WriteOnly));
   assert(Attrs.size() <= 1);
+
+  if (isAssumedInaccessibleMemOnly())
+    Attrs.push_back(Attribute::get(Ctx, Attribute::InaccessibleMemOnly));
+  else if (isAssumedArgMemOnly())
+    Attrs.push_back(Attribute::get(Ctx, Attribute::ArgMemOnly));
+  else if (isAssumedInaccessibleOrArgMemOnly())
+    Attrs.push_back(
+        Attribute::get(Ctx, Attribute::InaccessibleMemOrArgMemOnly));
+  assert(Attrs.size() <= 2);
 }
 
 /// An AA to represent the memory behavior function attributes.
 struct AAMemoryBehaviorFunction final : public AAMemoryBehaviorImpl {
 
   /// See AAMemoryBehaviorImpl::AAMemoryBehaviorImpl(...).
   AAMemoryBehaviorFunction(Function &F, AAResults &AAR)
       : AAMemoryBehaviorImpl(F, AAR) {}
struct AAMemoryBehaviorFunction final : public AAMemoryBehaviorImpl {
 
   /// See AbstractAttribute::manifest(Attributor &A).
   virtual ChangeStatus manifest(Attributor &A) override;
 
   /// See AbstractAttribute::getManifestPosition().
   virtual ManifestPosition getManifestPosition() const override {
     return MP_FUNCTION;
   }
+
+protected:
+  /// Encoding of different locations that could be accessed by a memory access.
+  enum MemoryLocationKind {
+    MLK_NONE = 0,
+    MLK_CONST_OR_LOCAL = 1 << 0,
+    MLK_GLOBAL = 1 << 1,
+    MLK_ARGUMENT = 1 << 2,
+    MLK_INACCESSIBLE = 1 << 3,
+    MLK_UNKNOWN =
+        MLK_CONST_OR_LOCAL | MLK_GLOBAL | MLK_ARGUMENT | MLK_INACCESSIBLE,
+  };
+
+  /// Return the kind(s) of location that may be accessed by \p I.
+  MemoryLocationKind
+  categorizeAccessedLocations(Attributor &A, const Instruction &I,
+                              const AAMemoryBehavior *MemBehaviorAA);
+
+  /// Return the kind(s) of location that may be represented by \p V.
+  MemoryLocationKind
+  categorizeRepresentedLocations(Attributor &A, const Value &V,
+                                 SmallPtrSetImpl<const Value *> &Visited);
+};
+
+AAMemoryBehaviorFunction::MemoryLocationKind
+AAMemoryBehaviorFunction::categorizeRepresentedLocations(
+    Attributor &A, const Value &V, SmallPtrSetImpl<const Value *> &Visited) {
+  if (!Visited.insert(&V).second)
+    return MLK_NONE;
+
+  const Value *Ptr, *PtrOrigin = V.stripInBoundsConstantOffsets();
+  do {
+    Ptr = PtrOrigin;
+    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Ptr))
+      PtrOrigin = BCI->getOperand(0);
+    else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
+      PtrOrigin = GEP->getPointerOperand();
+    else if (const SelectInst *SI = dyn_cast<SelectInst>(Ptr)) {
+      return (MemoryLocationKind)(
+          categorizeRepresentedLocations(A, *SI->getTrueValue(), Visited) |
+          categorizeRepresentedLocations(A, *SI->getFalseValue(), Visited));
+    } else if (const PHINode *PHI = dyn_cast<PHINode>(Ptr)) {
+      MemoryLocationKind MLK = MLK_NONE;
+      for (const Value *PHIOp : PHI->operands())
+        MLK = (MemoryLocationKind)(
+            MLK | categorizeRepresentedLocations(A, *PHIOp, Visited));
+      return MLK;
+    }
+  } while (PtrOrigin != Ptr);
+
+  if (isa<UndefValue>(Ptr))
+    return MLK_NONE;
+  if (isa<Argument>(Ptr))
+    return MLK_ARGUMENT;
+  if (isa<GlobalValue>(Ptr))
+    return MLK_GLOBAL;
+  if (AAR.pointsToConstantMemory(Ptr, /*OrLocal=*/true))
+    return MLK_CONST_OR_LOCAL;
+
+  return MLK_UNKNOWN;
+}
+
+AAMemoryBehaviorFunction::MemoryLocationKind
+AAMemoryBehaviorFunction::categorizeAccessedLocations(
+    Attributor &A, const Instruction &I,
+    const AAMemoryBehavior *MemBehaviorAA) {
+  SmallPtrSet<const Value *, 16> VisitedValues;
+
+  auto CollectArgumentLocations = [&](const ImmutableCallSite &ICS) {
+    MemoryLocationKind MLK = MLK_NONE;
+    unsigned ArgNo = 0;
+    for (Value *ArgOp : ICS.args()) {
+      // If the argument is readnone we ignore it.
+      auto *MemBehaviorAA =
+          A.getAAFor<AAMemoryBehavior>(*this, *ICS.getCalledValue(), ArgNo++);
+      if (MemBehaviorAA && MemBehaviorAA->getState().isValidState() &&
+          MemBehaviorAA->isAssumedReadNone())
+        continue;
+
+      MLK = (MemoryLocationKind)(
+          MLK | categorizeRepresentedLocations(A, *ArgOp, VisitedValues));
+    }
+    return MLK;
   };
 
+  // We can try to lookup another in-flight abstract attribute for the
+  // instruction in question.
+  if (MemBehaviorAA && MemBehaviorAA->getState().isValidState()) {
+    if (MemBehaviorAA->isAssumedReadNone())
+      return MLK_NONE;
+    if (MemBehaviorAA->isAssumedInaccessibleMemOnly())
+      return MLK_INACCESSIBLE;
+
+    ImmutableCallSite ICS(&I);
+    if (ICS && MemBehaviorAA->isAssumedArgMemOnly())
+      return CollectArgumentLocations(ICS);
+    if (ICS && MemBehaviorAA->isAssumedInaccessibleOrArgMemOnly())
+      return (MemoryLocationKind)(MLK_INACCESSIBLE |
+                                  CollectArgumentLocations(ICS));
+  }
+
+  // TODO: Memory intrinsics
+  Optional<MemoryLocation> Loc = MemoryLocation::getOrNone(&I);
+  if (!Loc.hasValue())
+    return MLK_UNKNOWN;
+
+  if (AAR.pointsToConstantMemory(Loc.getValue(), /*OrLocal=*/true))
+    return MLK_CONST_OR_LOCAL;
+
+  return categorizeRepresentedLocations(A, *Loc->Ptr, VisitedValues);
+}
+
 ChangeStatus AAMemoryBehaviorFunction::updateImpl(Attributor &A) {
 
   // The current assumed state used to determine a change.
   auto AssumedState = getAssumed();
 
   Function &F = cast<Function>(getAnchoredValue());
   auto &ReadOrWriteInsts = A.getReadOrWriteInstsForFunction(F);
 
   for (const Instruction *I : ReadOrWriteInsts) {
     assert(I->mayReadOrWriteMemory());
 
     // If the instruction has an own memory behavior state, use it to restrict
     // the local state. No further analysis is required as the other memory
     // state is as optimistic as it gets.
     auto *MemBehaviorAA = A.getAAFor<AAMemoryBehaviorImpl>(*this, *I);
     if (MemBehaviorAA && MemBehaviorAA->getState().isValidState()) {
       intersectAssumedBits(MemBehaviorAA->getAssumed());
       continue;
     }
 
+    // If the instruction does not have an own memory behavior state, we
+    // categorize all potentially accessed locations and the potential
+    // side-effects explicitly.
+    MemoryLocationKind MLK = categorizeAccessedLocations(A, *I, MemBehaviorAA);
+    if (MLK == MLK_NONE || MLK == MLK_CONST_OR_LOCAL)
+      continue;
+
+    // Remove location modifiers if necessary.
+    if (MLK & MLK_GLOBAL)
+      removeAssumedBits(ONLY_ARGUMENT_MEM | ONLY_INACCESSIBLE_MEM |
+                        ONLY_INACCESSIBLE_OR_ARGUMENT_MEM);
+    else if (MLK & MLK_ARGUMENT)
+      removeAssumedBits(ONLY_INACCESSIBLE_MEM);
+    else if (MLK & MLK_INACCESSIBLE)
+      removeAssumedBits(ONLY_ARGUMENT_MEM);
+
     // Remove access kind modifiers if necessary.
     if (I->mayReadFromMemory())
       removeAssumedBits(NO_READS);
     if (I->mayWriteToMemory())
       removeAssumedBits(NO_WRITES);
   }
 
   return (AssumedState != getAssumed()) ? ChangeStatus::CHANGED
getKnownStateFromValue(F, ExistingState, /* ValueOnly */ true,
                          /* AAR */ nullptr);
   if (ExistingState.isKnown(getAssumed()))
     return ChangeStatus::UNCHANGED;
 
   // Remove existing attributes as they not always mix well with derived ones.
   F.removeFnAttr(Attribute::ReadNone);
   F.removeFnAttr(Attribute::ReadOnly);
   F.removeFnAttr(Attribute::WriteOnly);
-  if (isAssumedReadNone()) {
-    F.removeFnAttr(Attribute::ArgMemOnly);
-    F.removeFnAttr(Attribute::InaccessibleMemOnly);
-    F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
-  }
   return AbstractAttribute::manifest(A);
 }
 
 /// An AA to represent the memory behavior argument attributes.
 struct AAMemoryBehaviorArgument final : public AAMemoryBehaviorImpl {
 
   /// See AAMemoryBehaviorImpl::AAMemoryBehaviorImpl(...).
   AAMemoryBehaviorArgument(Argument &Arg, AAResults &AAR)
       : AAMemoryBehaviorImpl(Arg, AAR) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     Argument &Arg = cast<Argument>(getAnchoredValue());
 
+    // Reset the memory location flags inherited from the AAMemoryBehaviorImpl
+    // class. The best for an argument is the combination of no-reads and
+    // no-writes => readnone.
+    removeAssumedBits(NO_LOCATIONS);
+
     if (Arg.getNumUses() == 0)
       addKnownBits(NO_ACCESSES);
     else
       getKnownStateFromValue(Arg, *this, /* ValueOnly */ false, &AAR);
   }
 
   /// See AbstractAttribute::updateImpl(Attributor &A).
   virtual ChangeStatus updateImpl(Attributor &A) override;