[Attributor] Deduce "nosync" function attribute

[sstefan1]

Summary

Introduce new "nosync" attribute which indicates that a function does not synchronize with other functions. Will be used with "nofree" (D49165 & D62687) for dereferencable.

[sstefan1]

changed updateImpl, the logic was wrong.

[sstefan1]

update

[sstefan1]

wrong diff

llvm/docs/LangRef.rst

 ``noreturn``
     This function attribute indicates that the function never returns
     normally. This produces undefined behavior at runtime if the
     function ever does dynamically return.
 ``norecurse``
     This function attribute indicates that the function does not call itself
     either directly or indirectly down any possible call path. This produces
     undefined behavior at runtime if the function ever does recurse.
+
+``nosync``
+    This function attribute indicates that the function does not communicate 
+    (synchronize) with another thread causing that other thread to delete
+    the memory.
 ``nounwind``
     This function attribute indicates that the function never raises an
     exception. If the function does raise an exception, its runtime
     behavior is undefined. However, functions marked nounwind may still
     trap or generate asynchronous exceptions. Exception handling schemes
     that are recognized by LLVM to handle asynchronous exceptions, such
     as SEH, will still provide their implementation defined semantics.
 ``"null-pointer-is-valid"``
``sspreq``
     This attribute indicates that the function should *always* emit a
     stack smashing protector. This overrides the ``ssp`` function
     attribute.
 
     Variables that are identified as requiring a protector will be arranged
     on the stack such that they are adjacent to the stack protector guard.
     The specific layout rules are:
 
-    #. Large arrays and structures containing large arrays
        (``>= ssp-buffer-size``) are closest to the stack protector.
     #. Small arrays and structures containing small arrays
        (``< ssp-buffer-size``) are 2nd closest to the protector.
     #. Variables that have had their address taken are 3rd closest to the
        protector.
 
     If a function that has an ``sspreq`` attribute is inlined into a
     function that doesn't have an ``sspreq`` attribute or which has an

 
 .. code-block:: llvm
 
     define void @f() {
       call void @x()  ;; no deopt state
       call void @y() [ "deopt"(i32 10) ]
       call void @y() [ "deopt"(i32 10), "unknown"(i8* null) ]
       ret void
-    }
 
     define void @g() {
       call void @f() [ "deopt"(i32 20) ]
       ret void
     }
 
 will result in
 

llvm/include/llvm/IR/Attributes.td

 def NoRecurse : EnumAttr<"norecurse">;
 
 /// Disable redzone.
 def NoRedZone : EnumAttr<"noredzone">;
 
 /// Mark the function as not returning.
 def NoReturn : EnumAttr<"noreturn">;
 
+/// Function does not synchronize.
+def NoSync : StrBoolAttr<"nofree">;
+
 /// Disable Indirect Branch Tracking.
 def NoCfCheck : EnumAttr<"nocf_check">;
 
 /// Function doesn't unwind stack.
 def NoUnwind : EnumAttr<"nounwind">;
 
 /// Select optimizations for best fuzzing signal.
 def OptForFuzzing : EnumAttr<"optforfuzzing">;

llvm/lib/Transforms/IPO/Attributor.cpp

-//===- Attributor.cpp - Module-wide attribute deduction -------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
+// //
+// // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements an inter procedural pass which walk the call-graph
 // deducing and/or propagating attributes along the way. This is done in an
 // abstract interpretation style fixpoint iteration. See the Attributor.h

 STATISTIC(NumFnWithoutExactDefinition,
           "Number of function without exact definitions");
 STATISTIC(NumAttributesTimedOut,
           "Number of abstract attributes timed out before fixpoint");
 STATISTIC(NumAttributesValidFixpoint,
           "Number of abstract attributes in a valid fixpoint state");
 STATISTIC(NumAttributesManifested,
           "Number of abstract attributes manifested in IR");
+STATISTIC(NumFnNoSync, "Number of functions marked nosync");
 
 // 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

 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
 }
 ///}
 
