blob: c00f9b6d226df31788deabbb9d0923b1391ee552 [file] [log] [blame]
//===------ YieldOnceCheck.cpp - Check usage of yields in accessors ------===//
// 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 pass statically verifies that yield-once coroutines, such as the
// generalized accessors `read` and `modify`, yield exactly once in every
// invocation, and diagnoses any violation of this property. This pass uses a
// linear-time, data-flow analysis to check that every path in the control-flow
// graph of the coroutine has a yield instruction before a return instruction.
#define DEBUG_TYPE "yield-once-check"
#include "swift/AST/ASTWalker.h"
#include "swift/AST/DiagnosticsSIL.h"
#include "swift/AST/Expr.h"
#include "swift/AST/Stmt.h"
#include "swift/SIL/BasicBlockUtils.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/Dominance.h"
#include "swift/SIL/TerminatorUtils.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/ADT/BreadthFirstIterator.h"
#include "llvm/ADT/DenseSet.h"
using namespace swift;
namespace {
class YieldOnceCheck : public SILFunctionTransform {
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)...);
/// Data-flow analysis state that is associated with basic blocks.
struct BBState {
/// Indicates whether a basic block is encountered before seeing a yield
/// (BeforeYield) or after seeing a yield (AfterYield), or in both states
/// (Conflict). This enum is a semi-lattice where Conflict is the top and
/// the merge of BeforeYield and AfterYield states is Conflict.
enum YieldState { BeforeYield, AfterYield, Conflict } yieldState;
// The following states are maintained for emitting diagnostics.
/// For AfterYield and Conflict states, this field records the yield
/// instruction that was seen while propagating the state.
SILInstruction *yieldInst;
/// For Conflict state, these fields record the basic blocks that
/// propagated the 'AfterYield' and 'BeforeYield' states which resulted
/// in the Conflict.
SILBasicBlock *yieldingPred;
SILBasicBlock *nonYieldingPred;
BBState(YieldState yState, SILInstruction *yieldI, SILBasicBlock *yieldPred,
SILBasicBlock *noYieldPred)
: yieldState(yState), yieldInst(yieldI), yieldingPred(yieldPred),
nonYieldingPred(noYieldPred) {}
static BBState getInitialState() {
return BBState(BeforeYield, nullptr, nullptr, nullptr);
static BBState getAfterYieldState(SILInstruction *yieldI) {
return BBState(AfterYield, yieldI, nullptr, nullptr);
static BBState getConflictState(SILInstruction *yieldI,
SILBasicBlock *yieldPred,
SILBasicBlock *noYieldPred) {
assert(yieldI && yieldPred && noYieldPred);
return BBState(Conflict, yieldI, yieldPred, noYieldPred);
SILInstruction *getYieldInstruction() const {
assert(yieldState == AfterYield || yieldState == Conflict);
return yieldInst;
SILBasicBlock *getYieldingPred() {
assert(yieldState == Conflict);
return yieldingPred;
SILBasicBlock *getNonYieldingPred() {
assert(yieldState == Conflict);
return nonYieldingPred;
/// A structure that records an error found during the analysis along with
/// some context information that will be used by diagnostics.
struct YieldError {
/// The kind of error.
enum Kind { MultipleYield, ReturnBeforeYield, ReturnOnConflict } errorKind;
/// The termination instruction where the error should be reported.
SILInstruction *termInst;
/// The input state when the error is encountered.
BBState inState;
YieldError(Kind kind, SILInstruction *term, BBState state)
: errorKind(kind), termInst(term), inState(state) {}
static YieldError getMultipleYieldError(YieldInst *yield, BBState state) {
assert(state.yieldState != BBState::BeforeYield);
return YieldError(MultipleYield, yield, state);
static YieldError getReturnBeforeYieldError(ReturnInst *returnI,
BBState state) {
assert(state.yieldState == BBState::BeforeYield);
return YieldError(ReturnBeforeYield, returnI, state);
static YieldError getReturnOnConflict(ReturnInst *returnI, BBState state) {
assert(state.yieldState == BBState::Conflict);
return YieldError(ReturnOnConflict, returnI, state);
/// Transfer function of the data-flow analysis.
/// \param bb Basic block that should be processed
/// \param inState BBState at the start of the basic block
/// \param error out parameter that will contain information about
/// an error that is detected.
/// \return the state at the exit of the basic block if it can be computed
/// and None otherwise.
static Optional<BBState>
transferStateThroughBasicBlock(SILBasicBlock *bb, BBState inState,
Optional<YieldError> &error) {
error = None;
auto *term = bb->getTerminator();
if (auto *returnInst = dyn_cast<ReturnInst>(term)) {
if (inState.yieldState == BBState::BeforeYield) {
error = YieldError::getReturnBeforeYieldError(returnInst, inState);
return None;
if (inState.yieldState == BBState::Conflict) {
error = YieldError::getReturnOnConflict(returnInst, inState);
return None;
return inState;
if (auto *yieldInst = dyn_cast<YieldInst>(term)) {
if (inState.yieldState != BBState::BeforeYield) {
error = YieldError::getMultipleYieldError(yieldInst, inState);
return None;
// If the current state is BeforeYield and if the basic block ends in a
// yield the new state is AfterYield.
return inState.getAfterYieldState(term);
// We cannot have throws within generalized accessors.
return inState;
/// Merge operation of the data-flow analysis.
/// \param mergeBlock the basic block that is reached with two states
/// \param oldState the previous state at the entry of the basic block
/// \param newState the current state at the entry of the basic block
/// \param newStatePred the predecessor of 'mergeBlock' that has propagated
/// the 'newState'.
/// \param bbToStateMap a map from the basic blocks visited by the analysis
/// to the BBStates in which they were seen. This is used to identify
/// blocks that propagate conflicting states when the merge results
/// in a conflict.
/// \return the new state obtained by merging the oldState with the newState
static BBState merge(SILBasicBlock *mergeBlock, BBState oldState,
BBState newState, SILBasicBlock *newStatePred,
llvm::DenseMap<SILBasicBlock *, BBState> &bbToStateMap) {
auto oldYieldState = oldState.yieldState;
auto newYieldState = newState.yieldState;
if (oldYieldState == BBState::Conflict) {
return oldState;
if (newYieldState == BBState::Conflict) {
return newState;
if (oldYieldState == newYieldState) {
return oldState;
// Here, one state is AfterYield and the other one is BeforeYield.
// Merging them will result in Conflict.
assert((newYieldState == BBState::AfterYield &&
oldYieldState == BBState::BeforeYield) ||
(newYieldState == BBState::BeforeYield &&
oldYieldState == BBState::AfterYield));
// For diagnostics, find another predecessor of 'mergeBlock' that was
// previously seen by the analysis. This predecessor would have
// propagated the 'oldState'.
SILBasicBlock *oldStatePred = nullptr;
for (auto predBB : mergeBlock->getPredecessorBlocks()) {
if (predBB != newStatePred && bbToStateMap.count(predBB)) {
oldStatePred = predBB;
if (oldState.yieldState == BBState::BeforeYield) {
return BBState::getConflictState(newState.getYieldInstruction(),
/* yieldPred */ newStatePred,
/* noYieldPred */ oldStatePred);
} else {
return BBState::getConflictState(oldState.getYieldInstruction(),
/* yieldPred */ oldStatePred,
/* noYieldPred */ newStatePred);
/// Perform a data-flow analysis to check whether there is exactly one
/// yield before a return in every path in the control-flow graph.
/// Diagnostics are not reported for nodes unreachable from the entry of
/// the control-flow graph.
void diagnoseYieldOnceUsage(SILFunction &fun) {
llvm::DenseMap<SILBasicBlock *, BBState> bbToStateMap;
SmallVector<SILBasicBlock *, 16> worklist;
auto *entryBB = fun.getEntryBlock();
bbToStateMap.try_emplace(entryBB, BBState::getInitialState());
// ReturnBeforeYield errors, which denote that no paths yield before
// returning, are not diagnosed until the analysis completes, in order to
// distinguish them from ReturnOnConflict errors, which happen when some
// paths yield and some don't.
Optional<YieldError> returnBeforeYieldError = None;
// The algorithm uses a worklist to propagate the state through basic
// blocks until a fix point. Since the state lattice has height one, each
// basic block will be visited at most twice, and at most once if there are
// no conflicts (which are errors). The basic blocks are added to the
// worklist in a breadth-first fashion. The order of visiting basic blocks
// is not important for correctness, but it could change the errors
// diagnosed when there are multiple errors. Breadth-first order diagnoses
// errors along shorter paths to return.
while (!worklist.empty()) {
SILBasicBlock *bb = worklist.pop_back_val();
const BBState &state = bbToStateMap.find(bb)->getSecond();
Optional<YieldError> errorResult = None;
auto resultState = transferStateThroughBasicBlock(bb, state, errorResult);
if (!resultState.hasValue()) {
auto error = errorResult.getValue();
// ReturnBeforeYield errors will not be reported until the analysis
// completes. So record it and continue.
if (error.errorKind == YieldError::ReturnBeforeYield) {
if (!returnBeforeYieldError.hasValue()) {
returnBeforeYieldError = error;
emitDiagnostics(error, fun, bbToStateMap);
auto nextState = resultState.getValue();
for (auto *succBB : bb->getSuccessorBlocks()) {
// Optimistically try to set the state of the successor as next state.
auto insertResult = bbToStateMap.try_emplace(succBB, nextState);
// If the insertion was successful, it means we are seeing the successor
// for the first time. Add the successor to the worklist.
if (insertResult.second) {
worklist.insert(worklist.begin(), succBB);
// Here the successor already has a state. Merge the current and
// previous states and propagate it if it is different from the
// old state.
const auto &oldState = insertResult.first->second;
auto mergedState = merge(succBB, oldState, nextState, bb, bbToStateMap);
if (mergedState.yieldState == oldState.yieldState)
// Even though at this point there has to be an error since there is an
// inconsistency between states coming along two different paths,
// continue propagation of this conflict state to determine
// whether this results in multiple-yields error or return-on-conflict
// error.
insertResult.first->second = mergedState;
worklist.insert(worklist.begin(), succBB);
if (returnBeforeYieldError.hasValue()) {
emitDiagnostics(returnBeforeYieldError.getValue(), fun, bbToStateMap);
void emitDiagnostics(YieldError &error, SILFunction &fun,
llvm::DenseMap<SILBasicBlock *, BBState> &visitedBBs) {
ASTContext &astCtx = fun.getModule().getASTContext();
switch (error.errorKind) {
case YieldError::ReturnBeforeYield: {
diagnose(astCtx, error.termInst->getLoc().getSourceLoc(),
case YieldError::MultipleYield: {
diagnose(astCtx, error.termInst->getLoc().getSourceLoc(),
// Add a note that points to the previous yield.
case YieldError::ReturnOnConflict: {
// Emit an error on the return statement.
diagnose(astCtx, error.termInst->getLoc().getSourceLoc(),
// Here, the yield state of 'error' is Conflict.
auto &conflictState = error.inState;
// Emit a note that pin points the branch construct that resulted in
// this conflict. Note that a conflict state is created at a merge block
// when along one incoming edge the analysis sees a BeforeYield state
// and along another it sees an AfterYield state.
// Also note that, by the definition of the merge operation,
// 'error.yieldingPred()' is the immediate predecessor of the merge block
// that propagates AfterYield state, and 'error.nonYieldingPred()' is
// the immediate predecessor of the merge block that propagates a
// BeforeYield state.
auto yieldPred = conflictState.getYieldingPred();
auto noYieldPred = conflictState.getNonYieldingPred();
// Step 1: find a branching SIL instruction where one branch has
// 'yieldPred' and another branch has 'noYieldPred'. For instance,
// in the following example, cond_br is the instruction to find.
// cond_br bb1, bb2
// bb1:
// yield resume yieldPred, unwind err
// bb2:
// br noYieldPred
// yieldPred:
// br mergePoint
// noYieldPred:
// br mergePoint
// mergePoint:
// ...
// Intuitively, the conflicting branch is the instruction where
// 'yieldPred' and 'noYieldPred' meet when traversing the CFG in the
// reverse order. More formally, the branching instruction is a
// "lowest common ancestor" of 'yieldPred' and 'noYieldPred' in the
// the DAG obtained from the CFG by ignoring back edges of loops.
// Note that the lowest common ancestor may not be unique in a DAG.
// But, any such ancestor could be considered as the conflicting branch as
// 'yieldPred' and 'noYieldPred' will belong to two different branches of
// every such ancestor.
// Find all transitive predecessors of 'yieldPred' that were visited
// during the analysis
SmallPtrSet<SILBasicBlock *, 8> predecessorsOfYieldPred;
for (auto *predBB :
llvm::breadth_first<llvm::Inverse<SILBasicBlock *>>(yieldPred)) {
if (visitedBBs.count(predBB)) {
// Find the first predecessor of 'noYieldPred' that is also a predecessor
// of 'yieldPred', in the breadth-first search order of the reversed CFG.
SILBasicBlock *lowestCommonAncestorBB = nullptr;
SmallPtrSet<SILBasicBlock *, 8> predecessorsOfNoYieldPred;
for (auto *pred :
llvm::breadth_first<llvm::Inverse<SILBasicBlock *>>(noYieldPred)) {
if (!visitedBBs.count(pred)) {
if (predecessorsOfYieldPred.count(pred)) {
lowestCommonAncestorBB = pred;
auto *conflictingBranch = lowestCommonAncestorBB->getTerminator();
// Step 2: Find the target basic block of the 'conflictingBranch' that
// doesn't yield.
SILBasicBlock *noYieldTarget = nullptr;
for (auto *succ : lowestCommonAncestorBB->getSuccessorBlocks()) {
if (predecessorsOfNoYieldPred.count(succ)) {
noYieldTarget = succ;
// Step 3: Report specialized diagnostics for each kind of conflicting
// branch.
// For conditional-branch instructions, which correspond to the
// conditions of 'if', 'where' or 'guard' statements, report for what
// truth value the branch doesn't yield.
if (auto *condbr = dyn_cast<CondBranchInst>(conflictingBranch)) {
diagnose(astCtx, condbr->getLoc().getSourceLoc(),
/*non-yielding branch*/ condbr->getTrueBB() == noYieldTarget);
// For switch_enum instructions, report the case that doesn't yield.
enum SwitchCaseKind { Default, OptionNil, OptionSome };
if (auto switchEnum = SwitchEnumTermInst(conflictingBranch)) {
auto enumCaseLoc = noYieldTarget->begin()->getLoc().getSourceLoc();
if (switchEnum.hasDefault() &&
switchEnum.getDefaultBB() == noYieldTarget) {
diagnose(astCtx, enumCaseLoc, diag::case_doesnt_yield, Default);
// Find the case identifier that doesn't yield.
NullablePtr<EnumElementDecl> enumElemDecl =
// Specialize diagnostics for cases of an optional.
if (enumElemDecl.get() == astCtx.getOptionalNoneDecl()) {
diagnose(astCtx, enumCaseLoc, diag::case_doesnt_yield, OptionNil);
} else if (enumElemDecl.get() == astCtx.getOptionalSomeDecl()) {
diagnose(astCtx, enumCaseLoc, diag::case_doesnt_yield, OptionSome);
} else {
diagnose(astCtx, enumCaseLoc, diag::named_case_doesnt_yield,
// For switch_value instructions, report the case number that doesn't
// yield.
if (auto *switchValue = dyn_cast<SwitchValueInst>(conflictingBranch)) {
auto enumCaseLoc = noYieldTarget->begin()->getLoc().getSourceLoc();
if (switchValue->hasDefault() &&
switchValue->getDefaultBB() == noYieldTarget) {
diagnose(astCtx, enumCaseLoc, diag::case_doesnt_yield, Default);
// Find the case that doesn't yield.
Optional<unsigned> caseNumberOpt =
auto caseNumber = caseNumberOpt.getValue();
astCtx, enumCaseLoc, diag::switch_value_case_doesnt_yield,
(Twine(caseNumber) + llvm::getOrdinalSuffix(caseNumber)).str());
// For try-apply instructions, report whether throwing or non-throwing
// case doesn't yield.
if (auto *tryApply = dyn_cast<TryApplyInst>(conflictingBranch)) {
diagnose(astCtx, tryApply->getLoc().getSourceLoc(),
/*does error case not yield?*/ tryApply->getErrorBB() ==
llvm_unreachable("unexpected branch resulting in conflicting yield "
"states found in generalized accessor");
/// The entry point to the transformation.
void run() override {
auto *fun = getFunction();
if (fun->getLoweredFunctionType()->getCoroutineKind() !=
} // end anonymous namespace
SILTransform *swift::createYieldOnceCheck() {
return new YieldOnceCheck();