| //===--- DiagnoseStaticExclusivity.cpp - Find violations of exclusivity ---===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements a diagnostic pass that finds violations of the |
| // "Law of Exclusivity" at compile time. The Law of Exclusivity requires |
| // that the access duration of any access to an address not overlap |
| // with an access to the same address unless both accesses are reads. |
| // |
| // This pass relies on 'begin_access' and 'end_access' SIL instruction |
| // markers inserted during SILGen to determine when an access to an address |
| // begins and ends. It models the in-progress accesses with a map from |
| // storage locations to the counts of read and write-like accesses in progress |
| // for that location. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "static-exclusivity" |
| #include "swift/AST/ASTWalker.h" |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/DiagnosticsSIL.h" |
| #include "swift/AST/Expr.h" |
| #include "swift/AST/Stmt.h" |
| #include "swift/Basic/SourceLoc.h" |
| #include "swift/Parse/Lexer.h" |
| #include "swift/SIL/CFG.h" |
| #include "swift/SIL/InstructionUtils.h" |
| #include "swift/SIL/MemAccessUtils.h" |
| #include "swift/SIL/Projection.h" |
| #include "swift/SIL/SILArgument.h" |
| #include "swift/SIL/SILInstruction.h" |
| #include "swift/SILOptimizer/Analysis/AccessSummaryAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h" |
| #include "swift/SILOptimizer/PassManager/Passes.h" |
| #include "swift/SILOptimizer/PassManager/Transforms.h" |
| #include "llvm/ADT/PostOrderIterator.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| |
| using namespace swift; |
| |
| template <typename... T, typename... U> |
| static InFlightDiagnostic diagnose(ASTContext &Context, SourceLoc loc, |
| Diag<T...> diag, U &&... args) { |
| return Context.Diags.diagnose(loc, diag, std::forward<U>(args)...); |
| } |
| |
| namespace { |
| |
| enum class RecordedAccessKind { |
| /// The access was for a 'begin_access' instruction in the current function |
| /// being checked. |
| BeginInstruction, |
| |
| /// The access was inside noescape closure that we either |
| /// passed to function or called directly. It results from applying the |
| /// the summary of the closure to the closure's captures. |
| NoescapeClosureCapture |
| }; |
| |
| /// Records an access to an address and the single subpath of projections |
| /// that was performed on the address, if such a single subpath exists. |
| class RecordedAccess { |
| private: |
| RecordedAccessKind RecordKind; |
| |
| union { |
| BeginAccessInst *Inst; |
| struct { |
| SILAccessKind ClosureAccessKind; |
| SILLocation ClosureAccessLoc; |
| }; |
| }; |
| |
| const IndexTrieNode *SubPath; |
| public: |
| RecordedAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) : |
| RecordKind(RecordedAccessKind::BeginInstruction), Inst(BAI), |
| SubPath(SubPath) { } |
| |
| RecordedAccess(SILAccessKind ClosureAccessKind, |
| SILLocation ClosureAccessLoc, const IndexTrieNode *SubPath) : |
| RecordKind(RecordedAccessKind::NoescapeClosureCapture), |
| ClosureAccessKind(ClosureAccessKind), ClosureAccessLoc(ClosureAccessLoc), |
| SubPath(SubPath) { } |
| |
| RecordedAccessKind getRecordKind() const { |
| return RecordKind; |
| } |
| |
| BeginAccessInst *getInstruction() const { |
| assert(RecordKind == RecordedAccessKind::BeginInstruction); |
| return Inst; |
| } |
| |
| SILAccessKind getAccessKind() const { |
| switch (RecordKind) { |
| case RecordedAccessKind::BeginInstruction: |
| return Inst->getAccessKind(); |
| case RecordedAccessKind::NoescapeClosureCapture: |
| return ClosureAccessKind; |
| }; |
| } |
| |
| SILLocation getAccessLoc() const { |
| switch (RecordKind) { |
| case RecordedAccessKind::BeginInstruction: |
| return Inst->getLoc(); |
| case RecordedAccessKind::NoescapeClosureCapture: |
| return ClosureAccessLoc; |
| }; |
| } |
| |
| const IndexTrieNode *getSubPath() const { |
| return SubPath; |
| } |
| }; |
| |
| |
| /// Records the in-progress accesses to a given sub path. |
| class SubAccessInfo { |
| public: |
| SubAccessInfo(const IndexTrieNode *P) : Path(P) {} |
| |
| const IndexTrieNode *Path; |
| |
| /// The number of in-progress 'read' accesses (that is 'begin_access [read]' |
| /// instructions that have not yet had the corresponding 'end_access'). |
| unsigned Reads = 0; |
| |
| /// The number of in-progress write-like accesses. |
| unsigned NonReads = 0; |
| |
| /// The instruction that began the first in-progress access to the storage |
| /// location. Used for diagnostic purposes. |
| Optional<RecordedAccess> FirstAccess = None; |
| |
| public: |
| /// Increment the count for given access. |
| void beginAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) { |
| if (!FirstAccess) { |
| assert(Reads == 0 && NonReads == 0); |
| FirstAccess = RecordedAccess(BAI, SubPath); |
| } |
| |
| if (BAI->getAccessKind() == SILAccessKind::Read) |
| Reads++; |
| else |
| NonReads++; |
| } |
| |
| /// Decrement the count for given access. |
| void endAccess(EndAccessInst *EAI) { |
| if (EAI->getBeginAccess()->getAccessKind() == SILAccessKind::Read) |
| Reads--; |
| else |
| NonReads--; |
| |
| // If all open accesses are now ended, forget the location of the |
| // first access. |
| if (Reads == 0 && NonReads == 0) |
| FirstAccess = None; |
| } |
| |
| /// Returns true when there are any accesses to this location in progress. |
| bool hasAccessesInProgress() const { return Reads > 0 || NonReads > 0; } |
| |
| /// Returns true when there must have already been a conflict diagnosed |
| /// for an in-progress access. Used to suppress multiple diagnostics for |
| /// the same underlying access violation. |
| bool alreadyHadConflict() const { |
| return (NonReads > 0 && Reads > 0) || (NonReads > 1); |
| } |
| |
| // Returns true when beginning an access of the given Kind can |
| // result in a conflict with a previous access. |
| bool canConflictWithAccessOfKind(SILAccessKind Kind) const { |
| if (Kind == SILAccessKind::Read) { |
| // A read conflicts with any non-read accesses. |
| return NonReads > 0; |
| } |
| |
| // A non-read access conflicts with any other access. |
| return NonReads > 0 || Reads > 0; |
| } |
| |
| bool conflictsWithAccess(SILAccessKind Kind, |
| const IndexTrieNode *SubPath) const { |
| if (!canConflictWithAccessOfKind(Kind)) |
| return false; |
| |
| return pathsConflict(Path, SubPath); |
| } |
| |
| /// Returns true when the two subpaths access overlapping memory. |
| bool pathsConflict(const IndexTrieNode *Path1, |
| const IndexTrieNode *Path2) const { |
| return Path1->isPrefixOf(Path2) || Path2->isPrefixOf(Path1); |
| } |
| }; |
| |
| /// Models the in-progress accesses for an address on which access has begun |
| /// with a begin_access instruction. For a given address, tracks the |
| /// count and kinds of accesses as well as the subpaths (i.e., projections) that |
| /// were accessed. |
| class AccessInfo { |
| using SubAccessVector = SmallVector<SubAccessInfo, 4>; |
| |
| SubAccessVector SubAccesses; |
| |
| /// Returns the SubAccess info for accessing at the given SubPath. |
| SubAccessInfo &findOrCreateSubAccessInfo(const IndexTrieNode *SubPath) { |
| for (auto &Info : SubAccesses) { |
| if (Info.Path == SubPath) |
| return Info; |
| } |
| |
| SubAccesses.emplace_back(SubPath); |
| return SubAccesses.back(); |
| } |
| |
| SubAccessVector::const_iterator |
| findFirstSubPathWithConflict(SILAccessKind OtherKind, |
| const IndexTrieNode *OtherSubPath) const { |
| // Note this iteration requires deterministic ordering for repeatable |
| // diagnostics. |
| for (auto I = SubAccesses.begin(), E = SubAccesses.end(); I != E; ++I) { |
| const SubAccessInfo &Access = *I; |
| if (Access.conflictsWithAccess(OtherKind, OtherSubPath)) |
| return I; |
| } |
| |
| return SubAccesses.end(); |
| } |
| |
| public: |
| // Returns the previous access when beginning an access of the given Kind will |
| // result in a conflict with a previous access. |
| Optional<RecordedAccess> |
| conflictsWithAccess(SILAccessKind Kind, const IndexTrieNode *SubPath) const { |
| auto I = findFirstSubPathWithConflict(Kind, SubPath); |
| if (I == SubAccesses.end()) |
| return None; |
| |
| return I->FirstAccess; |
| } |
| |
| /// Returns true if any subpath of has already had a conflict. |
| bool alreadyHadConflict() const { |
| for (const auto &SubAccess : SubAccesses) { |
| if (SubAccess.alreadyHadConflict()) |
| return true; |
| } |
| return false; |
| } |
| |
| /// Returns true when there are any accesses to this location in progress. |
| bool hasAccessesInProgress() const { |
| for (const auto &SubAccess : SubAccesses) { |
| if (SubAccess.hasAccessesInProgress()) |
| return true; |
| } |
| return false; |
| } |
| |
| /// Increment the count for given access. |
| void beginAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) { |
| SubAccessInfo &SubAccess = findOrCreateSubAccessInfo(SubPath); |
| SubAccess.beginAccess(BAI, SubPath); |
| } |
| |
| /// Decrement the count for given access. |
| void endAccess(EndAccessInst *EAI, const IndexTrieNode *SubPath) { |
| SubAccessInfo &SubAccess = findOrCreateSubAccessInfo(SubPath); |
| SubAccess.endAccess(EAI); |
| } |
| }; |
| |
| /// Indicates whether a 'begin_access' requires exclusive access |
| /// or allows shared access. This needs to be kept in sync with |
| /// diag::exclusivity_access_required, exclusivity_access_required_swift3, |
| /// and diag::exclusivity_conflicting_access. |
| enum class ExclusiveOrShared_t : unsigned { |
| ExclusiveAccess = 0, |
| SharedAccess = 1 |
| }; |
| |
| |
| /// Tracks the in-progress accesses on per-storage-location basis. |
| using StorageMap = llvm::SmallDenseMap<AccessedStorage, AccessInfo, 4>; |
| |
| /// Represents two accesses that conflict and their underlying storage. |
| struct ConflictingAccess { |
| private: |
| |
| /// If true, always diagnose this conflict as a warning. This is useful for |
| /// staging in fixes for false negatives without affecting source |
| /// compatibility. |
| bool AlwaysDiagnoseAsWarning = false; |
| public: |
| /// Create a conflict for two begin_access instructions in the same function. |
| ConflictingAccess(const AccessedStorage &Storage, const RecordedAccess &First, |
| const RecordedAccess &Second) |
| : Storage(Storage), FirstAccess(First), SecondAccess(Second) {} |
| |
| const AccessedStorage Storage; |
| const RecordedAccess FirstAccess; |
| const RecordedAccess SecondAccess; |
| |
| bool getAlwaysDiagnoseAsWarning() const { return AlwaysDiagnoseAsWarning; } |
| void setAlwaysDiagnoseAsWarning(bool AlwaysDiagnoseAsWarning) { |
| this->AlwaysDiagnoseAsWarning = AlwaysDiagnoseAsWarning; |
| } |
| }; |
| |
| } // end anonymous namespace |
| |
| /// Returns whether an access of the given kind requires exclusive or shared |
| /// access to its storage. |
| static ExclusiveOrShared_t getRequiredAccess(SILAccessKind Kind) { |
| if (Kind == SILAccessKind::Read) |
| return ExclusiveOrShared_t::SharedAccess; |
| |
| return ExclusiveOrShared_t::ExclusiveAccess; |
| } |
| |
| /// Extract the text for the given expression. |
| static StringRef extractExprText(const Expr *E, SourceManager &SM) { |
| const auto CSR = Lexer::getCharSourceRangeFromSourceRange(SM, |
| E->getSourceRange()); |
| return SM.extractText(CSR); |
| } |
| |
| /// Returns true when the call expression is a call to swap() in the Standard |
| /// Library. |
| /// This is a helper function that is only used in an assertion, which is why |
| /// it is in the ifndef. |
| #ifndef NDEBUG |
| static bool isCallToStandardLibrarySwap(CallExpr *CE, ASTContext &Ctx) { |
| if (CE->getCalledValue() == Ctx.getSwap(nullptr)) |
| return true; |
| |
| // Is the call module qualified, i.e. Swift.swap(&a[i], &[j)? |
| if (auto *DSBIE = dyn_cast<DotSyntaxBaseIgnoredExpr>(CE->getFn())) { |
| if (auto *DRE = dyn_cast<DeclRefExpr>(DSBIE->getRHS())) { |
| return DRE->getDecl() == Ctx.getSwap(nullptr); |
| } |
| } |
| |
| return false; |
| } |
| #endif |
| |
| /// Do a syntactic pattern match to determine whether the call is a call |
| /// to swap(&base[index1], &base[index2]), which can |
| /// be replaced with a call to MutableCollection.swapAt(_:_:) on base. |
| /// |
| /// Returns true if the call can be replaced. Returns the call expression, |
| /// the base expression, and the two indices as out expressions. |
| /// |
| /// This method takes an array of all the ApplyInsts for calls to swap() |
| /// in the function to avoid needing to construct a parent map over the AST |
| /// to find the CallExpr for the inout accesses. |
| static bool |
| canReplaceWithCallToCollectionSwapAt(const BeginAccessInst *Access1, |
| const BeginAccessInst *Access2, |
| ArrayRef<ApplyInst *> CallsToSwap, |
| ASTContext &Ctx, |
| CallExpr *&FoundCall, |
| Expr *&Base, |
| Expr *&Index1, |
| Expr *&Index2) { |
| if (CallsToSwap.empty()) |
| return false; |
| |
| // Inout arguments must be modifications. |
| if (Access1->getAccessKind() != SILAccessKind::Modify || |
| Access2->getAccessKind() != SILAccessKind::Modify) { |
| return false; |
| } |
| |
| SILLocation Loc1 = Access1->getLoc(); |
| SILLocation Loc2 = Access2->getLoc(); |
| if (Loc1.isNull() || Loc2.isNull()) |
| return false; |
| |
| auto *InOut1 = Loc1.getAsASTNode<InOutExpr>(); |
| auto *InOut2 = Loc2.getAsASTNode<InOutExpr>(); |
| if (!InOut1 || !InOut2) |
| return false; |
| |
| FoundCall = nullptr; |
| // Look through all the calls to swap() recorded in the function to find |
| // which one we're diagnosing. |
| for (ApplyInst *AI : CallsToSwap) { |
| SILLocation CallLoc = AI->getLoc(); |
| if (CallLoc.isNull()) |
| continue; |
| |
| auto *CE = CallLoc.getAsASTNode<CallExpr>(); |
| if (!CE) |
| continue; |
| |
| assert(isCallToStandardLibrarySwap(CE, Ctx)); |
| // swap() takes two arguments. |
| auto *ArgTuple = cast<TupleExpr>(CE->getArg()); |
| const Expr *Arg1 = ArgTuple->getElement(0); |
| const Expr *Arg2 = ArgTuple->getElement(1); |
| if ((Arg1 == InOut1 && Arg2 == InOut2)) { |
| FoundCall = CE; |
| break; |
| } |
| } |
| if (!FoundCall) |
| return false; |
| |
| // We found a call to swap(&e1, &e2). Now check to see whether it |
| // matches the form swap(&someCollection[index1], &someCollection[index2]). |
| auto *SE1 = dyn_cast<SubscriptExpr>(InOut1->getSubExpr()); |
| if (!SE1) |
| return false; |
| auto *SE2 = dyn_cast<SubscriptExpr>(InOut2->getSubExpr()); |
| if (!SE2) |
| return false; |
| |
| // Do the two subscripts refer to the same subscript declaration? |
| auto *Decl1 = cast<SubscriptDecl>(SE1->getDecl().getDecl()); |
| auto *Decl2 = cast<SubscriptDecl>(SE2->getDecl().getDecl()); |
| if (Decl1 != Decl2) |
| return false; |
| |
| ProtocolDecl *MutableCollectionDecl = Ctx.getMutableCollectionDecl(); |
| |
| // Is the subcript either (1) on MutableCollection itself or (2) a |
| // a witness for a subscript on MutableCollection? |
| bool IsSubscriptOnMutableCollection = false; |
| ProtocolDecl *ProtocolForDecl = |
| Decl1->getDeclContext()->getAsProtocolOrProtocolExtensionContext(); |
| if (ProtocolForDecl) { |
| IsSubscriptOnMutableCollection = (ProtocolForDecl == MutableCollectionDecl); |
| } else { |
| for (ValueDecl *Req : Decl1->getSatisfiedProtocolRequirements()) { |
| DeclContext *ReqDC = Req->getDeclContext(); |
| ProtocolDecl *ReqProto = ReqDC->getAsProtocolOrProtocolExtensionContext(); |
| assert(ReqProto && "Protocol requirement not in a protocol?"); |
| |
| if (ReqProto == MutableCollectionDecl) { |
| IsSubscriptOnMutableCollection = true; |
| break; |
| } |
| } |
| } |
| |
| if (!IsSubscriptOnMutableCollection) |
| return false; |
| |
| // We're swapping two subscripts on mutable collections -- but are they |
| // the same collection? Approximate this by checking for textual |
| // equality on the base expressions. This is just an approximation, |
| // but is fine for a best-effort Fix-It. |
| SourceManager &SM = Ctx.SourceMgr; |
| StringRef Base1Text = extractExprText(SE1->getBase(), SM); |
| StringRef Base2Text = extractExprText(SE2->getBase(), SM); |
| |
| if (Base1Text != Base2Text) |
| return false; |
| |
| auto *Index1Paren = dyn_cast<ParenExpr>(SE1->getIndex()); |
| if (!Index1Paren) |
| return false; |
| |
| auto *Index2Paren = dyn_cast<ParenExpr>(SE2->getIndex()); |
| if (!Index2Paren) |
| return false; |
| |
| Base = SE1->getBase(); |
| Index1 = Index1Paren->getSubExpr(); |
| Index2 = Index2Paren->getSubExpr(); |
| return true; |
| } |
| |
| /// Suggest replacing with call with a call to swapAt(). |
| static void addSwapAtFixit(InFlightDiagnostic &Diag, CallExpr *&FoundCall, |
| Expr *Base, Expr *&Index1, Expr *&Index2, |
| SourceManager &SM) { |
| StringRef BaseText = extractExprText(Base, SM); |
| StringRef Index1Text = extractExprText(Index1, SM); |
| StringRef Index2Text = extractExprText(Index2, SM); |
| SmallString<64> FixItText; |
| { |
| llvm::raw_svector_ostream Out(FixItText); |
| Out << BaseText << ".swapAt(" << Index1Text << ", " << Index2Text << ")"; |
| } |
| |
| Diag.fixItReplace(FoundCall->getSourceRange(), FixItText); |
| } |
| |
| /// Returns a string representation of the BaseName and the SubPath |
| /// suitable for use in diagnostic text. Only supports the Projections |
| /// that stored-property relaxation supports: struct stored properties |
| /// and tuple elements. |
| static std::string getPathDescription(DeclName BaseName, SILType BaseType, |
| const IndexTrieNode *SubPath, |
| SILModule &M) { |
| std::string sbuf; |
| llvm::raw_string_ostream os(sbuf); |
| |
| os << "'" << BaseName; |
| os << AccessSummaryAnalysis::getSubPathDescription(BaseType, SubPath, M); |
| os << "'"; |
| |
| return os.str(); |
| } |
| |
| /// Emits a diagnostic if beginning an access with the given in-progress |
| /// accesses violates the law of exclusivity. Returns true when a |
| /// diagnostic was emitted. |
| static void diagnoseExclusivityViolation(const ConflictingAccess &Violation, |
| ArrayRef<ApplyInst *> CallsToSwap, |
| ASTContext &Ctx) { |
| |
| const AccessedStorage &Storage = Violation.Storage; |
| const RecordedAccess &FirstAccess = Violation.FirstAccess; |
| const RecordedAccess &SecondAccess = Violation.SecondAccess; |
| SILFunction *F = FirstAccess.getInstruction()->getFunction(); |
| |
| DEBUG(llvm::dbgs() << "Conflict on " << *FirstAccess.getInstruction() |
| << "\n vs " << *SecondAccess.getInstruction() |
| << "\n in function " << *F); |
| |
| // Can't have a conflict if both accesses are reads. |
| assert(!(FirstAccess.getAccessKind() == SILAccessKind::Read && |
| SecondAccess.getAccessKind() == SILAccessKind::Read)); |
| |
| ExclusiveOrShared_t FirstRequires = |
| getRequiredAccess(FirstAccess.getAccessKind()); |
| |
| // Diagnose on the first access that requires exclusivity. |
| bool FirstIsMain = (FirstRequires == ExclusiveOrShared_t::ExclusiveAccess); |
| const RecordedAccess &MainAccess = (FirstIsMain ? FirstAccess : SecondAccess); |
| const RecordedAccess &NoteAccess = (FirstIsMain ? SecondAccess : FirstAccess); |
| |
| SourceRange RangeForMain = MainAccess.getAccessLoc().getSourceRange(); |
| unsigned AccessKindForMain = |
| static_cast<unsigned>(MainAccess.getAccessKind()); |
| |
| // For now, all exclusivity violations are warning in Swift 3 mode. |
| // Also treat some violations as warnings to allow them to be staged in. |
| bool DiagnoseAsWarning = Violation.getAlwaysDiagnoseAsWarning() || |
| Ctx.LangOpts.isSwiftVersion3(); |
| |
| if (const ValueDecl *VD = Storage.getDecl(F)) { |
| // We have a declaration, so mention the identifier in the diagnostic. |
| auto DiagnosticID = (DiagnoseAsWarning ? |
| diag::exclusivity_access_required_warn : |
| diag::exclusivity_access_required); |
| SILType BaseType = FirstAccess.getInstruction()->getType().getAddressType(); |
| SILModule &M = FirstAccess.getInstruction()->getModule(); |
| std::string PathDescription = getPathDescription( |
| VD->getBaseName(), BaseType, MainAccess.getSubPath(), M); |
| |
| // Determine whether we can safely suggest replacing the violation with |
| // a call to MutableCollection.swapAt(). |
| bool SuggestSwapAt = false; |
| CallExpr *CallToReplace = nullptr; |
| Expr *Base = nullptr; |
| Expr *SwapIndex1 = nullptr; |
| Expr *SwapIndex2 = nullptr; |
| if (SecondAccess.getRecordKind() == RecordedAccessKind::BeginInstruction) { |
| SuggestSwapAt = canReplaceWithCallToCollectionSwapAt( |
| FirstAccess.getInstruction(), SecondAccess.getInstruction(), |
| CallsToSwap, Ctx, CallToReplace, Base, SwapIndex1, SwapIndex2); |
| } |
| |
| auto D = |
| diagnose(Ctx, MainAccess.getAccessLoc().getSourceLoc(), DiagnosticID, |
| PathDescription, AccessKindForMain, SuggestSwapAt); |
| D.highlight(RangeForMain); |
| if (SuggestSwapAt) |
| addSwapAtFixit(D, CallToReplace, Base, SwapIndex1, SwapIndex2, |
| Ctx.SourceMgr); |
| } else { |
| auto DiagnosticID = (DiagnoseAsWarning ? |
| diag::exclusivity_access_required_unknown_decl_warn : |
| diag::exclusivity_access_required_unknown_decl); |
| diagnose(Ctx, MainAccess.getAccessLoc().getSourceLoc(), DiagnosticID, |
| AccessKindForMain) |
| .highlight(RangeForMain); |
| } |
| diagnose(Ctx, NoteAccess.getAccessLoc().getSourceLoc(), |
| diag::exclusivity_conflicting_access) |
| .highlight(NoteAccess.getAccessLoc().getSourceRange()); |
| } |
| |
| /// Look through a value to find the underlying storage accessed. |
| static AccessedStorage findValidAccessedStorage(SILValue Source) { |
| const AccessedStorage &Storage = findAccessedStorage(Source); |
| if (!Storage) { |
| llvm::dbgs() << "Bad memory access source: " << Source; |
| llvm_unreachable("Unexpected access source."); |
| } |
| return Storage; |
| } |
| |
| /// Returns true when the apply calls the Standard Library swap(). |
| /// Used for fix-its to suggest replacing with Collection.swapAt() |
| /// on exclusivity violations. |
| static bool isCallToStandardLibrarySwap(ApplyInst *AI, ASTContext &Ctx) { |
| SILFunction *SF = AI->getReferencedFunction(); |
| if (!SF) |
| return false; |
| |
| if (!SF->hasLocation()) |
| return false; |
| |
| auto *FD = SF->getLocation().getAsASTNode<FuncDecl>(); |
| if (!FD) |
| return false; |
| |
| return FD == Ctx.getSwap(nullptr); |
| } |
| |
| static llvm::cl::opt<bool> ShouldAssertOnFailure( |
| "sil-assert-on-exclusivity-failure", |
| llvm::cl::desc("Should the compiler assert when it diagnoses conflicting " |
| "accesses rather than emitting a diagnostic? Intended for " |
| "use only with debugging.")); |
| |
| /// If making an access of the given kind at the given subpath would |
| /// would conflict, returns the first recorded access it would conflict |
| /// with. Otherwise, returns None. |
| static Optional<RecordedAccess> |
| shouldReportAccess(const AccessInfo &Info,swift::SILAccessKind Kind, |
| const IndexTrieNode *SubPath) { |
| if (Info.alreadyHadConflict()) |
| return None; |
| |
| auto result = Info.conflictsWithAccess(Kind, SubPath); |
| if (ShouldAssertOnFailure && result.hasValue()) |
| llvm_unreachable("Standard assertion routine."); |
| return result; |
| } |
| |
| /// For each projection that the summarized function accesses on its |
| /// capture, check whether the access conflicts with already-in-progress |
| /// access. Returns the most general summarized conflict -- so if there are |
| /// two conflicts in the called function and one is for an access to an |
| /// aggregate and another is for an access to a projection from the aggregate, |
| /// this will return the conflict for the aggregate. This approach guarantees |
| /// determinism and makes it more likely that we'll diagnose the most helpful |
| /// conflict. |
| static Optional<ConflictingAccess> |
| findConflictingArgumentAccess(const AccessSummaryAnalysis::ArgumentSummary &AS, |
| const AccessedStorage &AccessedStorage, |
| const AccessInfo &InProgressInfo) { |
| Optional<RecordedAccess> BestInProgressAccess; |
| Optional<RecordedAccess> BestArgAccess; |
| |
| for (const auto &MapPair : AS.getSubAccesses()) { |
| const IndexTrieNode *SubPath = MapPair.getFirst(); |
| const auto &SubAccess = MapPair.getSecond(); |
| SILAccessKind Kind = SubAccess.getAccessKind(); |
| auto InProgressAccess = shouldReportAccess(InProgressInfo, Kind, SubPath); |
| if (!InProgressAccess) |
| continue; |
| |
| if (!BestArgAccess || |
| AccessSummaryAnalysis::compareSubPaths(SubPath, |
| BestArgAccess->getSubPath())) { |
| SILLocation AccessLoc = SubAccess.getAccessLoc(); |
| |
| BestArgAccess = RecordedAccess(Kind, AccessLoc, SubPath); |
| BestInProgressAccess = InProgressAccess; |
| } |
| } |
| |
| if (!BestArgAccess) |
| return None; |
| |
| return ConflictingAccess(AccessedStorage, *BestInProgressAccess, |
| *BestArgAccess); |
| } |
| |
| /// Use the summary analysis to check whether a call to the given |
| /// function would conflict with any in progress accesses. The starting |
| /// index indicates what index into the the callee's parameters the |
| /// arguments array starts at -- this is useful for partial_apply functions, |
| /// which pass only a suffix of the callee's arguments at the apply site. |
| static void checkForViolationWithCall( |
| const StorageMap &Accesses, SILFunction *Callee, unsigned StartingAtIndex, |
| OperandValueArrayRef Arguments, AccessSummaryAnalysis *ASA, |
| bool DiagnoseAsWarning, |
| llvm::SmallVectorImpl<ConflictingAccess> &ConflictingAccesses) { |
| const AccessSummaryAnalysis::FunctionSummary &FS = |
| ASA->getOrCreateSummary(Callee); |
| |
| // For each argument in the suffix of the callee arguments being passed |
| // at this call site, determine whether the arguments will be accessed |
| // in a way that conflicts with any currently in progress accesses. |
| // If so, diagnose. |
| for (unsigned ArgumentIndex : indices(Arguments)) { |
| unsigned CalleeIndex = StartingAtIndex + ArgumentIndex; |
| |
| const AccessSummaryAnalysis::ArgumentSummary &AS = |
| FS.getAccessForArgument(CalleeIndex); |
| |
| const auto &SubAccesses = AS.getSubAccesses(); |
| |
| // Is the capture accessed in the callee? |
| if (SubAccesses.empty()) |
| continue; |
| |
| SILValue Argument = Arguments[ArgumentIndex]; |
| assert(Argument->getType().isAddress()); |
| |
| const AccessedStorage &Storage = findValidAccessedStorage(Argument); |
| auto AccessIt = Accesses.find(Storage); |
| |
| // Are there any accesses in progress at the time of the call? |
| if (AccessIt == Accesses.end()) |
| continue; |
| |
| const AccessInfo &Info = AccessIt->getSecond(); |
| if (auto Conflict = findConflictingArgumentAccess(AS, Storage, Info)) { |
| Conflict->setAlwaysDiagnoseAsWarning(DiagnoseAsWarning); |
| ConflictingAccesses.push_back(*Conflict); |
| } |
| } |
| } |
| |
| /// If the given values has a SILFunctionType or an Optional<SILFunctionType>, |
| /// return the SILFunctionType. Otherwise, return an invalid type. |
| static CanSILFunctionType getSILFunctionTypeForValue(SILValue arg) { |
| SILType argTy = arg->getType(); |
| // Handle `Optional<@convention(block) @noescape (_)->(_)>` |
| if (auto optionalObjTy = argTy.getOptionalObjectType()) |
| argTy = optionalObjTy; |
| |
| return argTy.getAs<SILFunctionType>(); |
| } |
| |
| /// Checks whether any of the arguments to the apply are closures and diagnoses |
| /// if any of the @inout_aliasable captures passed to those closures have |
| /// in-progress accesses that would conflict with any access the summary |
| /// says the closure would perform. |
| static void checkForViolationsInNoEscapeClosureArguments( |
| const StorageMap &Accesses, ApplySite AS, AccessSummaryAnalysis *ASA, |
| llvm::SmallVectorImpl<ConflictingAccess> &ConflictingAccesses, |
| bool DiagnoseAsWarning) { |
| |
| // Check for violation with closures passed as arguments |
| for (SILValue Argument : AS.getArguments()) { |
| auto fnType = getSILFunctionTypeForValue(Argument); |
| if (!fnType || !fnType->isNoEscape()) |
| continue; |
| |
| FindClosureResult result = findClosureForAppliedArg(Argument); |
| if (!result.PAI) |
| continue; |
| |
| SILFunction *Callee = result.PAI->getCalleeFunction(); |
| if (!Callee || Callee->empty()) |
| continue; |
| |
| // Check the closure's captures, which are a suffix of the closure's |
| // parameters. |
| unsigned StartIndex = |
| Callee->getArguments().size() - result.PAI->getNumArguments(); |
| checkForViolationWithCall(Accesses, Callee, StartIndex, |
| result.PAI->getArguments(), ASA, |
| /*DiagnoseAsWarning=*/false, ConflictingAccesses); |
| } |
| } |
| |
| /// Given a full apply site, diagnose if the apply either calls a closure |
| /// directly that conflicts with an in-progress access or takes a noescape |
| /// argument that, when called, would conflict with an in-progress access. |
| static void checkForViolationsInNoEscapeClosures( |
| const StorageMap &Accesses, FullApplySite FAS, AccessSummaryAnalysis *ASA, |
| llvm::SmallVectorImpl<ConflictingAccess> &ConflictingAccesses) { |
| // Check to make sure that calling a closure immediately will not result in |
| // a conflict. This diagnoses in cases where there is a conflict between an |
| // argument passed inout to the closure and an access inside the closure to a |
| // captured variable: |
| // |
| // var i = 7 |
| // ({ (p: inout Int) in i = 8})(&i) // Overlapping access to 'i' |
| // |
| SILFunction *Callee = FAS.getCalleeFunction(); |
| if (Callee && !Callee->empty()) { |
| // Check for violation with directly called closure |
| checkForViolationWithCall(Accesses, Callee, 0, FAS.getArguments(), ASA, |
| /*DiagnoseAsWarning=*/false, ConflictingAccesses); |
| } |
| |
| // Check to make sure that any arguments to the apply are not themselves |
| // noescape closures that -- when called -- might conflict with an in-progress |
| // access. For example, this will diagnose on the following: |
| // |
| // var i = 7 |
| // takesInoutAndClosure(&i) { i = 8 } // Overlapping access to 'i' |
| // |
| checkForViolationsInNoEscapeClosureArguments(Accesses, FAS, ASA, |
| ConflictingAccesses, |
| /*DiagnoseAsWarning=*/false); |
| } |
| |
| #ifndef NDEBUG |
| // If a partial apply has @inout_aliasable arguments, it may only be used as |
| // a @noescape function type in a way that is recognized by |
| // DiagnoseStaticExclusivity. |
| static void checkNoEscapePartialApply(PartialApplyInst *PAI) { |
| SmallVector<Operand *, 8> uses(PAI->getUses()); |
| while (!uses.empty()) { |
| Operand *oper = uses.pop_back_val(); |
| SILInstruction *user = oper->getUser(); |
| |
| if (isIncidentalUse(user) || onlyAffectsRefCount(user)) |
| continue; |
| |
| if (auto *MD = dyn_cast<MarkDependenceInst>(user)) { |
| if (oper->getOperandNumber() == MarkDependenceInst::Base) |
| continue; |
| uses.append(MD->getUses().begin(), MD->getUses().end()); |
| continue; |
| } |
| |
| if (SingleValueInstruction *copy = getSingleValueCopyOrCast(user)) { |
| uses.append(copy->getUses().begin(), copy->getUses().end()); |
| continue; |
| } |
| if (auto *cvt = dyn_cast<ConvertEscapeToNoEscapeInst>(user)) { |
| uses.append(cvt->getUses().begin(), cvt->getUses().end()); |
| continue; |
| } |
| // @noescape block storage can be passed as an Optional (Nullable). |
| if (EnumInst *EI = dyn_cast<EnumInst>(user)) { |
| uses.append(EI->getUses().begin(), EI->getUses().end()); |
| continue; |
| } |
| if (isa<ApplySite>(user)) { |
| SILValue arg = oper->get(); |
| auto ArgumentFnType = getSILFunctionTypeForValue(arg); |
| if (ArgumentFnType && ArgumentFnType->isNoEscape()) { |
| // Verify that the inverse operation, finding a partial_apply from a |
| // @noescape argument, is consistent. |
| assert(findClosureForAppliedArg(arg).PAI && |
| "cannot find partial_apply from @noescape function argument"); |
| continue; |
| } |
| llvm::dbgs() << "Argument must be @noescape function type: " << *arg; |
| llvm_unreachable("A partial_apply with @inout_aliasable may only be " |
| "used as a @noescape function type argument."); |
| } |
| auto *store = dyn_cast<StoreInst>(user); |
| if (store && oper->getOperandNumber() == StoreInst::Src) { |
| if (auto *PBSI = dyn_cast<ProjectBlockStorageInst>(store->getDest())) { |
| SILValue storageAddr = PBSI->getOperand(); |
| // The closure is stored to block storage. Recursively visit all |
| // uses of any initialized block storage values derived from this |
| // storage address.. |
| for (Operand *oper : storageAddr->getUses()) { |
| if (auto *IBS = dyn_cast<InitBlockStorageHeaderInst>(oper->getUser())) |
| uses.append(IBS->getUses().begin(), IBS->getUses().end()); |
| } |
| continue; |
| } |
| } |
| llvm::dbgs() << "Unexpected partial_apply use: " << *user; |
| llvm_unreachable("A partial_apply with @inout_aliasable may only be " |
| "used as a @noescape function type argument."); |
| } |
| } |
| #endif |
| |
| // Check that the given address-type operand is guarded by begin/end access |
| // markers. |
| static void checkAccessedAddress(Operand *memOper, StorageMap &Accesses) { |
| SILValue address = memOper->get(); |
| SILInstruction *memInst = memOper->getUser(); |
| |
| auto error = [address, memInst]() { |
| llvm::dbgs() << "Memory access not protected by begin_access:\n"; |
| memInst->printInContext(llvm::dbgs()); |
| llvm::dbgs() << "Accessing: " << address; |
| llvm::dbgs() << "In function:\n"; |
| memInst->getFunction()->print(llvm::dbgs()); |
| abort(); |
| }; |
| |
| // If the memory instruction is only used for initialization, it doesn't need |
| // an access marker. |
| if (memInstMustInitialize(memOper)) |
| return; |
| |
| if (auto apply = ApplySite::isa(memInst)) { |
| SILArgumentConvention conv = |
| apply.getArgumentConvention(apply.getCalleeArgIndex(*memOper)); |
| // Captured addresses currently use the @inout_aliasable convention. They |
| // are considered an access at any call site that uses the closure. However, |
| // those accesses are never explictly protected by access markers. Instead, |
| // exclusivity uses AccessSummaryAnalysis to check for conflicts. Here, we |
| // can simply ignore any @inout_aliasable arguments. |
| if (conv == SILArgumentConvention::Indirect_InoutAliasable) |
| return; |
| |
| assert(!isa<PartialApplyInst>(memInst) |
| && "partial apply can only capture an address as inout_aliasable"); |
| // TODO: We currently assume @in/@in_guaranteed are only used for |
| // pass-by-value arguments. i.e. the address points a local copy of the |
| // argument, which is only passed by address for abstraction |
| // reasons. However, in the future, @in_guaranteed may be used for |
| // borrowed values, which should be recognized as a formal read. |
| if (conv != SILArgumentConvention::Indirect_Inout) |
| return; |
| } |
| |
| // Strip off address projections, but not ref_element_addr. |
| const AccessedStorage &storage = findAccessedStorage(address); |
| // findAccessedStorage may return an invalid storage object if the address |
| // producer is not recognized by its whitelist. For the purpose of |
| // verification, we assume that this can only happen for local |
| // initialization, not a formal memory access. The strength of |
| // verification rests on the completeness of the opcode list inside |
| // findAccessedStorage. |
| if (!storage || !isPossibleFormalAccessBase(storage, memInst->getFunction())) |
| return; |
| |
| // A box or stack variable may represent lvalues, but they can only conflict |
| // with call sites in the same scope. Some initialization patters (stores to |
| // the local value) aren't protected by markers, so we need this check. |
| if (!isa<ApplySite>(memInst) |
| && (storage.getKind() == AccessedStorage::Box |
| || storage.getKind() == AccessedStorage::Stack)) { |
| return; |
| } |
| |
| // Otherwise, the address base should be an in-scope begin_access. |
| if (storage.getKind() == AccessedStorage::Nested) { |
| auto *BAI = cast<BeginAccessInst>(storage.getValue()); |
| const AccessedStorage &Storage = findValidAccessedStorage(BAI->getSource()); |
| AccessInfo &Info = Accesses[Storage]; |
| if (!Info.hasAccessesInProgress()) |
| error(); |
| return; |
| } |
| error(); |
| } |
| |
| static void checkStaticExclusivity(SILFunction &Fn, PostOrderFunctionInfo *PO, |
| AccessSummaryAnalysis *ASA) { |
| // The implementation relies on the following SIL invariants: |
| // - All incoming edges to a block must have the same in-progress |
| // accesses. This enables the analysis to not perform a data flow merge |
| // on incoming edges. |
| // - Further, for a given address each of the in-progress |
| // accesses must have begun in the same order on all edges. This ensures |
| // consistent diagnostics across changes to the exploration of the CFG. |
| // - On return from a function there are no in-progress accesses. This |
| // enables a sanity check for lean analysis state at function exit. |
| // - Each end_access instruction corresponds to exactly one begin access |
| // instruction. (This is encoded in the EndAccessInst itself) |
| // - begin_access arguments cannot be basic block arguments. |
| // This enables the analysis to look back to find the *single* storage |
| // storage location accessed. |
| |
| if (Fn.empty()) |
| return; |
| |
| bool VerifyMemOps = Fn.getModule().getOptions().VerifyExclusivity; |
| |
| // Collects calls the Standard Library swap() for Fix-Its. |
| llvm::SmallVector<ApplyInst *, 8> CallsToSwap; |
| |
| // Stores the accesses that have been found to conflict. Used to defer |
| // emitting diagnostics until we can determine whether they should |
| // be suppressed. |
| llvm::SmallVector<ConflictingAccess, 4> ConflictingAccesses; |
| |
| // For each basic block, track the stack of current accesses on |
| // exit from that block. |
| llvm::SmallDenseMap<SILBasicBlock *, Optional<StorageMap>, 32> |
| BlockOutAccesses; |
| |
| BlockOutAccesses[Fn.getEntryBlock()] = StorageMap(); |
| |
| for (auto *BB : PO->getReversePostOrder()) { |
| Optional<StorageMap> &BBState = BlockOutAccesses[BB]; |
| |
| // Because we use a reverse post-order traversal, unless this is the entry |
| // at least one of its predecessors must have been reached. Use the out |
| // state for that predecessor as our in state. The SIL verifier guarantees |
| // that all incoming edges must have the same current accesses. |
| for (auto *Pred : BB->getPredecessorBlocks()) { |
| auto it = BlockOutAccesses.find(Pred); |
| if (it == BlockOutAccesses.end()) |
| continue; |
| |
| const Optional<StorageMap> &PredAccesses = it->getSecond(); |
| if (PredAccesses) { |
| BBState = PredAccesses; |
| break; |
| } |
| } |
| |
| // The in-progress accesses for the current program point, represented |
| // as map from storage locations to the accesses in progress for the |
| // location. |
| StorageMap &Accesses = *BBState; |
| |
| for (auto &I : *BB) { |
| // Apply transfer functions. Beginning an access |
| // increments the read or write count for the storage location; |
| // Ending onr decrements the count. |
| if (auto *BAI = dyn_cast<BeginAccessInst>(&I)) { |
| SILAccessKind Kind = BAI->getAccessKind(); |
| const AccessedStorage &Storage = |
| findValidAccessedStorage(BAI->getSource()); |
| AccessInfo &Info = Accesses[Storage]; |
| const IndexTrieNode *SubPath = ASA->findSubPathAccessed(BAI); |
| if (auto Conflict = shouldReportAccess(Info, Kind, SubPath)) { |
| ConflictingAccesses.emplace_back(Storage, *Conflict, |
| RecordedAccess(BAI, SubPath)); |
| } |
| |
| Info.beginAccess(BAI, SubPath); |
| continue; |
| } |
| |
| if (auto *EAI = dyn_cast<EndAccessInst>(&I)) { |
| auto It = Accesses.find(findValidAccessedStorage(EAI->getSource())); |
| AccessInfo &Info = It->getSecond(); |
| |
| BeginAccessInst *BAI = EAI->getBeginAccess(); |
| const IndexTrieNode *SubPath = ASA->findSubPathAccessed(BAI); |
| Info.endAccess(EAI, SubPath); |
| |
| // If the storage location has no more in-progress accesses, remove |
| // it to keep the StorageMap lean. |
| if (!Info.hasAccessesInProgress()) |
| Accesses.erase(It); |
| continue; |
| } |
| |
| if (VerifyMemOps && I.mayReadOrWriteMemory()) { |
| visitAccessedAddress(&I, [&Accesses](Operand *memOper) { |
| checkAccessedAddress(memOper, Accesses); |
| }); |
| } |
| |
| if (auto *AI = dyn_cast<ApplyInst>(&I)) { |
| // Record calls to swap() for potential Fix-Its. |
| if (isCallToStandardLibrarySwap(AI, Fn.getASTContext())) |
| CallsToSwap.push_back(AI); |
| else |
| checkForViolationsInNoEscapeClosures(Accesses, AI, ASA, |
| ConflictingAccesses); |
| continue; |
| } |
| |
| if (auto *TAI = dyn_cast<TryApplyInst>(&I)) { |
| checkForViolationsInNoEscapeClosures(Accesses, TAI, ASA, |
| ConflictingAccesses); |
| continue; |
| } |
| #ifndef NDEBUG |
| // FIXME: Once AllocBoxToStack is fixed to correctly set noescape |
| // closure types, move this PartialApply verification into the |
| // SILVerifier to better pinpoint the offending pass. |
| if (auto *PAI = dyn_cast<PartialApplyInst>(&I)) { |
| ApplySite apply(PAI); |
| if (llvm::any_of(range(apply.getNumArguments()), |
| [apply](unsigned argIdx) { |
| return apply.getArgumentConvention(argIdx) |
| == SILArgumentConvention::Indirect_InoutAliasable; |
| })) { |
| checkNoEscapePartialApply(PAI); |
| } |
| } |
| #endif |
| // Sanity check to make sure entries are properly removed. |
| assert((!isa<ReturnInst>(&I) || Accesses.empty()) && |
| "Entries were not properly removed?!"); |
| } |
| } |
| |
| // Now that we've collected violations and suppressed calls, emit |
| // diagnostics. |
| for (auto &Violation : ConflictingAccesses) { |
| diagnoseExclusivityViolation(Violation, CallsToSwap, Fn.getASTContext()); |
| } |
| } |
| |
| namespace { |
| |
| class DiagnoseStaticExclusivity : public SILFunctionTransform { |
| public: |
| DiagnoseStaticExclusivity() {} |
| |
| private: |
| void run() override { |
| // Don't rerun diagnostics on deserialized functions. |
| if (getFunction()->wasDeserializedCanonical()) |
| return; |
| |
| SILFunction *Fn = getFunction(); |
| // This is a staging flag. Eventually the ability to turn off static |
| // enforcement will be removed. |
| if (!Fn->getModule().getOptions().EnforceExclusivityStatic) |
| return; |
| |
| PostOrderFunctionInfo *PO = getAnalysis<PostOrderAnalysis>()->get(Fn); |
| auto *ASA = getAnalysis<AccessSummaryAnalysis>(); |
| checkStaticExclusivity(*Fn, PO, ASA); |
| } |
| }; |
| |
| } // end anonymous namespace |
| |
| SILTransform *swift::createDiagnoseStaticExclusivity() { |
| return new DiagnoseStaticExclusivity(); |
| } |