+/// Simple state with integers encoding.
+///
+/// The interface ensures that the assumed bits are always a subset of the known
+/// bits. Users can only add known bits and, except through adding known bits,
+/// they can only remove assumed bits. This should guarantee monotoniticy and
+/// thereby the existence of a fixpoint (if used corretly). The fixpoint is
+/// reached when the assumed and known state/bits are equal. Users can
+/// force/inidicate a fixpoint. If an optimistic one is indicated, the known
+/// state will catch up with the assumed one, for a pessimistic fixpoint it is
+/// the other way around.
+struct IntegerState : public AbstractState {
+  /// Undrlying integer type, we assume 32 bits to be enough.
+  using base_t = uint32_t;
+
+  /// Initialize the (best) state.
+  IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
+
+  /// Return the worst possible representable state.
+  static constexpr base_t getWorstState() { return 0; }
+
+  /// See AbstractState::isValidState()
+  /// NOTE: For now we simply pretend that the worst possible state is invalid.
+  bool isValidState() const override { return Assumed != getWorstState(); }
+
+  /// See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override { return Assumed == Known; }
+
+  /// See AbstractState::indicateOptimisticFixpoint(...)
+  void indicateOptimisticFixpoint() override { Known = Assumed; }
+
+  /// See AbstractState::indicatePessimisticFixpoint(...)
+  void indicatePessimisticFixpoint() override { Assumed = Known; }
+
+  /// Return the known state encoding
+  base_t getKnown() const { return Known; }
+
+  /// Return the assumed state encoding.
+  base_t getAssumed() const { return Assumed; }
+
+  /// Return true if the bits set in \p BitsEncoding are "known bits".
+  bool isKnown(base_t BitsEncoding) const {
+    return (Known & BitsEncoding) == BitsEncoding;
+  }
+
+  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
+  bool isAssumed(base_t BitsEncoding) const {
+    return (Assumed & BitsEncoding) == BitsEncoding;
+  }
+
+  /// Add the bits in \p BitsEncoding to the "known bits".
+  IntegerState &addKnownBits(base_t Bits) {
+    // Make sure we never miss any "known bits".
+    Assumed |= Bits;
+    Known |= Bits;
+    return *this;
+  }
+
+  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
+  IntegerState &removeAssumedBits(base_t BitsEncoding) {
+    // Make sure we never loose any "known bits".
+    Assumed = (Assumed & ~BitsEncoding) | Known;
+    return *this;
+  }
+
+  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
+  IntegerState &intersectAssumedBits(base_t BitsEncoding) {
+    // Make sure we never loose any "known bits".
+    Assumed = (Assumed & BitsEncoding) | Known;
+    return *this;
+  }
+
+private:
+  /// The known state encoding in an integer of type base_t.
+  base_t Known = getWorstState();
+
+  /// The assumed state encoding in an integer of type base_t.
+  base_t Assumed;
+};
+
+/// Simple wrapper for a single bit (boolean) state.
+struct BooleanState : public IntegerState {
+  BooleanState() : IntegerState(1){};
+};
+
 /// Helper to adjust the statistics.
 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
                         const Attribute &Attr) {
   if (!AreStatisticsEnabled())
     return;
 
+  if (Attr.isStringAttribute()) {
+    StringRef StringAttr = Attr.getKindAsString();
+    if (StringAttr == Attr.getKindAsString())
+      NumFnNoSync++;
+    return;
+  }
+
   if (!Attr.isEnumAttribute())
     return;
   switch (Attr.getKindAsEnum()) {
   default:
     return;
   }
 }
 
if (isa<Instruction>(V))
     return *cast<Instruction>(V).getFunction();
   llvm_unreachable("No scope for anchored value found!");
 }
 
 const Function &AbstractAttribute::getAnchorScope() const {
   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 }
 
