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. + ``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 @@ -6,10 +6,10 @@ // //===----------------------------------------------------------------------===// // -// This file implements an inter procedural pass that deduces and/or propagating -// attributes. This is done in an abstract interpretation style fixpoint -// iteration. See the Attributor.h file comment and the class descriptions in -// that file for more information. +// This file implements an inter procedural pass that deduces and/or propagates +// attributes along the way. This is done in an abstract interpretation style +// fixpoint iteration. See the Attributor.h file comment and the class +// descriptions in that file for more information. // //===----------------------------------------------------------------------===// @@ -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. // @@ -63,16 +64,6 @@ cl::desc("Disable the attributor inter-procedural deduction pass."), cl::init(false)); -static cl::opt VerifyAttributor( - "attributor-verify", cl::Hidden, - cl::desc("Verify the Attributor deduction and manifestation of attributes"), -#ifdef EXPENSIVE_CHECKS - cl::init(true) -#else - cl::init(false) -#endif -); - /// Logic operators for the change status enum class. /// ///{ @@ -84,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 == "nosync") + NumFnNoSync++; + return; + } + if (!Attr.isEnumAttribute()) return; switch (Attr.getKindAsEnum()) { @@ -117,7 +199,10 @@ if (!Old.isIntAttribute()) return true; - return Old.getValueAsInt() >= New.getValueAsInt(); + if (Old.getValueAsInt() >= New.getValueAsInt()) + return true; + + return false; } /// Return true if the information provided by \p Attr was added to the @@ -210,6 +295,7 @@ if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo)) continue; + // Bookkeeping. HasChanged = ChangeStatus::CHANGED; bookkeeping(MP, Attr); } @@ -246,6 +332,130 @@ 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 if "nosync" is assumed. + bool isAssumedNoSync() const { return getAssumed(); } + + /// Returns true of "nosync" is known. + bool isKnownNoSync() const { return getKnown(); } + + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::None - 2); + + AtomicOrdering getOrdering(Instruction *I) const; + + bool isVolatile(Instruction *I) const; +}; + +/// Helper function used to get ordering of an atomic instruction. +AtomicOrdering AANoSyncFunction::getOrdering(Instruction *I) const { + AtomicOrdering Success, Failure; + switch (I->getOpcode()) { + case Instruction::AtomicRMW: + return cast(I)->getOrdering(); + case Instruction::Store: + return cast(I)->getOrdering(); + case Instruction::Load: + return cast(I)->getOrdering(); + case Instruction::Fence: + return cast(I)->getOrdering(); + case Instruction::AtomicCmpXchg: + Success = cast(I)->getSuccessOrdering(); + Failure = cast(I)->getFailureOrdering(); + if (Success == AtomicOrdering::Unordered || + Success == AtomicOrdering::Monotonic) + return Failure; + return Success; + default: + return AtomicOrdering::NotAtomic; + } +} + +/// Helper function used to determine whether an instruction is volatile. +bool AANoSyncFunction::isVolatile(Instruction *I) const { + switch (I->getOpcode()) { + case Instruction::AtomicRMW: + return cast(I)->isVolatile(); + case Instruction::Store: + return cast(I)->isVolatile(); + case Instruction::Load: + return cast(I)->isVolatile(); + case Instruction::AtomicCmpXchg: + return cast(I)->isVolatile(); + default: + return false; + } +} + +ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + /// We are looking for volatile instructions or Non-Relaxed atomics. + /// FIXME: We should ipmrove the handling of intrinsics. + for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) { + ImmutableCallSite ICS(I); + auto *NoSyncAA = A.getAAFor(*this, *I); + + if ((!NoSyncAA || !NoSyncAA->isAssumedNoSync()) && + !ICS.hasFnAttr("nosync") && !ICS.hasFnAttr("readnone")) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + if (!isVolatile(I) && !I->isAtomic()) + continue; + + AtomicOrdering Ordering = getOrdering(I); + + if ((Ordering == AtomicOrdering::Unordered || + Ordering == AtomicOrdering::Monotonic) && + !isVolatile(I)) + continue; + + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + return ChangeStatus::UNCHANGED; +} /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -299,8 +509,6 @@ << IterationCounter << "/" << MaxFixpointIterations << " iterations\n"); - bool FinishedAtFixpoint = Worklist.empty(); - // Reset abstract arguments not settled in a sound fixpoint by now. This // happens when we stopped the fixpoint iteration early. Note that only the // ones marked as "changed" *and* the ones transitively depending on them @@ -316,6 +524,7 @@ if (!State.isAtFixpoint()) { State.indicatePessimisticFixpoint(); + // Bookkeeping. NumAttributesTimedOut++; } @@ -335,10 +544,9 @@ for (AbstractAttribute *AA : AllAbstractAttributes) { AbstractState &State = AA->getState(); - // If there is not already a fixpoint reached, we can now take the - // optimistic state. This is correct because we enforced a pessimistic one - // on abstract attributes that were transitively dependent on a changed one - // already above. + // If there is not already a fixpoint reached we can now take the optimistic + // state because we enforced a pessimistic one on abstract attributes we + // needed to above. if (!State.isAtFixpoint()) State.indicateOptimisticFixpoint(); @@ -360,23 +568,7 @@ << " arguments while " << NumAtFixpoint << " were in a valid fixpoint state\n"); - // If verification is requested, we finished this run at a fixpoint, and the - // IR was changed, we re-run the whole fixpoint analysis, starting at - // re-initialization of the arguments. This re-run should not result in an IR - // change. Though, the (virtual) state of attributes at the end of the re-run - // might be more optimistic than the known state or the IR state if the better - // state cannot be manifested. - if (VerifyAttributor && FinishedAtFixpoint && - ManifestChange == ChangeStatus::CHANGED) { - VerifyAttributor = false; - ChangeStatus VerifyStatus = run(); - if (VerifyStatus != ChangeStatus::UNCHANGED) - llvm_unreachable( - "Attributor verification failed, re-run did result in an IR change " - "even after a fixpoint was reached in the original run."); - VerifyAttributor = true; - } - + // Bookkeeping. NumAttributesManifested += NumManifested; NumAttributesValidFixpoint += NumAtFixpoint; @@ -387,6 +579,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. @@ -399,6 +594,11 @@ switch (I.getOpcode()) { default: break; + case Instruction::Load: + case Instruction::Store: + case Instruction::AtomicRMW: + case Instruction::Fence: + IsInterestingOpcode = true; } if (IsInterestingOpcode) InstOpcodeMap[I.getOpcode()].push_back(&I); @@ -455,7 +655,7 @@ LLVM_DEBUG(dbgs() << "[Attributor] Run on SCC with " << SCC.size() << " functions.\n"); - // Create an Attributor and initially empty information cache that is filled + // Create an attributor and initially empty informatin cache that is filled // while we identify default attribute opportunities. Attributor A; InformationCache InfoCache; @@ -470,6 +670,8 @@ // information was found we could duplicate the functions that do not // have an exact definition. if (!F->hasExactDefinition()) { + + // Bookkeeping. NumFnWithoutExactDefinition++; continue; } @@ -479,12 +681,14 @@ F->hasFnAttribute(Attribute::OptimizeNone)) continue; + // Bookkeeping. NumFnWithExactDefinition++; + // Sanity check. assert(!F->isDeclaration() && "Expected a definition not a declaration!"); - // Populate the Attributor with abstract attribute opportunities in the - // function and the information cache with IR information. + // Populate the attributor with abstract attribute opportunities in the + // function and te information cache with IR information. A.identifyDefaultAbstractAttributes(*F, InfoCache); } @@ -503,8 +707,8 @@ } if (runAttributorOnSCC(SCCFunctions)) - return PreservedAnalyses::none(); - return PreservedAnalyses::all(); + return PreservedAnalyses::all(); + return PreservedAnalyses::none(); } namespace {