Merge pull request #18560 from shajrawi/merge_accesses
[AccessEnforcementOpts] Add mergeAccesses analysis + optimization
diff --git a/lib/SILOptimizer/LoopTransforms/LICM.cpp b/lib/SILOptimizer/LoopTransforms/LICM.cpp
index 4e4d8a8..78c2a9d 100644
--- a/lib/SILOptimizer/LoopTransforms/LICM.cpp
+++ b/lib/SILOptimizer/LoopTransforms/LICM.cpp
@@ -18,6 +18,7 @@
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILInstruction.h"
+#include "swift/SILOptimizer/Analysis/AccessedStorageAnalysis.h"
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
#include "swift/SILOptimizer/Analysis/Analysis.h"
#include "swift/SILOptimizer/Analysis/ArraySemantic.h"
@@ -361,6 +362,7 @@
AliasAnalysis *AA;
SideEffectAnalysis *SEA;
DominanceInfo *DomTree;
+ AccessedStorageAnalysis *ASA;
bool Changed;
/// True if LICM is done on high-level SIL, i.e. semantic calls are not
@@ -380,8 +382,9 @@
public:
LoopTreeOptimization(SILLoop *TopLevelLoop, SILLoopInfo *LI,
AliasAnalysis *AA, SideEffectAnalysis *SEA,
- DominanceInfo *DT, bool RunsOnHighLevelSil)
- : LoopInfo(LI), AA(AA), SEA(SEA), DomTree(DT), Changed(false),
+ DominanceInfo *DT, AccessedStorageAnalysis *ASA,
+ bool RunsOnHighLevelSil)
+ : LoopInfo(LI), AA(AA), SEA(SEA), DomTree(DT), ASA(ASA), Changed(false),
RunsOnHighLevelSIL(RunsOnHighLevelSil) {
// Collect loops for a recursive bottom-up traversal in the loop tree.
BotUpWorkList.push_back(TopLevelLoop);
@@ -528,9 +531,10 @@
return true;
}
-static bool
-analyzeBeginAccess(BeginAccessInst *BI,
- SmallVector<BeginAccessInst *, 8> &BeginAccesses) {
+static bool analyzeBeginAccess(BeginAccessInst *BI,
+ SmallVector<BeginAccessInst *, 8> &BeginAccesses,
+ SmallVector<FullApplySite, 8> &fullApplies,
+ AccessedStorageAnalysis *ASA) {
if (BI->getEnforcement() != SILAccessEnforcement::Dynamic) {
return false;
}
@@ -550,8 +554,18 @@
findAccessedStorageNonNested(OtherBI));
};
- return (
- std::all_of(BeginAccesses.begin(), BeginAccesses.end(), safeBeginPred));
+ if (!std::all_of(BeginAccesses.begin(), BeginAccesses.end(), safeBeginPred))
+ return false;
+
+ for (auto fullApply : fullApplies) {
+ FunctionAccessedStorage callSiteAccesses;
+ ASA->getCallSiteEffects(callSiteAccesses, fullApply);
+ SILAccessKind accessKind = BI->getAccessKind();
+ if (callSiteAccesses.mayConflictWith(accessKind, storage))
+ return false;
+ }
+
+ return true;
}
// Analyzes current loop for hosting/sinking potential:
@@ -575,6 +589,8 @@
SmallVector<FixLifetimeInst *, 8> FixLifetimes;
// Contains begin_access, we might be able to hoist them.
SmallVector<BeginAccessInst *, 8> BeginAccesses;
+ // Contains all applies - used for begin_access
+ SmallVector<FullApplySite, 8> fullApplies;
for (auto *BB : Loop->getBlocks()) {
for (auto &Inst : *BB) {
@@ -618,6 +634,9 @@
LLVM_FALLTHROUGH;
}
default: {
+ if (auto fullApply = FullApplySite::isa(&Inst)) {
+ fullApplies.push_back(fullApply);
+ }
checkSideEffects(Inst, MayWrites);
if (canHoistUpDefault(&Inst, Loop, DomTree, RunsOnHighLevelSIL)) {
HoistUp.insert(&Inst);
@@ -660,7 +679,7 @@
LLVM_DEBUG(llvm::dbgs() << "Some end accesses can't be handled\n");
continue;
}
- if (analyzeBeginAccess(BI, BeginAccesses)) {
+ if (analyzeBeginAccess(BI, BeginAccesses, fullApplies, ASA)) {
SpecialHoist.insert(BI);
}
}
@@ -711,6 +730,7 @@
DominanceAnalysis *DA = PM->getAnalysis<DominanceAnalysis>();
AliasAnalysis *AA = PM->getAnalysis<AliasAnalysis>();
SideEffectAnalysis *SEA = PM->getAnalysis<SideEffectAnalysis>();
+ AccessedStorageAnalysis *ASA = getAnalysis<AccessedStorageAnalysis>();
DominanceInfo *DomTree = nullptr;
LLVM_DEBUG(llvm::dbgs() << "Processing loops in " << F->getName() << "\n");
@@ -718,7 +738,7 @@
for (auto *TopLevelLoop : *LoopInfo) {
if (!DomTree) DomTree = DA->get(F);
- LoopTreeOptimization Opt(TopLevelLoop, LoopInfo, AA, SEA, DomTree,
+ LoopTreeOptimization Opt(TopLevelLoop, LoopInfo, AA, SEA, DomTree, ASA,
RunsOnHighLevelSil);
Changed |= Opt.optimize();
}
diff --git a/lib/SILOptimizer/PassManager/PassPipeline.cpp b/lib/SILOptimizer/PassManager/PassPipeline.cpp
index 86a9c0a..2b9e63c 100644
--- a/lib/SILOptimizer/PassManager/PassPipeline.cpp
+++ b/lib/SILOptimizer/PassManager/PassPipeline.cpp
@@ -199,6 +199,10 @@
P.addHighLevelLICM();
// Simplify CFG after LICM that creates new exit blocks
P.addSimplifyCFG();
+ // LICM might have added new merging potential by hoisting
+ // we don't want to restart the pipeline - ignore the
+ // potential of merging out of two loops
+ P.addAccessEnforcementOpts();
// Start of loop unrolling passes.
P.addArrayCountPropagation();
// To simplify induction variable.
@@ -457,6 +461,10 @@
P.addLICM();
// Simplify CFG after LICM that creates new exit blocks
P.addSimplifyCFG();
+ // LICM might have added new merging potential by hoisting
+ // we don't want to restart the pipeline - ignore the
+ // potential of merging out of two loops
+ P.addAccessEnforcementOpts();
// Optimize overflow checks.
P.addRedundantOverflowCheckRemoval();
diff --git a/lib/SILOptimizer/Transforms/AccessEnforcementOpts.cpp b/lib/SILOptimizer/Transforms/AccessEnforcementOpts.cpp
index 6aa06df..05394e4 100644
--- a/lib/SILOptimizer/Transforms/AccessEnforcementOpts.cpp
+++ b/lib/SILOptimizer/Transforms/AccessEnforcementOpts.cpp
@@ -65,6 +65,14 @@
/// any point in the pipeline. Until then, we could settle for a partially
/// working AccessEnforcementSelection, or expand it somewhat to handle
/// alloc_stack.
+///
+/// **Access marker merger**
+///
+/// When a pair of non-overlapping accesses, where the first access dominates
+/// the second and there are no conflicts on the same storage in the paths
+/// between them, and they are part of the same sub-region
+/// be it the same block or the sampe loop, merge those accesses to create
+/// a new, larger, scope with a single begin_access for the accesses.
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "access-enforcement-opts"
@@ -73,9 +81,12 @@
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SILOptimizer/Analysis/AccessedStorageAnalysis.h"
+#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
+#include "swift/SILOptimizer/Analysis/LoopRegionAnalysis.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/Local.h"
-#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SCCIterator.h"
using namespace swift;
@@ -127,16 +138,49 @@
} // namespace swift
namespace {
-// Sparse access sets are used temporarily for fast operations by local
-// reachability analysis. We don't care if they take more space.
-class SparseAccessSet;
+/// A dense map of (index, begin_access instructions) as a compact vector.
+/// Reachability results are stored here because very few accesses are
+/// typically in-progress at a particular program point,
+/// particularly at block boundaries.
+using DenseAccessMap = llvm::SmallMapVector<unsigned, BeginAccessInst *, 4>;
-/// A dense set of begin_access instructions as a compact vector. Reachability
-/// results are stored here because very few accesses are typically in-progress
-/// at a particular program point, particularly at block boundaries.
-using DenseAccessSet = SmallVector<BeginAccessInst *, 4>;
+// Tracks the local data flow result for a basic block
+struct RegionInfo {
+ struct AccessSummary {
+ // The actual begin_access instructions
+ DenseAccessMap conflictFreeAccesses;
+ // Flag to Indicate if we started a merging process
+ bool merged;
+ AccessSummary(unsigned size) : merged(false) {}
+ };
-/// Analyze a function's formal access to determine nested conflicts.
+ AccessSummary inScopeConflictFreeAccesses;
+ AccessSummary outOfScopeConflictFreeAccesses;
+ bool unidentifiedAccess;
+
+public:
+ RegionInfo(unsigned size)
+ : inScopeConflictFreeAccesses(size), outOfScopeConflictFreeAccesses(size),
+ unidentifiedAccess(false) {}
+
+ void reset() {
+ inScopeConflictFreeAccesses.conflictFreeAccesses.clear();
+ outOfScopeConflictFreeAccesses.conflictFreeAccesses.clear();
+ outOfScopeConflictFreeAccesses.merged = true;
+ unidentifiedAccess = false;
+ }
+
+ const DenseAccessMap &getInScopeAccesses() {
+ return inScopeConflictFreeAccesses.conflictFreeAccesses;
+ }
+
+ const DenseAccessMap &getOutOfScopeAccesses() {
+ return outOfScopeConflictFreeAccesses.conflictFreeAccesses;
+ }
+};
+
+/// Analyze a function's formal accesses.
+/// determines nested conflicts and mergeable accesses.
///
/// Maps each begin access instruction to its AccessInfo, which:
/// - identifies the accessed memory for conflict detection
@@ -150,21 +194,47 @@
/// or at the end_access instruction that is associated with the
/// begin_access.
///
-/// Forward data flow computes `blockOutAccess` for each block. At a control
-/// flow merge, this analysis forms an intersection of reachable accesses on
-/// each path. Only visited predecessors are merged (unvisited paths
-/// optimistically assume reachability). Before a block is visited, it has no
-/// map entry in blockOutAccess. Blocks are processed in RPO order, and a single
-/// begin_access dominates all associated end_access instructions. Consequently,
-/// when a block is first visited, blockOutAccess contains the maximal
+/// Forward data flow computes `BlockRegionInfo` for each region's blocks.
+/// Loops are processed bottom-up.
+/// Control flow within a loop or function top level is processed in RPO order.
+/// At a block's control flow merge, this analysis forms an intersection of
+/// reachable accesses on each path inside the region.
+/// Before a block is visited, it has no `BlockRegionInfo` entry.
+/// Blocks are processed in RPO order, and a single begin_access dominates
+/// all associated end_access instructions. Consequently,
+/// when a block is first visited, its storage accesses contains the maximal
/// reachability set. Further iteration would only reduce this set.
///
-/// The only result of this analysis is the seenNestedConflict flags in
-/// AccessInfo. Since reducing a reachability set cannot further detect
-/// conflicts, there is no need to iterate to a reachability fix point.
-class AccessConflictAnalysis {
+/// The only results of this analysis are:
+//// 1) The seenNestedConflict flags in AccessInfo. For Each begin_access
+/// Since reducing a reachability set cannot further detect
+/// conflicts, there is no need to iterate to a reachability fix point.
+/// This is derived from a block's in-scope accesses
+/// 2) A deterministic order map of out-of-scope instructions that we can
+/// merge. The way we construct this map guarantees the accesses within
+/// it are mergeable.
+///
+// Example:
+// %1 = begin_access X
+// %1 is in-scope
+// ...
+// %2 = begin_access Y // conflict with %1 if X (may-)aliases Y
+// If it conflicts - seenNestedConflict
+// ...
+// end_access %1
+// %1 is out-of-scope
+// ...
+// %3 = begin_access X // %1 reaches %3 -> we can merge
+class AccessConflictAndMergeAnalysis {
public:
using AccessMap = llvm::SmallDenseMap<BeginAccessInst *, AccessInfo, 32>;
+ using AccessedStorageSet = llvm::SmallDenseSet<AccessedStorage, 8>;
+ using LoopRegionToAccessedStorage =
+ llvm::SmallDenseMap<unsigned, AccessedStorageSet>;
+ using RegionIDToLocalInfoMap = llvm::DenseMap<unsigned, RegionInfo>;
+ // Instruction pairs we can merge from dominating instruction to dominated
+ using MergeablePairs =
+ llvm::SmallVector<std::pair<BeginAccessInst *, BeginAccessInst *>, 64>;
// This result of this analysis is a map from all BeginAccessInst in this
// function to AccessInfo.
struct Result {
@@ -173,6 +243,9 @@
/// the accesses, then AccessInfo::getAccessIndex() can be used.
AccessMap accessMap;
+ /// Instruction pairs we can merge the scope of
+ MergeablePairs mergePairs;
+
/// Convenience.
///
/// Note: If AccessInfo has already been retrieved, get the index directly
@@ -194,183 +267,274 @@
};
private:
- SILFunction *F;
- PostOrderFunctionInfo *PO;
+ LoopRegionFunctionInfo *LRFI;
AccessedStorageAnalysis *ASA;
- /// Tracks the in-scope accesses at the end of each block, for the purpose of
- /// finding nested conflicts. (Out-of-scope accesses are currently only
- /// tracked locally for the purpose of merging access scopes.)
- llvm::SmallDenseMap<SILBasicBlock *, DenseAccessSet, 32> blockOutAccess;
-
Result result;
public:
- AccessConflictAnalysis(SILFunction *F, PostOrderFunctionInfo *PO,
- AccessedStorageAnalysis *ASA)
- : F(F), PO(PO), ASA(ASA) {}
+ AccessConflictAndMergeAnalysis(LoopRegionFunctionInfo *LRFI,
+ AccessedStorageAnalysis *ASA)
+ : LRFI(LRFI), ASA(ASA) {}
- Result &&analyze() &&;
+ void analyze();
+
+ const Result &getResult() { return result; }
protected:
void identifyBeginAccesses();
- void visitBeginAccess(BeginAccessInst *beginAccess,
- SparseAccessSet &accessMap);
+ void
+ propagateAccessSetsBottomUp(LoopRegionToAccessedStorage ®ionToStorageMap,
+ llvm::SmallVector<unsigned, 16> worklist);
- void visitEndAccess(EndAccessInst *endAccess, SparseAccessSet &accessMap);
+ void calcBottomUpOrder(llvm::SmallVectorImpl<unsigned> &worklist);
- void visitFullApply(FullApplySite fullApply, SparseAccessSet &accessMap);
+ void visitBeginAccess(BeginAccessInst *beginAccess, RegionInfo &info);
- void mergePredAccesses(SILBasicBlock *succBB,
- SparseAccessSet &mergedAccesses);
+ void visitEndAccess(EndAccessInst *endAccess, RegionInfo &info);
- void visitBlock(SILBasicBlock *BB);
-};
+ void visitFullApply(FullApplySite fullApply, RegionInfo &info);
-/// A sparse set of in-flight accesses.
-///
-/// Explodes a DenseAccessSet into a temporary sparse set for comparison
-/// and membership.
-///
-/// The AccessConflictAnalysis result provides the instruction to index
-/// mapping.
-class SparseAccessSet {
- AccessConflictAnalysis::Result &result;
+ void mergePredAccesses(LoopRegion *region,
+ RegionIDToLocalInfoMap &localRegionInfos);
- // Mark the in-scope accesses.
- // (Most functions have < 64 accesses.)
- llvm::SmallBitVector inScopeBitmask;
- // Mark a potential conflicts on each access since the last begin/end marker.
- llvm::SmallBitVector conflictBitmask;
- DenseAccessSet denseVec; // Hold all local accesses seen thus far.
+ void detectConflictsInLoop(LoopRegion *loopRegion,
+ RegionIDToLocalInfoMap &localRegionInfos,
+ LoopRegionToAccessedStorage &accessSetsOfRegions);
-public:
- /// Iterate over in-scope, conflict free access.
- class NoNestedConflictIterator {
- const SparseAccessSet &sparseSet;
- DenseAccessSet::const_iterator denseIter;
+ void localDataFlowInBlock(LoopRegion *bbRegion,
+ RegionIDToLocalInfoMap &localRegionInfos);
- public:
- NoNestedConflictIterator(const SparseAccessSet &set)
- : sparseSet(set), denseIter(set.denseVec.begin()) {}
-
- BeginAccessInst *next() {
- auto end = sparseSet.denseVec.end();
- while (denseIter != end) {
- BeginAccessInst *beginAccess = *denseIter;
- ++denseIter;
- unsigned sparseIndex = sparseSet.result.getAccessIndex(beginAccess);
- if (sparseSet.inScopeBitmask[sparseIndex]
- && !sparseSet.conflictBitmask[sparseIndex]) {
- return beginAccess;
- }
- }
- return nullptr;
- }
- };
-
- SparseAccessSet(AccessConflictAnalysis::Result &result)
- : result(result), inScopeBitmask(result.accessMap.size()),
- conflictBitmask(result.accessMap.size()) {}
-
- // All accessed in the given denseVec are presumed to be in-scope and conflict
- // free.
- SparseAccessSet(const DenseAccessSet &denseVec,
- AccessConflictAnalysis::Result &result)
- : result(result), inScopeBitmask(result.accessMap.size()),
- conflictBitmask(result.accessMap.size()), denseVec(denseVec) {
- for (BeginAccessInst *beginAccess : denseVec)
- inScopeBitmask.set(result.getAccessIndex(beginAccess));
- }
- bool hasConflictFreeAccess() const {
- NoNestedConflictIterator iterator(*this);
- return iterator.next() != nullptr;
- }
-
- bool hasInScopeAccess() const {
- return llvm::any_of(denseVec, [this](BeginAccessInst *beginAccess) {
- unsigned sparseIndex = result.getAccessIndex(beginAccess);
- return inScopeBitmask[sparseIndex];
- });
- }
-
- bool isInScope(unsigned index) const { return inScopeBitmask[index]; }
-
- // Insert the given BeginAccessInst with its corresponding reachability index.
- // Set the in-scope bit and reset the conflict bit.
- bool enterScope(BeginAccessInst *beginAccess, unsigned index) {
- assert(!inScopeBitmask[index]
- && "nested access should not be dynamically enforced.");
- inScopeBitmask.set(index);
- conflictBitmask.reset(index);
- denseVec.push_back(beginAccess);
- return true;
- }
-
- /// End the scope of the given access by marking it in-scope and clearing the
- /// conflict bit. (The conflict bit only marks conflicts since the last begin
- /// *or* end access).
- void exitScope(unsigned index) { inScopeBitmask.reset(index); }
-
- bool seenConflict(unsigned index) const { return conflictBitmask[index]; }
-
- void setConflict(unsigned index) { conflictBitmask.set(index); }
-
- // Only merge accesses that are present on the `other` map. i.e. erase
- // all accesses in this map that are not present in `other`.
- void merge(const SparseAccessSet &other) {
- inScopeBitmask &= other.inScopeBitmask;
- // Currently only conflict free accesses are preserved across blocks by this
- // analysis. Otherwise, taking the union of conflict bits would be valid.
- assert(other.conflictBitmask.none());
- }
-
- void copyNoNestedConflictInto(DenseAccessSet &other) {
- other.clear();
- NoNestedConflictIterator iterator(*this);
- while (BeginAccessInst *beginAccess = iterator.next())
- other.push_back(beginAccess);
- }
-
- // Dump only the accesses with no conflict up to this point.
- void dump() const {
- for (BeginAccessInst *beginAccess : denseVec) {
- unsigned sparseIndex = result.getAccessIndex(beginAccess);
- if (conflictBitmask[sparseIndex])
- continue;
-
- llvm::dbgs() << *beginAccess << " ";
- if (!inScopeBitmask[sparseIndex])
- llvm::dbgs() << " [noscope]";
- result.getAccessInfo(beginAccess).dump();
- }
- }
+private:
+ void addInScopeAccess(RegionInfo &info, BeginAccessInst *beginAccess);
+ void removeInScopeAccess(RegionInfo &info, BeginAccessInst *beginAccess);
+ void recordConflict(RegionInfo &info, const AccessedStorage &storage);
+ void addOutOfScopeAccess(RegionInfo &info, BeginAccessInst *beginAccess);
+ void mergeAccessStruct(RegionInfo &info,
+ RegionInfo::AccessSummary &accessStruct,
+ const RegionInfo::AccessSummary &RHSAccessStruct);
+ void merge(RegionInfo &info, const RegionInfo &RHS);
+ void removeConflictFromStruct(RegionInfo &info,
+ RegionInfo::AccessSummary &accessStruct,
+ const AccessedStorage &storage);
+ void visitSetForConflicts(
+ const DenseAccessMap &accessSet, RegionInfo &info,
+ AccessConflictAndMergeAnalysis::AccessedStorageSet &loopStorage);
+ void
+ detectApplyConflicts(const swift::FunctionAccessedStorage &callSiteAccesses,
+ const DenseAccessMap &conflictFreeSet,
+ const swift::FullApplySite &fullApply, RegionInfo &info);
};
} // namespace
-// Top-level driver for AccessConflictAnalysis.
-AccessConflictAnalysis::Result &&AccessConflictAnalysis::analyze() && {
- // Populate beginAccessMap.
+void AccessConflictAndMergeAnalysis::addInScopeAccess(
+ RegionInfo &info, BeginAccessInst *beginAccess) {
+ auto &ai = result.getAccessInfo(beginAccess);
+ auto index = ai.getAccessIndex();
+ assert(info.getInScopeAccesses().find(index) ==
+ info.inScopeConflictFreeAccesses.conflictFreeAccesses.end() &&
+ "the begin_access should not have been in Set.");
+ info.inScopeConflictFreeAccesses.conflictFreeAccesses.insert(
+ std::make_pair(index, beginAccess));
+}
+
+void AccessConflictAndMergeAnalysis::removeInScopeAccess(
+ RegionInfo &info, BeginAccessInst *beginAccess) {
+ auto &ai = result.getAccessInfo(beginAccess);
+ auto index = ai.getAccessIndex();
+ auto it = info.inScopeConflictFreeAccesses.conflictFreeAccesses.find(index);
+ assert(it != info.inScopeConflictFreeAccesses.conflictFreeAccesses.end() &&
+ "the begin_access should have been in Set.");
+ info.inScopeConflictFreeAccesses.conflictFreeAccesses.erase(it);
+}
+
+void AccessConflictAndMergeAnalysis::removeConflictFromStruct(
+ RegionInfo &info, RegionInfo::AccessSummary &accessStruct,
+ const AccessedStorage &storage) {
+ auto pred = [&](const std::pair<unsigned, BeginAccessInst *> &pair) {
+ auto &currStorage = result.getAccessInfo(pair.second);
+ return !currStorage.isDistinctFrom(storage);
+ };
+ auto it = std::find_if(accessStruct.conflictFreeAccesses.begin(),
+ accessStruct.conflictFreeAccesses.end(), pred);
+ while (it != accessStruct.conflictFreeAccesses.end()) {
+ accessStruct.conflictFreeAccesses.erase(it);
+ it = std::find_if(accessStruct.conflictFreeAccesses.begin(),
+ accessStruct.conflictFreeAccesses.end(), pred);
+ }
+}
+
+void AccessConflictAndMergeAnalysis::recordConflict(
+ RegionInfo &info, const AccessedStorage &storage) {
+ removeConflictFromStruct(info, info.outOfScopeConflictFreeAccesses, storage);
+ DenseAccessMap tmpSet(info.inScopeConflictFreeAccesses.conflictFreeAccesses);
+ removeConflictFromStruct(info, info.inScopeConflictFreeAccesses, storage);
+ for (auto it : tmpSet) {
+ if (std::find(info.inScopeConflictFreeAccesses.conflictFreeAccesses.begin(),
+ info.inScopeConflictFreeAccesses.conflictFreeAccesses.end(),
+ it) ==
+ info.inScopeConflictFreeAccesses.conflictFreeAccesses.end()) {
+ auto &ai = result.getAccessInfo(it.second);
+ ai.setSeenNestedConflict();
+ }
+ }
+}
+
+void AccessConflictAndMergeAnalysis::addOutOfScopeAccess(
+ RegionInfo &info, BeginAccessInst *beginAccess) {
+ auto newStorageInfo = result.getAccessInfo(beginAccess);
+ auto newIndex = newStorageInfo.getAccessIndex();
+ auto pred = [&](const std::pair<unsigned, BeginAccessInst *> &pair) {
+ auto currStorageInfo = result.getAccessInfo(pair.second);
+ return currStorageInfo.hasIdenticalBase(newStorageInfo);
+ };
+
+ auto it = std::find_if(
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.rbegin(),
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.rend(), pred);
+
+ if (it == info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.rend()) {
+ // We don't have a match in outOfScopeConflictFreeAccesses
+ // Just add it and return
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.insert(
+ std::make_pair(newIndex, beginAccess));
+ return;
+ }
+
+ auto *otherBegin = it->second;
+ auto index = it->first;
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.erase(index);
+
+ auto predDistinct = [&](const std::pair<unsigned, BeginAccessInst *> &pair) {
+ auto currStorageInfo = result.getAccessInfo(pair.second);
+ return !currStorageInfo.isDistinctFrom(newStorageInfo);
+ };
+
+ auto itDistinct = std::find_if(
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.begin(),
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.end(),
+ predDistinct);
+
+ if (itDistinct ==
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.end()) {
+ LLVM_DEBUG(llvm::dbgs() << "Found mergable pair: " << *otherBegin << ", "
+ << *beginAccess << "\n");
+ result.mergePairs.push_back(std::make_pair(otherBegin, beginAccess));
+ } else {
+ while (itDistinct !=
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.end()) {
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.erase(
+ itDistinct);
+ itDistinct = std::find_if(
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.begin(),
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.end(),
+ predDistinct);
+ }
+ }
+
+ info.outOfScopeConflictFreeAccesses.conflictFreeAccesses.insert(
+ std::make_pair(newIndex, beginAccess));
+}
+
+static void copyMap(DenseAccessMap &to, const DenseAccessMap &from) {
+ for (auto it : from) {
+ to.insert(it);
+ }
+}
+
+void AccessConflictAndMergeAnalysis::mergeAccessStruct(
+ RegionInfo &info, RegionInfo::AccessSummary &accessStruct,
+ const RegionInfo::AccessSummary &RHSAccessStruct) {
+ if (!accessStruct.merged) {
+ copyMap(accessStruct.conflictFreeAccesses,
+ RHSAccessStruct.conflictFreeAccesses);
+ accessStruct.merged = true;
+ return;
+ }
+
+ DenseAccessMap tmpMap;
+ copyMap(tmpMap, accessStruct.conflictFreeAccesses);
+
+ for (auto pair : tmpMap) {
+ auto index = pair.first;
+ if (RHSAccessStruct.conflictFreeAccesses.find(index) !=
+ RHSAccessStruct.conflictFreeAccesses.end())
+ continue;
+ // Not in RHS - remove from intersect
+ accessStruct.conflictFreeAccesses.erase(index);
+ }
+}
+
+void AccessConflictAndMergeAnalysis::merge(RegionInfo &info,
+ const RegionInfo &RHS) {
+ info.unidentifiedAccess |= RHS.unidentifiedAccess;
+ mergeAccessStruct(info, info.inScopeConflictFreeAccesses,
+ RHS.inScopeConflictFreeAccesses);
+ mergeAccessStruct(info, info.outOfScopeConflictFreeAccesses,
+ RHS.outOfScopeConflictFreeAccesses);
+}
+
+// Top-level driver for AccessConflictAndMergeAnalysis
+void AccessConflictAndMergeAnalysis::analyze() {
identifyBeginAccesses();
+ LoopRegionToAccessedStorage accessSetsOfRegions;
+ llvm::SmallVector<unsigned, 16> worklist;
+ calcBottomUpOrder(worklist);
+ propagateAccessSetsBottomUp(accessSetsOfRegions, worklist);
- // Perform data flow and set the conflict flags on AccessInfo.
- for (auto *BB : PO->getReversePostOrder())
- visitBlock(BB);
-
- return std::move(result);
+ LLVM_DEBUG(llvm::dbgs() << "Processing Function: "
+ << LRFI->getFunction()->getName() << "\n");
+ while (!worklist.empty()) {
+ auto regionID = worklist.pop_back_val();
+ LLVM_DEBUG(llvm::dbgs() << "Processing Sub-Region: " << regionID << "\n");
+ auto *region = LRFI->getRegion(regionID);
+ RegionIDToLocalInfoMap localRegionInfos;
+ // This is RPO order of the sub-regions
+ for (auto subID : region->getSubregions()) {
+ auto *subRegion = LRFI->getRegion(subID);
+ // testIrreducibleGraph2 in test/SILOptimizer/access_enforcement_opts:
+ // If the sub-region is the source of a previously visited backedge,
+ // Then the in-state is an empty set.
+ bool disableCrossBlock = false;
+ if (localRegionInfos.find(subID) != localRegionInfos.end()) {
+ // Irreducible loop - we already set the predecessor to empty set
+ disableCrossBlock = true;
+ } else {
+ localRegionInfos.insert(
+ std::make_pair(subID, RegionInfo(result.accessMap.size())));
+ mergePredAccesses(subRegion, localRegionInfos);
+ }
+ if (subRegion->isBlock()) {
+ localDataFlowInBlock(subRegion, localRegionInfos);
+ } else {
+ assert(subRegion->isLoop() && "Expected a loop sub-region");
+ detectConflictsInLoop(subRegion, localRegionInfos, accessSetsOfRegions);
+ }
+ // After doing the control flow on the region, and as mentioned above,
+ // the sub-region is the source of a previously visited backedge,
+ // we want to remove the merging candidates from its final state
+ if (disableCrossBlock) {
+ // Clear-out the out state: this is risky irreducible control flow
+ // Only in-block conflict and merging is allowed
+ localRegionInfos.find(subID)->getSecond().reset();
+ }
+ }
+ }
}
// Find all begin access operations in this function. Map each access to
// AccessInfo, which includes its identified memory location, identifying
// index, and analysis result flags.
//
+// Also, add the storage location to the function's RegionStorage
+//
// TODO: begin_unpaired_access is not tracked. Even though begin_unpaired_access
// isn't explicitly paired, it may be possible after devirtualization and
// inlining to find all uses of the scratch buffer. However, this doesn't
// currently happen in practice (rdar://40033735).
-void AccessConflictAnalysis::identifyBeginAccesses() {
- for (auto &BB : *F) {
+void AccessConflictAndMergeAnalysis::identifyBeginAccesses() {
+ for (auto &BB : *LRFI->getFunction()) {
for (auto &I : BB) {
auto *beginAccess = dyn_cast<BeginAccessInst>(&I);
if (!beginAccess)
@@ -401,146 +565,244 @@
}
}
-/// When a conflict is detected, flag the access so it can't be folded, and
-/// remove its index from the current access set so we stop checking for
-/// conflicts. Erasing from SparseAccessSet does not invalidate any iterators.
-static void recordConflict(AccessInfo &info, SparseAccessSet &accessSet) {
- info.setSeenNestedConflict();
- accessSet.setConflict(info.getAccessIndex());
-}
-
-// Given an "inner" access, check for potential conflicts with any outer access.
-// Allow these overlapping accesses:
-// - read/read
-// - different bases, both valid, and at least one is local
-//
-// Remove any outer access that may conflict from the accessSet.
-// and flag the conflict in beginAccessMap.
-//
-// Record the inner access in the accessSet.
-//
-void AccessConflictAnalysis::visitBeginAccess(BeginAccessInst *innerBeginAccess,
- SparseAccessSet &accessSet) {
- if (innerBeginAccess->getEnforcement() != SILAccessEnforcement::Dynamic)
- return;
-
- const AccessInfo &innerAccess = result.getAccessInfo(innerBeginAccess);
- SILAccessKind innerAccessKind = innerBeginAccess->getAccessKind();
-
- SparseAccessSet::NoNestedConflictIterator accessIter(accessSet);
- while (BeginAccessInst *outerBeginAccess = accessIter.next()) {
- // If both are reads, keep the mapped access.
- if (!accessKindMayConflict(innerAccessKind,
- outerBeginAccess->getAccessKind())) {
- continue;
+// Returns a mapping from each loop sub-region to all its access storage
+// Propagates access summaries bottom-up from nested regions
+void AccessConflictAndMergeAnalysis::propagateAccessSetsBottomUp(
+ LoopRegionToAccessedStorage ®ionToStorageMap,
+ llvm::SmallVector<unsigned, 16> worklist) {
+ while (!worklist.empty()) {
+ auto regionID = worklist.pop_back_val();
+ auto *region = LRFI->getRegion(regionID);
+ assert(regionToStorageMap.find(regionID) == regionToStorageMap.end() &&
+ "Should not process a region twice");
+ AccessedStorageSet &accessedStorageSet = regionToStorageMap[regionID];
+ for (auto subID : region->getSubregions()) {
+ auto *subRegion = LRFI->getRegion(subID);
+ if (subRegion->isLoop()) {
+ // propagate access summaries bottom-up from nested loops.
+ auto subRegionStorageIt = regionToStorageMap.find(subID);
+ assert(subRegionStorageIt != regionToStorageMap.end() &&
+ "Should have processed sub-region");
+ for (auto storage : subRegionStorageIt->getSecond()) {
+ accessedStorageSet.insert(storage);
+ }
+ } else {
+ assert(subRegion->isBlock() && "Expected a block region");
+ auto *bb = subRegion->getBlock();
+ for (auto &instr : *bb) {
+ if (auto *beginAccess = dyn_cast<BeginAccessInst>(&instr)) {
+ const AccessedStorage &storage =
+ findAccessedStorageNonNested(beginAccess->getSource());
+ accessedStorageSet.insert(storage);
+ }
+ if (auto *beginAccess = dyn_cast<BeginUnpairedAccessInst>(&instr)) {
+ const AccessedStorage &storage =
+ findAccessedStorageNonNested(beginAccess->getSource());
+ accessedStorageSet.insert(storage);
+ }
+ }
+ }
}
- AccessInfo &outerAccess = result.getAccessInfo(outerBeginAccess);
-
- // If there is no potential conflict, leave the outer access mapped.
- if (!outerAccess.isDistinctFrom(innerAccess))
- continue;
-
- LLVM_DEBUG(innerAccess.dump(); llvm::dbgs() << " may conflict with:\n";
- outerAccess.dump());
-
- recordConflict(outerAccess, accessSet);
}
- LLVM_DEBUG(llvm::dbgs() << "Recording access: " << *innerBeginAccess;
- llvm::dbgs() << " at: "; innerAccess.dump());
-
- // Record the current access in the map. It can potentially be folded
- // regardless of whether it may conflict with an outer access.
- bool inserted =
- accessSet.enterScope(innerBeginAccess, innerAccess.getAccessIndex());
- (void)inserted;
- assert(inserted && "the same begin_access cannot be seen twice.");
}
-void AccessConflictAnalysis::visitEndAccess(EndAccessInst *endAccess,
- SparseAccessSet &accessSet) {
- auto *beginAccess = endAccess->getBeginAccess();
+// Helper function for calcBottomUpOrder
+static void calcBottomUpOrderRecurse(LoopRegion *region,
+ llvm::SmallVectorImpl<unsigned> &worklist,
+ LoopRegionFunctionInfo *LRFI) {
+ worklist.push_back(region->getID());
+ for (auto regionIndex : region->getReverseSubregions()) {
+ auto *region = LRFI->getRegion(regionIndex);
+ if (region->isBlock())
+ continue;
+ calcBottomUpOrderRecurse(region, worklist, LRFI);
+ }
+}
+
+// Returns a worklist of loop IDs is bottom-up order.
+void AccessConflictAndMergeAnalysis::calcBottomUpOrder(
+ llvm::SmallVectorImpl<unsigned> &worklist) {
+ auto *topRegion = LRFI->getTopLevelRegion();
+ calcBottomUpOrderRecurse(topRegion, worklist, LRFI);
+}
+
+void AccessConflictAndMergeAnalysis::visitBeginAccess(
+ BeginAccessInst *beginAccess, RegionInfo &info) {
if (beginAccess->getEnforcement() != SILAccessEnforcement::Dynamic)
return;
- unsigned index = result.getAccessIndex(beginAccess);
- LLVM_DEBUG(if (accessSet.seenConflict(index)) llvm::dbgs()
- << "No conflict on one path from " << *beginAccess << " to "
- << *endAccess);
+ // Get the Access info:
+ auto &beginAccessInfo = result.getAccessInfo(beginAccess);
+ if (beginAccessInfo.getKind() == AccessedStorage::Unidentified) {
+ info.unidentifiedAccess = true;
+ }
+ SILAccessKind beginAccessKind = beginAccess->getAccessKind();
+ // check the current in-scope accesses for conflicts:
+ for (auto pair : info.getInScopeAccesses()) {
+ auto *outerBeginAccess = pair.second;
+ // If both are reads, keep the mapped access.
+ if (!accessKindMayConflict(beginAccessKind,
+ outerBeginAccess->getAccessKind())) {
+ continue;
+ }
- // Erase this access from the sparse set. We only want to detect conflicts
- // within the access scope.
- accessSet.exitScope(index);
+ auto &outerAccessInfo = result.getAccessInfo(outerBeginAccess);
+ // If there is no potential conflict, leave the outer access mapped.
+ if (!outerAccessInfo.isDistinctFrom(beginAccessInfo))
+ continue;
+
+ LLVM_DEBUG(beginAccessInfo.dump(); llvm::dbgs() << " may conflict with:\n";
+ outerAccessInfo.dump());
+
+ recordConflict(info, outerAccessInfo);
+ break;
+ }
+
+ // Record the current access to InScopeAccesses.
+ // It can potentially be folded
+ // regardless of whether it may conflict with an outer access.
+ addInScopeAccess(info, beginAccess);
}
-void AccessConflictAnalysis::visitFullApply(FullApplySite fullApply,
- SparseAccessSet &accessSet) {
+void AccessConflictAndMergeAnalysis::visitEndAccess(EndAccessInst *endAccess,
+ RegionInfo &info) {
+ auto *beginAccess = endAccess->getBeginAccess();
+ if (beginAccess->getEnforcement() != SILAccessEnforcement::Dynamic)
+ return;
+ auto &ai = result.getAccessInfo(beginAccess);
+ auto &inScope = info.getInScopeAccesses();
+ if (inScope.find(ai.getAccessIndex()) != inScope.end()) {
+ LLVM_DEBUG(llvm::dbgs() << "No conflict on one path from " << *beginAccess
+ << " to " << *endAccess);
+ removeInScopeAccess(info, beginAccess);
+ }
+
+ // We can merge out-of-scope regardless of having a conflict within a scope,
+ // when encountering an end access instruction,
+ // regardless of having it in the In scope set,
+ // add it to the out of scope set.
+ LLVM_DEBUG(llvm::dbgs() << "Got out of scope from " << *beginAccess << " to "
+ << *endAccess << "\n");
+
+ addOutOfScopeAccess(info, beginAccess);
+}
+
+void AccessConflictAndMergeAnalysis::detectApplyConflicts(
+ const swift::FunctionAccessedStorage &callSiteAccesses,
+ const DenseAccessMap &conflictFreeSet,
+ const swift::FullApplySite &fullApply, RegionInfo &info) {
+ for (auto pair : conflictFreeSet) {
+ auto *outerBeginAccess = pair.second;
+ // If there is no potential conflict, leave the outer access mapped.
+ SILAccessKind accessKind = outerBeginAccess->getAccessKind();
+ AccessInfo &outerAccessInfo = result.getAccessInfo(outerBeginAccess);
+ if (!callSiteAccesses.mayConflictWith(accessKind, outerAccessInfo))
+ continue;
+
+ LLVM_DEBUG(
+ llvm::dbgs() << *fullApply.getInstruction() << " call site access: ";
+ callSiteAccesses.dump(); llvm::dbgs() << " may conflict with:\n";
+ outerAccessInfo.dump());
+
+ recordConflict(info, outerAccessInfo);
+ break;
+ }
+}
+
+void AccessConflictAndMergeAnalysis::visitFullApply(FullApplySite fullApply,
+ RegionInfo &info) {
FunctionAccessedStorage callSiteAccesses;
ASA->getCallSiteEffects(callSiteAccesses, fullApply);
- SparseAccessSet::NoNestedConflictIterator accessIter(accessSet);
- while (BeginAccessInst *outerBeginAccess = accessIter.next()) {
+ detectApplyConflicts(callSiteAccesses, info.getInScopeAccesses(), fullApply,
+ info);
+ detectApplyConflicts(callSiteAccesses, info.getOutOfScopeAccesses(),
+ fullApply, info);
+}
- // If there is no potential conflict, leave the outer access mapped.
- SILAccessKind accessKind = outerBeginAccess->getAccessKind();
- AccessInfo &outerAccess = result.getAccessInfo(outerBeginAccess);
- if (!callSiteAccesses.mayConflictWith(accessKind, outerAccess))
- continue;
-
- LLVM_DEBUG(llvm::dbgs() << *fullApply.getInstruction()
- << " call site access: ";
- callSiteAccesses.dump();
- llvm::dbgs() << " may conflict with:\n";
- outerAccess.dump());
-
- recordConflict(outerAccess, accessSet);
+void AccessConflictAndMergeAnalysis::mergePredAccesses(
+ LoopRegion *region, RegionIDToLocalInfoMap &localRegionInfos) {
+ RegionInfo &info = localRegionInfos.find(region->getID())->getSecond();
+ auto bbRegionParentID = region->getParentID();
+ bool changed = false;
+ for (auto pred : region->getPreds()) {
+ auto *predRegion = LRFI->getRegion(pred);
+ assert((predRegion->getParentID() == bbRegionParentID) &&
+ "predecessor is not part of the parent region - unhandled control "
+ "flow");
+ if (localRegionInfos.find(pred) == localRegionInfos.end()) {
+ // Backedge / irreducable control flow - bail
+ info.reset();
+ // Clear out the accesses of all predecessor:
+ for (auto pred : region->getPreds()) {
+ if (localRegionInfos.find(pred) == localRegionInfos.end()) {
+ // Create a region info with empty-set for predecessors
+ localRegionInfos.insert(
+ std::make_pair(pred, RegionInfo(result.accessMap.size())));
+ }
+ RegionInfo &predInfo = localRegionInfos.find(pred)->getSecond();
+ predInfo.reset();
+ }
+ return;
+ }
+ const RegionInfo &predInfo = localRegionInfos.find(pred)->getSecond();
+ changed = true;
+ merge(info, predInfo);
+ }
+ if (!changed) {
+ // If there are no predecessors
+ info.reset();
+ return;
}
}
-// Merge all predecessor accesses into the local acces set. Only propagate
-// accesses that are still present in all predecessors. The absence of a begin
-// access from a visited predecessor indicates the presence of a conflict. A
-// block has been visited if it has a map entry in blockOutAccess.
-void AccessConflictAnalysis::mergePredAccesses(SILBasicBlock *succBB,
- SparseAccessSet &mergedAccesses) {
- for (SILBasicBlock *predBB : succBB->getPredecessorBlocks()) {
- auto mapI = blockOutAccess.find(predBB);
- if (mapI == blockOutAccess.end())
- continue;
+void AccessConflictAndMergeAnalysis::visitSetForConflicts(
+ const DenseAccessMap &accessSet, RegionInfo &info,
+ AccessConflictAndMergeAnalysis::AccessedStorageSet &loopStorage) {
+ for (auto pair : accessSet) {
+ BeginAccessInst *beginAccess = pair.second;
+ AccessInfo &accessInfo = result.getAccessInfo(beginAccess);
- const DenseAccessSet &predSet = mapI->second;
- mergedAccesses.merge(SparseAccessSet(predSet, result));
+ for (auto loopAccess : loopStorage) {
+ if (loopAccess.isDistinctFrom(accessInfo) && !info.unidentifiedAccess)
+ continue;
+
+ recordConflict(info, loopAccess);
+ break;
+ }
}
}
-// Compute access reachability within the given block.
-void AccessConflictAnalysis::visitBlock(SILBasicBlock *BB) {
- // Sparse set for tracking accesses with an individual block.
- SparseAccessSet accessSet(result);
- mergePredAccesses(BB, accessSet);
+void AccessConflictAndMergeAnalysis::detectConflictsInLoop(
+ LoopRegion *loopRegion, RegionIDToLocalInfoMap &localRegionInfos,
+ LoopRegionToAccessedStorage &accessSetsOfRegions) {
+ assert(loopRegion->isLoop() && "Expected a loop region");
+ auto loopID = loopRegion->getID();
+ RegionInfo &info = localRegionInfos.find(loopID)->getSecond();
+ AccessedStorageSet &loopStorage =
+ accessSetsOfRegions.find(loopID)->getSecond();
+ visitSetForConflicts(info.getInScopeAccesses(), info, loopStorage);
+ visitSetForConflicts(info.getOutOfScopeAccesses(), info, loopStorage);
+}
- for (auto &I : *BB) {
- if (auto *BAI = dyn_cast<BeginAccessInst>(&I)) {
- visitBeginAccess(BAI, accessSet);
+void AccessConflictAndMergeAnalysis::localDataFlowInBlock(
+ LoopRegion *bbRegion, RegionIDToLocalInfoMap &localRegionInfos) {
+ assert(bbRegion->isBlock() && "Expected a block region");
+ auto *bb = bbRegion->getBlock();
+ RegionInfo &info = localRegionInfos.find(bbRegion->getID())->getSecond();
+ for (auto &instr : *bb) {
+ if (auto *beginAccess = dyn_cast<BeginAccessInst>(&instr)) {
+ visitBeginAccess(beginAccess, info);
continue;
}
- if (auto *EAI = dyn_cast<EndAccessInst>(&I)) {
- visitEndAccess(EAI, accessSet);
+ if (auto *endAccess = dyn_cast<EndAccessInst>(&instr)) {
+ visitEndAccess(endAccess, info);
continue;
}
- if (auto fullApply = FullApplySite::isa(&I)) {
- visitFullApply(fullApply, accessSet);
+ if (auto fullApply = FullApplySite::isa(&instr)) {
+ visitFullApply(fullApply, info);
}
}
- LLVM_DEBUG(if (accessSet.hasConflictFreeAccess()) {
- llvm::dbgs() << "Initializing no-conflict access out of bb"
- << BB->getDebugID() << "\n";
- accessSet.dump();
- });
- if (BB->getTerminator()->isFunctionExiting())
- assert(!accessSet.hasInScopeAccess() && "no postdominating end_access");
-
- // Initialize blockOutAccess for this block with the current access set.
- accessSet.copyNoNestedConflictInto(blockOutAccess[BB]);
}
// -----------------------------------------------------------------------------
@@ -558,7 +820,7 @@
/// end_unpaired_access instructions during analysis and deleting them here in
/// the same order, or sorting them here by their begin_unpaired_access index.
static bool
-foldNonNestedAccesses(AccessConflictAnalysis::AccessMap &accessMap) {
+foldNonNestedAccesses(AccessConflictAndMergeAnalysis::AccessMap &accessMap) {
bool changed = false;
// Iteration over accessMap is nondeterministic. Setting the conflict flags
// can be done in any order.
@@ -578,7 +840,7 @@
/// Perform local access marker elimination.
///
-/// Disable accesses to uniquely identified local storage for which no
+/// Disable access checks for uniquely identified local storage for which no
/// accesses can have nested conflicts. This is only valid if the function's
/// local storage cannot be potentially modified by unidentified access:
///
@@ -594,7 +856,7 @@
/// Unidentified access within the function without the [no_nested_conflict]
/// flag.
static bool
-removeLocalNonNestedAccess(const AccessConflictAnalysis::Result &result,
+removeLocalNonNestedAccess(const AccessConflictAndMergeAnalysis::Result &result,
const FunctionAccessedStorage &functionAccess) {
if (functionAccess.hasUnidentifiedAccess())
return false;
@@ -619,6 +881,172 @@
return changed;
}
+// TODO: support multi-end access cases
+static EndAccessInst *getSingleEndAccess(BeginAccessInst *inst) {
+ EndAccessInst *end = nullptr;
+ for (auto *currEnd : inst->getEndAccesses()) {
+ if (end == nullptr)
+ end = currEnd;
+ else
+ return nullptr;
+ }
+ return end;
+}
+
+struct SCCInfo {
+ unsigned id;
+ bool hasLoop;
+};
+
+static void mergeEndAccesses(BeginAccessInst *parentIns,
+ BeginAccessInst *childIns) {
+ auto *endP = getSingleEndAccess(parentIns);
+ if (!endP)
+ llvm_unreachable("not supported");
+ auto *endC = getSingleEndAccess(childIns);
+ if (!endC)
+ llvm_unreachable("not supported");
+
+ endC->setOperand(parentIns);
+ endP->eraseFromParent();
+}
+
+static bool canMergeEnd(BeginAccessInst *parentIns, BeginAccessInst *childIns) {
+ auto *endP = getSingleEndAccess(parentIns);
+ if (!endP)
+ return false;
+
+ auto *endC = getSingleEndAccess(childIns);
+ if (!endC)
+ return false;
+
+ return true;
+}
+
+// TODO: support other merge patterns
+static bool
+canMergeBegin(PostDominanceInfo *postDomTree,
+ const llvm::DenseMap<SILBasicBlock *, SCCInfo> &blockToSCCMap,
+ BeginAccessInst *parentIns, BeginAccessInst *childIns) {
+ if (!postDomTree->properlyDominates(childIns, parentIns)) {
+ return false;
+ }
+ auto parentSCCIt = blockToSCCMap.find(parentIns->getParent());
+ assert(parentSCCIt != blockToSCCMap.end() && "Expected block in SCC Map");
+ auto childSCCIt = blockToSCCMap.find(childIns->getParent());
+ assert(childSCCIt != blockToSCCMap.end() && "Expected block in SCC Map");
+ auto parentSCC = parentSCCIt->getSecond();
+ auto childSCC = childSCCIt->getSecond();
+ if (parentSCC.id == childSCC.id) {
+ return true;
+ }
+ if (parentSCC.hasLoop) {
+ return false;
+ }
+ if (childSCC.hasLoop) {
+ return false;
+ }
+ return true;
+}
+
+static bool
+canMerge(PostDominanceInfo *postDomTree,
+ const llvm::DenseMap<SILBasicBlock *, SCCInfo> &blockToSCCMap,
+ BeginAccessInst *parentIns, BeginAccessInst *childIns) {
+ if (!canMergeBegin(postDomTree, blockToSCCMap, parentIns, childIns))
+ return false;
+
+ return canMergeEnd(parentIns, childIns);
+}
+
+/// Perform access merging.
+static bool mergeAccesses(
+ SILFunction *F, PostDominanceInfo *postDomTree,
+ const AccessConflictAndMergeAnalysis::MergeablePairs &mergePairs) {
+ bool changed = false;
+
+ // Compute a map from each block to its SCC -
+ // For now we can't merge cross SCC boundary
+ llvm::DenseMap<SILBasicBlock *, SCCInfo> blockToSCCMap;
+ SCCInfo info;
+ info.id = 0;
+ for (auto sccIt = scc_begin(F); !sccIt.isAtEnd(); ++sccIt) {
+ ++info.id;
+ info.hasLoop = sccIt.hasLoop();
+ for (auto *bb : *sccIt) {
+ blockToSCCMap.insert(std::make_pair(bb, info));
+ }
+ }
+ // make a temporary reverse copy to work on:
+ // It is in reverse order just to make it easier to debug / follow
+ AccessConflictAndMergeAnalysis::MergeablePairs workPairs;
+ workPairs.append(mergePairs.rbegin(), mergePairs.rend());
+
+ // Assume the result contains two access pairs to be merged:
+ // (begin_access %1, begin_access %2)
+ // = merge end_access %1 with begin_access %2
+ // (begin_access %2, begin_access %3)
+ // = merge end_access %2 with begin_access %3
+ // After merging the first pair, begin_access %2 is removed,
+ // so the second pair in the result list points to a to-be-deleted
+ // begin_access instruction. We store (begin_access %2 -> begin_access %1)
+ // to re-map a merged begin_access to it's replaced instruction.
+ llvm::DenseMap<BeginAccessInst *, BeginAccessInst *> oldToNewMap;
+
+ while (!workPairs.empty()) {
+ auto curr = workPairs.pop_back_val();
+ auto *parentIns = curr.first;
+ auto *childIns = curr.second;
+ if (oldToNewMap.count(parentIns) != 0) {
+ parentIns = oldToNewMap[parentIns];
+ }
+ assert(oldToNewMap.count(childIns) == 0 &&
+ "Can't have same child instruction twice in map");
+
+ // The optimization might not currently support every mergeable pair
+ // If the current pattern is not supported - skip
+ if (!canMerge(postDomTree, blockToSCCMap, parentIns, childIns))
+ continue;
+
+ LLVM_DEBUG(llvm::dbgs()
+ << "Merging: " << *childIns << " into " << *parentIns << "\n");
+
+ // Change the type of access of parent:
+ // should be the worse between it and child
+ auto childAccess = childIns->getAccessKind();
+ if (parentIns->getAccessKind() < childAccess) {
+ parentIns->setAccessKind(childAccess);
+ }
+
+ // Change the no nested conflict of parent:
+ // should be the worst case scenario: we might merge to non-conflicting
+ // scopes to a conflicting one. f the new result does not conflict,
+ // a later on pass will remove the flag
+ parentIns->setNoNestedConflict(false);
+
+ // remove end accesses and create new ones that cover bigger scope:
+ mergeEndAccesses(parentIns, childIns);
+
+ // In case the child instruction is at the map,
+ // updated the oldToNewMap to reflect that we are getting rid of it:
+ oldToNewMap.insert(std::make_pair(childIns, parentIns));
+
+ // Modify the users of child instruction to use the parent:
+ childIns->replaceAllUsesWith(parentIns);
+
+ changed = true;
+ }
+
+ // Delete all old instructions from parent scopes:
+ while (!oldToNewMap.empty()) {
+ auto curr = oldToNewMap.begin();
+ auto *oldIns = curr->getFirst();
+ oldToNewMap.erase(oldIns);
+ oldIns->eraseFromParent();
+ }
+ return changed;
+}
+
namespace {
struct AccessEnforcementOpts : public SILFunctionTransform {
void run() override {
@@ -629,18 +1057,19 @@
LLVM_DEBUG(llvm::dbgs() << "Running local AccessEnforcementOpts on "
<< F->getName() << "\n");
- PostOrderFunctionInfo *PO = getAnalysis<PostOrderAnalysis>()->get(F);
+ LoopRegionFunctionInfo *LRFI = getAnalysis<LoopRegionAnalysis>()->get(F);
AccessedStorageAnalysis *ASA = getAnalysis<AccessedStorageAnalysis>();
- auto result = AccessConflictAnalysis(F, PO, ASA).analyze();
+ AccessConflictAndMergeAnalysis a(LRFI, ASA);
+ a.analyze();
+ auto result = a.getResult();
// Perform access folding by setting the [no_nested_conflict] flag on
// begin_access instructions.
- if (!foldNonNestedAccesses(result.accessMap))
- return;
-
- // Recompute AccessStorageAnalysis, just for this function, to update the
- // StorageAccessInfo::noNestedConflict status for each accessed storage.
- invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
+ if (foldNonNestedAccesses(result.accessMap)) {
+ // Recompute AccessStorageAnalysis, just for this function, to update the
+ // StorageAccessInfo::noNestedConflict status for each accessed storage.
+ invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
+ }
// Use the updated AccessedStorageAnalysis to find any uniquely identified
// local storage that has no nested conflict on any of its accesses within
@@ -652,6 +1081,14 @@
const FunctionAccessedStorage &functionAccess = ASA->getEffects(F);
if (removeLocalNonNestedAccess(result, functionAccess))
invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
+
+ // Perform the access merging
+ // The inital version of the optimization requires a postDomTree
+ PostDominanceAnalysis *postDomAnalysis =
+ getAnalysis<PostDominanceAnalysis>();
+ PostDominanceInfo *postDomTree = postDomAnalysis->get(F);
+ if (mergeAccesses(F, postDomTree, result.mergePairs))
+ invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
}
};
} // namespace
diff --git a/test/SILOptimizer/access_enforcement_opts.sil b/test/SILOptimizer/access_enforcement_opts.sil
index debfe0f..e9c4555 100644
--- a/test/SILOptimizer/access_enforcement_opts.sil
+++ b/test/SILOptimizer/access_enforcement_opts.sil
@@ -365,8 +365,8 @@
// CHECK-LABEL: sil @testInoutReadEscapeRead : $@convention(thin) () -> () {
// CHECK: [[BOX:%.*]] = alloc_box ${ var Int64 }, var, name "x"
// CHECK: [[BOXADR:%.*]] = project_box [[BOX]] : ${ var Int64 }, 0
-// CHECK: begin_access [read] [static] [no_nested_conflict] [[BOXADR]] : $*Int64
-// CHECK: begin_access [read] [static] [no_nested_conflict] [[BOXADR]] : $*Int64
+// CHECK: begin_access [read] [static] [[BOXADR]] : $*Int64
+// CHECK-NOT: begin_access
// CHECK-LABEL: } // end sil function 'testInoutReadEscapeRead'
sil @testInoutReadEscapeRead : $@convention(thin) () -> () {
bb0:
@@ -427,9 +427,11 @@
// CHECK-LABEL: sil @testInoutReadEscapeWrite : $@convention(thin) () -> () {
// CHECK: [[BOX:%.*]] = alloc_box ${ var Int64 }, var, name "x"
// CHECK: [[BOXADR:%.*]] = project_box [[BOX]] : ${ var Int64 }, 0
-// CHECK: begin_access [read] [dynamic] [[BOXADR]] : $*Int64
+// CHECK: [[BEGIN:%.*]] = begin_access [read] [dynamic] [[BOXADR]] : $*Int64
// CHECK: apply
-// CHECK: begin_access [read] [dynamic] [no_nested_conflict] [[BOXADR]] : $*Int64
+// CHECK-NOT: begin_access
+// CHECK: end_access [[BEGIN]]
+// CHECK-NOT: begin_access
// CHECK-LABEL: } // end sil function 'testInoutReadEscapeWrite'
sil @testInoutReadEscapeWrite : $@convention(thin) () -> () {
bb0:
@@ -490,9 +492,11 @@
// CHECK-LABEL: sil @$S17enforce_with_opts24testInoutWriteEscapeReadyyF : $@convention(thin) () -> () {
// CHECK: [[BOX:%.*]] = alloc_box ${ var Int64 }, var, name "x"
// CHECK: [[BOXADR:%.*]] = project_box [[BOX]] : ${ var Int64 }, 0
-// CHECK: begin_access [modify] [dynamic] [[BOXADR]] : $*Int64
+// CHECK: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[BOXADR]] : $*Int64
// CHECK: apply
-// CHECK: begin_access [read] [dynamic] [no_nested_conflict] %1 : $*Int64
+// CHECK-NOT: begin_access
+// CHECK: end_access [[BEGIN]]
+// CHECK-NOT: begin_access
// CHECK-LABEL: } // end sil function '$S17enforce_with_opts24testInoutWriteEscapeReadyyF'
sil @$S17enforce_with_opts24testInoutWriteEscapeReadyyF : $@convention(thin) () -> () {
bb0:
@@ -561,9 +565,11 @@
// CHECK-LABEL: sil @$S17enforce_with_opts020testInoutWriteEscapeF0yyF : $@convention(thin) () -> () {
// CHECK: [[BOX:%.*]] = alloc_box ${ var Int64 }, var, name "x"
// CHECK: [[BOXADR:%.*]] = project_box [[BOX]] : ${ var Int64 }, 0
-// CHECK: begin_access [modify] [dynamic] [[BOXADR]] : $*Int64
+// CHECK: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[BOXADR]] : $*Int64
// CHECK: apply
-// CHECK: begin_access [read] [dynamic] [no_nested_conflict] [[BOXADR]] : $*Int64
+// CHECK-NOT: begin_access
+// CHECK: end_access [[BEGIN]]
+// CHECK-NOT: begin_access
// CHECK-LABEL: } // end sil function '$S17enforce_with_opts020testInoutWriteEscapeF0yyF'
sil @$S17enforce_with_opts020testInoutWriteEscapeF0yyF : $@convention(thin) () -> () {
bb0:
@@ -912,3 +918,430 @@
%10 = tuple ()
return %10 : $()
}
+
+// public func testOldToNewMapRead() {
+// Checks merging of 3 scopes resulting in a larger read scope
+//
+// CHECK-LABEL: sil @testOldToNewMapRead : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [read] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testOldToNewMapRead'
+sil @testOldToNewMapRead : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [read] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ %4 = begin_access [read] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %7 = begin_access [read] [dynamic] %0 : $*X
+ %8 = load %7 : $*X
+ end_access %7 : $*X
+ %10 = tuple ()
+ return %10 : $()
+}
+
+// public func testOldToNewMapWrite) {
+// Checks merging of 3 scopes resulting in a larger modify scope
+//
+// CHECK-LABEL: sil @testOldToNewMapWrite : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK: store {{.*}} to [[BEGIN]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testOldToNewMapWrite'
+sil @testOldToNewMapWrite : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [read] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ %4 = metatype $@thin X.Type
+ // function_ref X.init()
+ %5 = function_ref @Xinit : $@convention(method) (@thin X.Type) -> X
+ %6 = apply %5(%4) : $@convention(method) (@thin X.Type) -> X
+ %7 = begin_access [modify] [dynamic] %0 : $*X
+ store %6 to %7 : $*X
+ end_access %7 : $*X
+ %10 = begin_access [read] [dynamic] %0 : $*X
+ %11 = load %10 : $*X
+ end_access %10 : $*X
+ %12 = tuple ()
+ return %12 : $()
+}
+
+// public func testDataFlowAcrossBBs() {
+// Checks merging of scopes across basic blocks - propagating that information
+//
+// CHECK-LABEL: sil @testDataFlowAcrossBBs : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: br bb2
+// CHECK: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testDataFlowAcrossBBs'
+sil @testDataFlowAcrossBBs : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [modify] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ br bb2
+
+bb2:
+ %4 = begin_access [read] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %7 = tuple ()
+ return %7 : $()
+}
+
+// public func testDataFlowAcrossInnerLoop() {
+// Checks merging of scopes across an inner loop
+//
+// CHECK-LABEL: sil @testDataFlowAcrossInnerLoop : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: cond_br {{.*}}, bb1, bb2
+// CHECK: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testDataFlowAcrossInnerLoop'
+sil @testDataFlowAcrossInnerLoop : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [modify] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %cond = integer_literal $Builtin.Int1, 1
+ cond_br %cond, bb1, bb2
+
+bb2:
+ %4 = begin_access [read] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %7 = tuple ()
+ return %7 : $()
+}
+
+// public func testConflictInInnerLoop() {
+// Checks summary propagation and conflict detection in sub-regions
+//
+// CHECK-LABEL: sil @testConflictInInnerLoop : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: [[BEGIN2:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN2]] : $*X
+// CHECK-NEXT: end_access [[BEGIN2]] : $*X
+// CHECK: cond_br {{.*}}, bb1, bb2
+// CHECK: [[BEGIN3:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN3]] : $*X
+// CHECK-NEXT: end_access [[BEGIN3]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testConflictInInnerLoop'
+sil @testConflictInInnerLoop : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [modify] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %4 = begin_access [read] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %cond = integer_literal $Builtin.Int1, 1
+ cond_br %cond, bb1, bb2
+
+bb2:
+ %7 = begin_access [read] [dynamic] %0 : $*X
+ %8 = load %7 : $*X
+ end_access %7 : $*X
+ %10 = tuple ()
+ return %10 : $()
+}
+
+sil hidden_external [global_init] @globalAddressor : $@convention(thin) () -> Builtin.RawPointer
+
+// public func testUnidentifiedAccessInLoop() {
+// Tests Unidentified Accesses detection + propagation
+//
+// CHECK-LABEL: sil @testUnidentifiedAccessInLoop : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: [[BEGIN2:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] {{.*}} : $*Int64
+// CHECK-NEXT: load [[BEGIN2]] : $*Int64
+// CHECK-NEXT: end_access [[BEGIN2]] : $*Int64
+// CHECK: cond_br {{.*}}, bb1, bb2
+// CHECK: [[BEGIN3:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN3]] : $*X
+// CHECK-NEXT: end_access [[BEGIN3]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testUnidentifiedAccessInLoop'
+sil @testUnidentifiedAccessInLoop : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [modify] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %u0 = function_ref @globalAddressor : $@convention(thin) () -> Builtin.RawPointer
+ %u1 = apply %u0() : $@convention(thin) () -> Builtin.RawPointer
+ %u2 = pointer_to_address %u1 : $Builtin.RawPointer to [strict] $*Int64
+ %u3 = begin_access [read] [dynamic] %u2 : $*Int64
+ %u4 = load %u3 : $*Int64
+ end_access %u3 : $*Int64
+ %cond = integer_literal $Builtin.Int1, 1
+ cond_br %cond, bb1, bb2
+
+bb2:
+ %7 = begin_access [read] [dynamic] %0 : $*X
+ %8 = load %7 : $*X
+ end_access %7 : $*X
+ %10 = tuple ()
+ return %10 : $()
+}
+
+// public func testIrreducibleGraph() {
+// Checks detection of irreducible control flow / bail
+// See mergePredAccesses in the algorithm
+//
+// CHECK-LABEL: sil @testIrreducibleGraph : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: [[BEGIN2:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN2]] : $*X
+// CHECK-NEXT: end_access [[BEGIN2]] : $*X
+// CHECK: cond_br {{.*}}, bb2, bb3
+// CHECK: [[BEGIN3:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN3]] : $*X
+// CHECK-NEXT: end_access [[BEGIN3]] : $*X
+// CHECK: cond_br {{.*}}, bb3, bb4
+// CHECK: [[BEGIN4:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN4]] : $*X
+// CHECK-NEXT: end_access [[BEGIN4]] : $*X
+// CHECK: cond_br {{.*}}, bb2, bb1
+// CHECK: [[BEGIN5:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN5]] : $*X
+// CHECK-NEXT: end_access [[BEGIN5]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testIrreducibleGraph'
+sil @testIrreducibleGraph : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [read] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %4 = begin_access [modify] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %cond1 = integer_literal $Builtin.Int1, 1
+ cond_br %cond1, bb2, bb3
+
+bb2:
+ %6 = begin_access [read] [dynamic] %0 : $*X
+ %7 = load %6 : $*X
+ end_access %6 : $*X
+ %cond2 = integer_literal $Builtin.Int1, 1
+ cond_br %cond2, bb3, bb4
+
+bb3:
+ %8 = begin_access [read] [dynamic] %0 : $*X
+ %9 = load %8 : $*X
+ end_access %8 : $*X
+ %cond3 = integer_literal $Builtin.Int1, 1
+ cond_br %cond3, bb2, bb1
+
+bb4:
+ %10 = begin_access [read] [dynamic] %0 : $*X
+ %11 = load %10 : $*X
+ end_access %10 : $*X
+ %12 = tuple ()
+ return %12 : $()
+}
+
+// public func testIrreducibleGraph2() {
+// Checks detection of irreducible control flow / bail + parts that we *can* merge
+// See disableCrossBlock in the algorithm: this detects this corner case
+//
+// CHECK-LABEL: sil @testIrreducibleGraph2 : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK: cond_br {{.*}}, bb2, bb3
+// CHECK: [[BEGIN2:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN2]] : $*X
+// CHECK-NEXT: end_access [[BEGIN2]] : $*X
+// CHECK-NEXT: br bb3
+// CHECK: [[BEGIN3:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN3]] : $*X
+// CHECK-NEXT: end_access [[BEGIN3]] : $*X
+// CHECK: br bb4
+// CHECK: [[BEGIN4:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN4]] : $*X
+// CHECK-NEXT: end_access [[BEGIN4]] : $*X
+// CHECK: cond_br {{.*}}, bb2, bb5
+// CHECK: [[BEGIN5:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN5]] : $*X
+// CHECK-NEXT: end_access [[BEGIN5]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testIrreducibleGraph2'
+sil @testIrreducibleGraph2 : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [read] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %4 = begin_access [modify] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %cond1 = integer_literal $Builtin.Int1, 1
+ cond_br %cond1, bb2, bb3
+
+bb2:
+ %6 = begin_access [read] [dynamic] %0 : $*X
+ %7 = load %6 : $*X
+ end_access %6 : $*X
+ br bb3
+
+bb3:
+ %8 = begin_access [read] [dynamic] %0 : $*X
+ %9 = load %8 : $*X
+ end_access %8 : $*X
+ br bb4
+
+bb4:
+ %10 = begin_access [read] [dynamic] %0 : $*X
+ %11 = load %10 : $*X
+ end_access %10 : $*X
+ %cond2 = integer_literal $Builtin.Int1, 1
+ cond_br %cond2, bb2, bb5
+
+bb5:
+ %13 = begin_access [read] [dynamic] %0 : $*X
+ %14 = load %13 : $*X
+ end_access %13 : $*X
+ %16 = tuple ()
+ return %16 : $()
+}
+
+
+// public func testStronglyConnectedComponent() {
+// During the merge optimization,
+// Check that we don't merge cross strongly component boundaries for now
+//
+// CHECK-LABEL: sil @testStronglyConnectedComponent : $@convention(thin) () -> () {
+// CHECK: [[GLOBAL:%.*]] = global_addr @globalX : $*X
+// CHECK-NEXT: [[BEGIN:%.*]] = begin_access [modify] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN]] : $*X
+// CHECK-NEXT: br bb1
+// CHECK: load [[BEGIN]] : $*X
+// CHECK-NEXT: end_access [[BEGIN]] : $*X
+// CHECK: cond_br {{.*}}, bb2, bb3
+// CHECK: [[BEGIN2:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN2]] : $*X
+// CHECK-NEXT: end_access [[BEGIN2]] : $*X
+// CHECK-NEXT: br bb3
+// CHECK: [[BEGIN3:%.*]] = begin_access [read] [dynamic] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN3]] : $*X
+// CHECK: br bb4
+// CHECK: load [[BEGIN3]] : $*X
+// CHECK-NEXT: end_access [[BEGIN3]] : $*X
+// CHECK: cond_br {{.*}}, bb5, bb6
+// CHECK: [[BEGIN4:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN4]] : $*X
+// CHECK-NEXT: end_access [[BEGIN4]] : $*X
+// CHECK: br bb2
+// CHECK: [[BEGIN5:%.*]] = begin_access [read] [dynamic] [no_nested_conflict] [[GLOBAL]] : $*X
+// CHECK-NEXT: load [[BEGIN5]] : $*X
+// CHECK-NEXT: end_access [[BEGIN5]] : $*X
+// CHECK-NOT: begin_access
+// CHECK-LABEL: } // end sil function 'testStronglyConnectedComponent'
+sil @testStronglyConnectedComponent : $@convention(thin) () -> () {
+bb0:
+ %0 = global_addr @globalX: $*X
+ %1 = begin_access [read] [dynamic] %0 : $*X
+ %2 = load %1 : $*X
+ end_access %1 : $*X
+ br bb1
+
+bb1:
+ %4 = begin_access [modify] [dynamic] %0 : $*X
+ %5 = load %4 : $*X
+ end_access %4 : $*X
+ %cond1 = integer_literal $Builtin.Int1, 1
+ cond_br %cond1, bb2, bb3
+
+bb2:
+ %6 = begin_access [read] [dynamic] %0 : $*X
+ %7 = load %6 : $*X
+ end_access %6 : $*X
+ br bb3
+
+bb3:
+ %8 = begin_access [read] [dynamic] %0 : $*X
+ %9 = load %8 : $*X
+ end_access %8 : $*X
+ br bb4
+
+bb4:
+ %10 = begin_access [read] [dynamic] %0 : $*X
+ %11 = load %10 : $*X
+ end_access %10 : $*X
+ %cond2 = integer_literal $Builtin.Int1, 1
+ cond_br %cond2, bb5, bb6
+
+bb5:
+ %13 = begin_access [read] [dynamic] %0 : $*X
+ %14 = load %13 : $*X
+ end_access %13 : $*X
+ br bb2
+
+bb6:
+ %16 = begin_access [read] [dynamic] %0 : $*X
+ %17 = load %16 : $*X
+ end_access %16 : $*X
+ %19 = tuple ()
+ return %19 : $()
+}
diff --git a/test/SILOptimizer/licm_exclusivity.swift b/test/SILOptimizer/licm_exclusivity.swift
index 93cbc9c..7fac624 100644
--- a/test/SILOptimizer/licm_exclusivity.swift
+++ b/test/SILOptimizer/licm_exclusivity.swift
@@ -14,7 +14,6 @@
// TESTSIL: br bb{{.*}}
// TESTSIL-NEXT bb{{.*}}:
// TESTSIL: end_access
-// TESTSIL: return
var x = 0
func run_ReversedArray(_ N: Int) {
let array = Array(repeating: 1, count: 42)
@@ -32,14 +31,11 @@
// TEST2-LABEL: Processing loops in {{.*}}count_unicodeScalars{{.*}}
// TEST2: Hoist and Sink pairs attempt
// TEST2: Hoisted
-// TEST2: cloning
-// TEST2: Successfully hosited and sank pair
// TESTSIL-LABEL: sil @$S16licm_exclusivity20count_unicodeScalarsyySS17UnicodeScalarViewVF : $@convention(thin) (@guaranteed String.UnicodeScalarView) -> () {
// TESTSIL: bb0(%0 : $String.UnicodeScalarView)
// TESTSIL-NEXT: %1 = global_addr @$S16licm_exclusivity5countSivp : $*Int
// TESTSIL: begin_access [modify] [dynamic] [no_nested_conflict] %1 : $*Int
-// TESTSIL-NEXT: br bb1
// TESTSIL: end_access
// TESTSIL: return
var count: Int = 0
diff --git a/test/SILOptimizer/merge_exclusivity.swift b/test/SILOptimizer/merge_exclusivity.swift
new file mode 100644
index 0000000..91cb4be
--- /dev/null
+++ b/test/SILOptimizer/merge_exclusivity.swift
@@ -0,0 +1,354 @@
+// RUN: %target-swift-frontend -O -enforce-exclusivity=checked -emit-sil -primary-file %s | %FileCheck %s --check-prefix=TESTSIL
+// REQUIRES: optimized_stdlib,asserts
+// REQUIRES: PTRSIZE=64
+
+public var check: UInt64 = 0
+
+@inline(never)
+func sum(_ x: UInt64, _ y: UInt64) -> UInt64 {
+ return x &+ y
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest1yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL: bb5
+// TESTSIL: [[B2:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B2]]
+// TESTSIL: store {{.*}} to [[B2]]
+// TESTSIL: end_access [[B2]]
+// TESTSIL: bb6
+// TESTSIL: [[B3:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B3]]
+// TESTSIL: store {{.*}} to [[B3]]
+// TESTSIL: end_access [[B3]]
+// TESTSIL: bb7
+// TESTSIL: [[B4:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B4]]
+// TESTSIL: store {{.*}} to [[B4]]
+// TESTSIL: end_access [[B4]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest1yySiF'
+@inline(never)
+public func MergeTest1(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ if (e == 0) {
+ check = sum(check, UInt64(1))
+ }
+ else {
+ check = sum(check, UInt64(2))
+ }
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest2yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL: bb6
+// TESTSIL: [[B2:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B2]]
+// TESTSIL: store {{.*}} to [[B2]]
+// TESTSIL: end_access [[B2]]
+// TESTSIL: bb7
+// TESTSIL: [[B3:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B3]]
+// TESTSIL: store {{.*}} to [[B3]]
+// TESTSIL: end_access [[B3]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest2yySiF'
+@inline(never)
+public func MergeTest2(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ if (e == 0) {
+ check = sum(check, UInt64(1))
+ }
+ else {
+ check = sum(check, UInt64(2))
+ }
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest3yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest3yySiF'
+@inline(never)
+public func MergeTest3(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest4yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL: bb7
+// TESTSIL: [[B2:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B2]]
+// TESTSIL: store {{.*}} to [[B2]]
+// TESTSIL: end_access [[B2]]
+// TESTSIL: bb8
+// TESTSIL: [[B3:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B3]]
+// TESTSIL: store {{.*}} to [[B3]]
+// TESTSIL: end_access [[B3]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest4yySiF'
+@inline(never)
+public func MergeTest4(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ if (e == 0) {
+ check = sum(check, UInt64(1))
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest5yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL: bb6
+// TESTSIL: [[B2:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B2]]
+// TESTSIL: store {{.*}} to [[B2]]
+// TESTSIL: end_access [[B2]]
+// TESTSIL: bb7
+// TESTSIL: [[B3:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B3]]
+// TESTSIL: store {{.*}} to [[B3]]
+// TESTSIL: end_access [[B3]]
+// TESTSIL: bb8
+// TESTSIL: [[B4:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL-NEXT: load [[B4]]
+// TESTSIL: store {{.*}} to [[B4]]
+// TESTSIL: end_access [[B4]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest5yySiF'
+@inline(never)
+public func MergeTest5(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ if (e == 0) {
+ check = sum(check, UInt64(1))
+ }
+ else {
+ check = sum(check, UInt64(2))
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest6yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest6yySiF'
+@inline(never)
+public func MergeTest6(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ for _ in range {
+ check = sum(check, UInt64(e))
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+@inline(never)
+public func foo() {
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest7yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest7yySiF'
+@inline(never)
+public func MergeTest7(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ for _ in range {
+ foo()
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity10MergeTest8yySiF : $@convention(thin)
+// TESTSIL: bb0
+// TESTSIL: [[GLOBALVAR:%.*]] = global_addr @$S17merge_exclusivity5checks6UInt64Vvp
+// TESTSIL: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[GLOBALVAR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL-NOT: begin_access
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity10MergeTest8yySiF'
+@inline(never)
+public func MergeTest8(_ N: Int) {
+ let range = 0..<10000
+ check = 0
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ for _ in range {
+ foo()
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+ for _ in 1...N {
+ for e in range {
+ check = sum(check, UInt64(e))
+ for _ in range {
+ foo()
+ }
+ check = sum(check, UInt64(e))
+ }
+ }
+}
+
+// Large, test that tests the interaction between access merging,
+// and the rest of the access optimizations.
+
+public protocol WriteProt {
+ func writeTo(_ stream: StreamClass)
+}
+
+public final class StreamClass {
+ private var buffer: [UInt8]
+
+ public init() {
+ self.buffer = []
+ }
+
+ public func write(_ byte: UInt8) {
+ buffer.append(byte)
+ }
+
+ public func write(_ value: WriteProt) {
+ value.writeTo(self)
+ }
+
+ public func writeEscaped(_ string: String) {
+ writeEscaped(string: string.utf8)
+ }
+
+ public func writeEscaped<T: Collection>(
+ string sequence: T
+ ) where T.Iterator.Element == UInt8 {
+ for character in sequence {
+ buffer.append(character)
+ buffer.append(character)
+ }
+ }
+}
+
+public func toStream(_ stream: StreamClass, _ value: WriteProt) -> StreamClass {
+ stream.write(value)
+ return stream
+}
+
+extension UInt8: WriteProt {
+ public func writeTo(_ stream: StreamClass) {
+ stream.write(self)
+ }
+}
+
+public func asWriteProt(_ string: String) -> WriteProt {
+ return EscapedString(value: string)
+}
+
+private struct EscapedString: WriteProt {
+ let value: String
+
+ func writeTo(_ stream: StreamClass) {
+ _ = toStream(stream, UInt8(ascii: "a"))
+ stream.writeEscaped(value)
+ _ = toStream(stream, UInt8(ascii: "a"))
+ }
+}
+
+public func asWriteProt<T>(_ items: [T], transform: @escaping (T) -> String) -> WriteProt {
+ return EscapedTransforme(items: items, transform: transform)
+}
+
+private struct EscapedTransforme<T>: WriteProt {
+ let items: [T]
+ let transform: (T) -> String
+
+ func writeTo(_ stream: StreamClass) {
+ for (i, item) in items.enumerated() {
+ if i != 0 { _ = toStream(stream, asWriteProt(transform(item))) }
+ _ = toStream(stream, asWriteProt(transform(item)))
+ }
+ }
+}
+
+// TESTSIL-LABEL: sil [noinline] @$S17merge_exclusivity14run_MergeTest9yySiF : $@convention(thin)
+// TESTSIL: [[REFADDR:%.*]] = ref_element_addr {{.*}} : $StreamClass, #StreamClass.buffer
+// TESTSIL-NEXT: [[B1:%.*]] = begin_access [modify] [dynamic] [no_nested_conflict] [[REFADDR]]
+// TESTSIL: end_access [[B1]]
+// TESTSIL: [[BCONF:%.*]] = begin_access [modify] [dynamic] [[REFADDR]]
+// TESTSIL: apply {{.*}} : $@convention(method) (Int, @inout Array<UInt8>) -> ()
+// TESTSIL: end_access [[BCONF]]
+// TESTSIL: [[BCONF:%.*]] = begin_access [modify] [dynamic] [[REFADDR]]
+// TESTSIL: apply {{.*}} : $@convention(method) (Int, @inout Array<UInt8>) -> ()
+// TESTSIL: end_access [[BCONF]]
+// TESTSIL: [[BCONF:%.*]] = begin_access [modify] [dynamic] [[REFADDR]]
+// TESTSIL: apply {{.*}} : $@convention(method) (Int, @inout Array<UInt8>) -> ()
+// TESTSIL: end_access [[BCONF]]
+// TESTSIL-LABEL: } // end sil function '$S17merge_exclusivity14run_MergeTest9yySiF'
+@inline(never)
+public func run_MergeTest9(_ N: Int) {
+ struct Thing {
+ var value: String
+ init(_ value: String) { self.value = value }
+ }
+ let listOfStrings: [String] = (0..<10).map { "This is the number: \($0)!\n" }
+ let listOfThings: [Thing] = listOfStrings.map(Thing.init)
+ for _ in 1...N {
+ let stream = StreamClass()
+ _ = toStream(stream, asWriteProt(listOfThings, transform: { $0.value }))
+ }
+}