+/// ------------------------ NoSync Function Attribute -------------------------
+
+struct AANoSyncFunction : AbstractAttribute, BooleanState {
+
+  AANoSyncFunction(Function &F, InformationCache &InfoCache)
+      : AbstractAttribute(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+
+
+  /// See AbstractAttribute::getAsStr().
+  virtual const std::string getAsStr() const override {
+    return getAssumed() ? "nosync" : "may-sync";
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// Return deduced attributes in \p Attrs.
+  virtual void
+  getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+    Attrs.emplace_back(Attribute::get(Ctx, "nosync"));
+  }
+
+  /// See AbstractAttribute::getAttrKind().
+  virtual Attribute::AttrKind getAttrKind() const override {
+    return Attribute::None;
+  }
+
+  /// Returns true of "nosync" is assumed.
+  bool isAssumedNoSync() const { return getAssumed(); }
+
+  /// Returns true of "nosync" is known.
+  bool isKnownNoFree() const { return getKnown(); }
+
+  static constexpr Attribute::AttrKind ID =
+      Attribute::AttrKind(Attribute::None - 2);
+};
+
+/// helper functions.
+AtomicOrdering getOrdering(Instruction *I) {
+  switch (I->getOpcode()) {
+  case Instruction::AtomicRMW:
+    return cast<AtomicRMWInst>(I)->getOrdering();
+  case Instruction::Store:
+    return cast<StoreInst>(I)->getOrdering();
+  case Instruction::Load:
+    return cast<LoadInst>(I)->getOrdering();
+  default:
+    return AtomicOrdering::NotAtomic;
+  }
+}
+
+bool isVolatile(Instruction *I) {
+  switch (I->getOpcode()) {
+  case Instruction::AtomicRMW:
+    return cast<AtomicRMWInst>(I)->isVolatile();
+  case Instruction::Store:
+    return cast<StoreInst>(I)->isVolatile();
+  case Instruction::Load:
+    return cast<LoadInst>(I)->isVolatile();
+  default:
+    return false;
+  }
+}
+
+ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  /// The map from instruction opcodes to those instructions in the function.
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+  auto MemoryOperators = {(unsigned)Instruction::Load,
+                          (unsigned)Instruction::Store,
+                          (unsigned)Instruction::AtomicRMW};
+
+  /// We are looking for volatile instructions or Non-Relaxed atomics.
+  for (auto Opcode : MemoryOperators) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      if (!isVolatile(I))
+        continue;
+      if (!I->isAtomic())
+        continue;
+
+      auto ordering = getOrdering(I);
+
+      if (ordering == AtomicOrdering::Unordered ||
+          ordering == AtomicOrdering::Monotonic)
+        continue;
+
+      ImmutableCallSite ICS(I);
+      auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
+      if ((!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
+          !ICS.hasFnAttr("nosync") && !ICS.hasFnAttr("readnone")) {
+        indicatePessimisticFixpoint();
+        return ChangeStatus::CHANGED;
+      }
+    }
+  }
+  indicateOptimisticFixpoint();
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
ChangeStatus Attributor::run() {
 
   return ManifestChange;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(
     Function &F, InformationCache &InfoCache,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
+    // Every function might be marked "nosync".
+    registerAA(*new AANoSyncFunction(F, InfoCache));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
   for (Instruction &I : instructions(&F)) {
     bool IsInterestingOpcode = false;
 
     switch (I.getOpcode()) {
     default:
       break;
+    case Instruction::Load:
+    case Instruction::Store:
+    case Instruction::AtomicRMW:
+      IsInterestingOpcode = true;
     }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
       ReadOrWriteInsts.push_back(&I);
   }
 }
 

llvm/test/Transforms/FunctionAttrs/nosync.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Test cases designet for the "nosync" function attribute.
+; FIXME's are used to indicate problems and missing attributes.
+
+; struct RT {
+;   char A;
+;   int B[10][20];
+;   char C;
+; };
+; struct ST {
+;   int X;
+;   double Y;
+;   struct RT Z;
+; };
+; 
+; int *foo(struct ST *s) {
+;   return &s[1].Z.B[5][13];
+; }
+
+; TEST 1
+; attribute readnone implies "nosync"
+%struct.RT = type { i8, [10 x [20 x i32]], i8 }
+%struct.ST = type { i32, double, %struct.RT }
+
+; FIXME: missing "nosync"
+; CHECK Function Attrs: nounwind uwtable readnone optsize ssp
+define i32* @foo(%struct.ST* %s) nounwind uwtable readnone optsize ssp {
+entry:
+  %arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2, i32 1, i64 5, i64 13
+  ret i32* %arrayidx
+} 
+
+; TEST 2
+; atomic load with monotonic ordering
+; int load_monotonic(_Atomic int *num) {
+;   int n = atomic_load_explicit(num, memory_order_relaxed);
+;   return n;
+; }
+  
+; FIXME: missing "nosync"
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NEXT: define i32 @load_monotonic(i32* nocapture readonly)
+define i32 @load_monotonic(i32* nocapture readonly) norecurse nounwind uwtable {
+  %2 = load atomic i32, i32* %0 monotonic, align 4
+  ret i32 %2
+}
+
+
+; TEST 3
+; atomic store with monotonic ordering.
+; void store_monotonic(_Atomic int *num) {
+;   atomic_load_explicit(num, memory_order_relaxed);
+; }
+
+; FIXME: missing "nosync"
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NEXT: define void @store_monotonic(i32* nocapture)
+define void @store_monotonic(i32* nocapture) norecurse nounwind uwtable {
+  store atomic i32 10, i32* %0 monotonic, align 4
+  ret void
+}
+
+; TEST 4 - negative, should not deduce "nosync"
+; atomic load with acquire ordering.
+; int load_acquire(_Atomic int *num) {
+;   int n = atomic_load_explicit(num, memory_order_acquire);
+;   return n;
+; }
+
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define i32 @load_acquire(i32* nocapture readonly)
+define i32 @load_acquire(i32* nocapture readonly) norecurse nounwind uwtable {
+  %2 = load atomic i32, i32* %0 acquire, align 4
+  ret i32 %2
+}
+
+; TEST 5 - negative, should not deduce "nosync"
+; atomic load with release ordering
+; void load_release(_Atomic int *num) {
+;   atomic_store_explicit(num, 10, memory_order_release);
+; }
+
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define void @load_release(i32* nocapture)
+define void @load_release(i32* nocapture) norecurse nounwind uwtable {
+  store atomic i32 10, i32* %0 release, align 4
+  ret void
+}
+
+; TEST 6 - negative, should not deduce "nosync"
+; volatile store.
+; void volatile_store(volatile int *num) {
+;   *num = 14;
+; }
+
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define void @volatile_store(i32*)
+define void @volatile_store(i32*) norecurse nounwind uwtable {
+  ;store volatile i32 14, i32* %0, align 4, !tbaa !2
+  store volatile i32 14, i32* %0, align 4
+  ret void
+}
+
+; TEST 7 - negative, should not deduce "nosync"
+; volatile load.
+; int volatile_load(volatile int *num) {
+;   int n = *num;
+;   return n;
+; }
+
+; CHECK: Function Attrs: norecurse nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define i32 @volatile_load(i32*)
+define i32 @volatile_load(i32*) norecurse nounwind uwtable {
+  ;%2 = load volatile i32, i32* %0, align 4, !tbaa !2
+  %2 = load volatile i32, i32* %0, align 4
+  ret i32 %2
+}
+
+; TEST 8 
+declare void @nosync_function() noinline nounwind uwtable
+
+; FIXME: missing "nosync"
+; CHECK: Function Attrs: noinline nounwind uwtable
+; CHECK: define void @call_nosync_function()
+define void @call_nosync_function() nounwind uwtable noinline {
+  tail call void @nosync_function() noinline nounwind uwtable
+  ret void
+}
+
+; TEST 9 - negative, should not deduce "nosync"
+declare void @might_sync() noinline nounwind uwtable
+
+; CHECK: Function Attrs: noinline nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK: define void @call_might_sync()
+define void @call_might_sync() nounwind uwtable noinline {
+  tail call void @might_sync() noinline nounwind uwtable
+  ret void
+}
+
+; TEST 10 - negative, should not deduce "nosync"
+; volatile operation in same scc. Call volatile_load defined in TEST 7.
+
+; CHECK: Function Attrs: noinline nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define i32 @scc1(i32*)
+define i32 @scc1(i32*) noinline nounwind uwtable {
+  tail call void @scc2(i32* %0);
+  %val = tail call i32 @volatile_load(i32* %0);
+  ret i32 %val;
+}
+
+; CHECK: Function Attrs: noinline nounwind uwtable
+; CHECK-NOT: nosync
+; CHECK-NEXT: define void @scc2(i32*)
+define void @scc2(i32*) noinline nounwind uwtable {
+  tail call i32 @scc1(i32* %0);
+  ret void;
+}