diff --git a/llvm/docs/LangRef.rst b/llvm/docs/LangRef.rst --- a/llvm/docs/LangRef.rst +++ b/llvm/docs/LangRef.rst @@ -1472,6 +1472,11 @@ 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 @@ -1707,7 +1712,7 @@ 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 +#. 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. @@ -1866,7 +1871,7 @@ 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) ] diff --git a/llvm/include/llvm/IR/Attributes.td b/llvm/include/llvm/IR/Attributes.td --- a/llvm/include/llvm/IR/Attributes.td +++ b/llvm/include/llvm/IR/Attributes.td @@ -106,6 +106,9 @@ /// 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">; diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -1,6 +1,6 @@ -//===- 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 // @@ -44,6 +44,7 @@ "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. // @@ -74,12 +75,103 @@ } ///} +/// 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()) { @@ -240,6 +332,118 @@ return const_cast(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 &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(I)->getOrdering(); + case Instruction::Store: + return cast(I)->getOrdering(); + case Instruction::Load: + return cast(I)->getOrdering(); + default: + return AtomicOrdering::NotAtomic; + } +} + +bool isVolatile(Instruction *I) { + switch (I->getOpcode()) { + case Instruction::AtomicRMW: + return cast(I)->isVolatile(); + case Instruction::Store: + return cast(I)->isVolatile(); + case Instruction::Load: + return cast(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(*this, *I); + if ((!NoSyncAA || !NoSyncAA->isAssumedNoSync()) && + !ICS.hasFnAttr("nosync") && !ICS.hasFnAttr("readnone")) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + } + indicateOptimisticFixpoint(); + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -363,6 +567,9 @@ Function &F, InformationCache &InfoCache, DenseSet *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. @@ -375,6 +582,10 @@ switch (I.getOpcode()) { default: break; + case Instruction::Load: + case Instruction::Store: + case Instruction::AtomicRMW: + IsInterestingOpcode = true; } if (IsInterestingOpcode) InstOpcodeMap[I.getOpcode()].push_back(&I); diff --git a/llvm/test/Transforms/FunctionAttrs/nosync.ll b/llvm/test/Transforms/FunctionAttrs/nosync.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FunctionAttrs/nosync.ll @@ -0,0 +1,165 @@ +; 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; +}