blob: f9e68af362c479336bb80ca77688e14dd88842b6 [file] [log] [blame]
//===--- DiagnoseStaticExclusivity.cpp - Find violations of exclusivity ---===//
// This source file is part of the 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 for license information
// See 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.
/// 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.
/// 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 {
RecordedAccessKind RecordKind;
union {
BeginAccessInst *Inst;
struct {
SILAccessKind AccessKind;
SILLocation AccessLoc;
} Closure;
const IndexTrieNode *SubPath;
RecordedAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) :
RecordKind(RecordedAccessKind::BeginInstruction), Inst(BAI),
SubPath(SubPath) { }
RecordedAccess(SILAccessKind ClosureAccessKind,
SILLocation ClosureAccessLoc, const IndexTrieNode *SubPath) :
Closure({ClosureAccessKind, 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 Closure.AccessKind;
llvm_unreachable("unhandled kind");
SILLocation getAccessLoc() const {
switch (RecordKind) {
case RecordedAccessKind::BeginInstruction:
return Inst->getLoc();
case RecordedAccessKind::NoescapeClosureCapture:
return Closure.AccessLoc;
llvm_unreachable("unhandled kind");
const IndexTrieNode *getSubPath() const {
return SubPath;
/// Records the in-progress accesses to a given sub path.
class SubAccessInfo {
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;
/// 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)
/// Decrement the count for given access.
void endAccess(EndAccessInst *EAI) {
if (EAI->getBeginAccess()->getAccessKind() == SILAccessKind::Read)
// 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;
return SubAccesses.back();
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();
// Returns the previous access when beginning an access of the given Kind will
// result in a conflict with a previous access.
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);
/// 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 {
/// 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;
} // 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,
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())
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();
return false;
/// 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())
auto *CE = CallLoc.getAsASTNode<CallExpr>();
if (!CE)
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;
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 =
if (ProtocolForDecl) {
IsSubscriptOnMutableCollection = (ProtocolForDecl == MutableCollectionDecl);
} else {
for (ValueDecl *Req : Decl1->getSatisfiedProtocolRequirements()) {
DeclContext *ReqDC = Req->getDeclContext();
ProtocolDecl *ReqProto = ReqDC->getSelfProtocolDecl();
assert(ReqProto && "Protocol requirement not in a protocol?");
if (ReqProto == MutableCollectionDecl) {
IsSubscriptOnMutableCollection = true;
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,
TypeExpansionContext context) {
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();
LLVM_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 =
// 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 =
if (const ValueDecl *VD = Storage.getDecl()) {
// We have a declaration, so mention the identifier in the diagnostic.
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(),
PathDescription, AccessKindForMain, SuggestSwapAt);
if (SuggestSwapAt)
addSwapAtFixit(D, CallToReplace, Base, SwapIndex1, SwapIndex2,
} else {
diagnose(Ctx, MainAccess.getAccessLoc().getSourceLoc(),
diag::exclusivity_access_required_unknown_decl, AccessKindForMain)
diagnose(Ctx, NoteAccess.getAccessLoc().getSourceLoc(),
/// 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->getReferencedFunctionOrNull();
if (!SF)
return false;
if (!SF->hasLocation())
return false;
auto *FD = SF->getLocation().getAsASTNode<FuncDecl>();
if (!FD)
return false;
return FD == Ctx.getSwap();
static llvm::cl::opt<bool> ShouldAssertOnFailure(
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)
if (!BestArgAccess ||
BestArgAccess->getSubPath())) {
SILLocation AccessLoc = SubAccess.getAccessLoc();
BestArgAccess = RecordedAccess(Kind, AccessLoc, SubPath);
BestInProgressAccess = InProgressAccess;
if (!BestArgAccess)
return None;
return ConflictingAccess(AccessedStorage, *BestInProgressAccess,
// =============================================================================
// The data flow algorithm that drives diagnostics.
// Forward declare verification entry point.
static void checkAccessedAddress(Operand *memOper, StorageMap &Accesses);
namespace {
/// Track the current state of formal accesses, including exclusivity
/// violations, and function summaries at a particular point in the program.
struct AccessState {
AccessSummaryAnalysis *ASA;
// 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;
// Collects calls the Standard Library swap() for Fix-Its.
llvm::SmallVector<ApplyInst *, 8> CallsToSwap;
StorageMap *Accesses = nullptr;
AccessState(AccessSummaryAnalysis *ASA) : ASA(ASA) {}
} // namespace
// Find conflicting access on each argument using AccessSummaryAnalysis.
static void
checkAccessSummary(ApplySite Apply, AccessState &State,
const AccessSummaryAnalysis::FunctionSummary &FS) {
for (unsigned ArgumentIndex : range(Apply.getNumArguments())) {
unsigned CalleeIndex =
Apply.getCalleeArgIndexOfFirstAppliedArg() + ArgumentIndex;
const AccessSummaryAnalysis::ArgumentSummary &AS =
const auto &SubAccesses = AS.getSubAccesses();
// Is the capture accessed in the callee?
if (SubAccesses.empty())
SILValue Argument = Apply.getArgument(ArgumentIndex);
// A valid AccessedStorage should always be found because Unsafe accesses
// are not tracked by AccessSummaryAnalysis.
auto Storage = AccessedStorage::computeInScope(Argument);
assert(Storage && "captured address must have valid storage");
auto AccessIt = State.Accesses->find(Storage);
// Are there any accesses in progress at the time of the call?
if (AccessIt == State.Accesses->end())
const AccessInfo &Info = AccessIt->getSecond();
if (auto Conflict = findConflictingArgumentAccess(AS, Storage, Info))
/// For each argument in the range of the callee arguments being applied at the
/// given apply site, use the summary analysis to determine whether the
/// arguments will be accessed in a way that conflicts with any currently in
/// progress accesses. If so, diagnose.
static void checkCaptureAccess(ApplySite Apply, AccessState &State) {
// A callee may be nullptr or empty for various reasons, such as being
// dynamically replaceable.
SILFunction *Callee = Apply.getCalleeFunction();
if (Callee && !Callee->empty()) {
checkAccessSummary(Apply, State, State.ASA->getOrCreateSummary(Callee));
// In the absence of AccessSummaryAnalysis, conservatively assume by-address
// captures are fully accessed by the callee.
for (Operand &argOper : Apply.getArgumentOperands()) {
auto convention = Apply.getArgumentConvention(argOper);
if (convention != SILArgumentConvention::Indirect_InoutAliasable)
// A valid AccessedStorage should always be found because Unsafe accesses
// are not tracked by AccessSummaryAnalysis.
auto Storage = AccessedStorage::computeInScope(argOper.get());
assert(Storage && "captured address must have valid storage");
// Are there any accesses in progress at the time of the call?
auto AccessIt = State.Accesses->find(Storage);
if (AccessIt == State.Accesses->end())
// The unknown argument access is considered a modify of the root subpath.
auto argAccess = RecordedAccess(SILAccessKind::Modify, Apply.getLoc(),
// Construct a conflicting RecordedAccess if one doesn't already exist.
const AccessInfo &info = AccessIt->getSecond();
auto inProgressAccess =
shouldReportAccess(info, SILAccessKind::Modify, argAccess.getSubPath());
if (!inProgressAccess)
State.ConflictingAccesses.emplace_back(Storage, *inProgressAccess,
/// 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>();
/// Recursively check for conflicts with in-progress accesses at the given
/// apply.
/// Any captured variable accessed by a noescape closure is considered to be
/// accessed at the point that the closure is fully applied. This includes
/// variables captured by address by the noescape closure being applied or by
/// any other noescape closure that is itself passed as an argument to that
/// closure.
/// (1) Use AccessSummaryAnalysis to check each argument for statically
/// enforced accesses nested within the callee.
/// (2) If an applied argument is itself a function type, recursively check for
/// violations on the closure being passed as an argument.
/// (3) Walk up the chain of partial applies to recursively visit all arguments.
/// Note: This handles closures that are called immediately:
/// var i = 7
/// ({ (p: inout Int) in i = 8})(&i) // Overlapping access to 'i'
/// Note: This handles chains of partial applies:
/// pa1 = partial_apply f(c) : $(a, b, c)
/// pa2 = partial_apply pa1(b) : $(a, b)
/// apply pa2(a)
static void checkForViolationAtApply(ApplySite Apply, AccessState &State) {
// First, check access to variables immediately captured at this apply site.
checkCaptureAccess(Apply, State);
// Next, recursively check any noescape closures passed as arguments at this
// apply site.
TinyPtrVector<PartialApplyInst *> partialApplies;
for (SILValue Argument : Apply.getArguments()) {
auto FnType = getSILFunctionTypeForValue(Argument);
if (!FnType || !FnType->isNoEscape())
findClosuresForFunctionValue(Argument, partialApplies);
// Continue recursively walking up the chain of applies if necessary.
findClosuresForFunctionValue(Apply.getCallee(), partialApplies);
for (auto *PAI : partialApplies)
checkForViolationAtApply(ApplySite(PAI), State);
// Apply transfer function to the AccessState. Beginning an access
// increments the read or write count for the storage location;
// Ending one decrements the count.
static void checkForViolationsAtInstruction(SILInstruction &I,
AccessState &State) {
if (auto *BAI = dyn_cast<BeginAccessInst>(&I)) {
if (BAI->getEnforcement() == SILAccessEnforcement::Unsafe)
SILAccessKind Kind = BAI->getAccessKind();
const AccessedStorage &Storage = identifyFormalAccess(BAI);
assert(Storage && "unidentified formal access");
// Storage may be associated with a nested access where the outer access is
// "unsafe". That's ok because the outer access can itself be treated like a
// valid source, as long as we don't ask for its source.
AccessInfo &Info = (*State.Accesses)[Storage];
const IndexTrieNode *SubPath = State.ASA->findSubPathAccessed(BAI);
if (auto Conflict = shouldReportAccess(Info, Kind, SubPath)) {
State.ConflictingAccesses.emplace_back(Storage, *Conflict,
RecordedAccess(BAI, SubPath));
Info.beginAccess(BAI, SubPath);
if (auto *EAI = dyn_cast<EndAccessInst>(&I)) {
BeginAccessInst *BAI = EAI->getBeginAccess();
if (BAI->getEnforcement() == SILAccessEnforcement::Unsafe)
const AccessedStorage &Storage = identifyFormalAccess(BAI);
assert(Storage && "unidentified formal access");
auto It = State.Accesses->find(identifyFormalAccess(BAI));
AccessInfo &Info = It->getSecond();
const IndexTrieNode *SubPath = State.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())
if (I.getModule().getOptions().VerifyExclusivity && I.mayReadOrWriteMemory()) {
visitAccessedAddress(&I, [&State](Operand *memOper) {
checkAccessedAddress(memOper, *State.Accesses);
if (auto apply = FullApplySite::isa(&I)) {
if (auto *AI = dyn_cast<ApplyInst>(&I)) {
// Record calls to swap() for potential Fix-Its.
if (isCallToStandardLibrarySwap(AI, I.getFunction()->getASTContext())) {
checkForViolationAtApply(apply, State);
// Sanity check to make sure entries are properly removed.
assert((!isa<ReturnInst>(&I) || State.Accesses->empty())
&& "Entries were not properly removed?!");
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())
AccessState State(ASA);
// For each basic block, track the stack of current accesses on
// exit from that block.
llvm::SmallDenseMap<SILBasicBlock *, Optional<StorageMap>, 32>
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())
const Optional<StorageMap> &PredAccesses = it->getSecond();
if (PredAccesses) {
BBState = PredAccesses;
// The in-progress accesses for the current program point, represented
// as map from storage locations to the accesses in progress for the
// location.
State.Accesses = BBState.getPointer();
for (auto &I : *BB)
checkForViolationsAtInstruction(I, State);
// Now that we've collected violations and suppressed calls, emit
// diagnostics.
for (auto &Violation : State.ConflictingAccesses) {
diagnoseExclusivityViolation(Violation, State.CallsToSwap,
// =============================================================================
// Verification
// Check that the given address-type operand is guarded by begin/end access
// markers.
static void checkAccessedAddress(Operand *memOper, StorageMap &Accesses) {
SILValue accessBegin = getAccessScope(memOper->get());
SILInstruction *memInst = memOper->getUser();
auto error = [accessBegin, memInst]() {
llvm::dbgs() << "Memory access not protected by begin_access:\n";
llvm::dbgs() << "Accessing: " << accessBegin;
llvm::dbgs() << "In function:\n";
// Check if this address is guarded by an access.
if (auto *BAI = dyn_cast<BeginAccessInst>(accessBegin)) {
if (BAI->getEnforcement() == SILAccessEnforcement::Unsafe)
const AccessedStorage &Storage = identifyFormalAccess(BAI);
assert(Storage && "unidentified formal access");
AccessInfo &Info = Accesses[Storage];
if (Info.hasAccessesInProgress())
// --- This address is not guarded by a begin_access.
// If the memory instruction is only used for initialization, it doesn't need
// an access marker.
if (memInstMustInitialize(memOper))
if (auto apply = ApplySite::isa(memInst)) {
SILArgumentConvention conv = apply.getArgumentConvention(*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)
&& "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)
auto storage = AccessedStorage::compute(accessBegin);
// AccessedStorage::compute may return an invalid storage object if the
// address producer is not recognized by its allowlist. 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 AccessedStorage::compute.
// For the purpose of verification, an unidentified access is
// unenforced. These occur in cases like global addressors and local buffers
// that make use of RawPointers.
if (!storage || storage.getKind() == AccessedStorage::Unidentified)
// Some identifiable addresses can also be recognized as local initialization
// or other patterns that don't qualify as formal access.
if (!isPossibleFormalAccessBase(storage, memInst->getFunction()))
// 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)) {
// =============================================================================
// Function Pass Driver
namespace {
class DiagnoseStaticExclusivity : public SILFunctionTransform {
DiagnoseStaticExclusivity() {}
void run() override {
// Don't rerun diagnostics on deserialized functions.
if (getFunction()->wasDeserializedCanonical())
SILFunction *Fn = getFunction();
// This is a staging flag. Eventually the ability to turn off static
// enforcement will be removed.
if (!Fn->getModule().getOptions().EnforceExclusivityStatic)
PostOrderFunctionInfo *PO = getAnalysis<PostOrderAnalysis>()->get(Fn);
auto *ASA = getAnalysis<AccessSummaryAnalysis>();
checkStaticExclusivity(*Fn, PO, ASA);
} // end anonymous namespace
SILTransform *swift::createDiagnoseStaticExclusivity() {
return new DiagnoseStaticExclusivity();