blob: 94dbda3909adcdbf93741c15e24930a92c0dab40 [file] [log] [blame]
//===--- OwnedToGuaranteedPhiOpt.cpp --------------------------------------===//
// This source file is part of the open source project
// Copyright (c) 2014 - 2020 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
/// \file
/// Late optimization that eliminates webs of owned phi nodes.
#include "Context.h"
#include "OwnershipPhiOperand.h"
#include "Transforms.h"
#include "swift/Basic/STLExtras.h"
using namespace swift;
using namespace swift::semanticarc;
namespace {
using ConsumingOperandState = Context::ConsumingOperandState;
} // anonymous namespace
template <typename OperandRangeTy>
static bool canEliminatePhi(
OperandRangeTy optimizableIntroducerRange,
ArrayRef<OwnershipPhiOperand> incomingValueOperandList,
SmallVectorImpl<OwnedValueIntroducer> &ownedValueIntroducerAccumulator) {
for (auto incomingValueOperand : incomingValueOperandList) {
SILValue incomingValue = incomingValueOperand.getValue();
// Before we do anything, see if we have an incoming value with trivial
// ownership. This can occur in the case where we are working with enums due
// to trivial non-payloaded cases. Skip that.
if (incomingValue.getOwnershipKind() == OwnershipKind::None) {
// Then see if this is an introducer that we actually saw as able to be
// optimized if we could flip this joined live range.
// NOTE: If this linear search is too slow, we can change the multimap to
// sort the mapped to list by pointer instead of insertion order. In such a
// case, we could then bisect.
if (llvm::find(optimizableIntroducerRange,
incomingValueOperand.getOperand()) ==
optimizableIntroducerRange.end()) {
return false;
// Now that we know it is an owned value that we saw before, check for
// introducers of the owned value which are the copies that we may be able
// to eliminate. Since we do not look through joined live ranges, we must
// only have a single introducer. So look for that one and if not, bail.
auto singleIntroducer = getSingleOwnedValueIntroducer(incomingValue);
if (!singleIntroducer.hasValue()) {
return false;
// Then make sure that our owned value introducer is able to be converted to
// guaranteed and that we found it to have a LiveRange that we could have
// eliminated /if/ we were to get rid of this phi.
if (!singleIntroducer->isConvertableToGuaranteed()) {
return false;
// Otherwise, add the introducer to our result array.
#ifndef NDEBUG
// Other parts of the pass ensure that we only add values to the list if their
// owned value introducer is not used by multiple live ranges. That being
// said, lets assert that.
SmallVector<OwnedValueIntroducer, 32> uniqueCheck;
uniqueCheck.size() == ownedValueIntroducerAccumulator.size() &&
"multiple joined live range operands are from the same live range?!");
return true;
static bool getIncomingJoinedLiveRangeOperands(
SILValue joinedLiveRange,
SmallVectorImpl<OwnershipPhiOperand> &resultingOperands) {
if (auto *phi = dyn_cast<SILPhiArgument>(joinedLiveRange)) {
return phi->visitIncomingPhiOperands([&](Operand *op) {
if (auto phiOp = OwnershipPhiOperand::get(op)) {
return true;
return false;
if (auto *svi = dyn_cast<SingleValueInstruction>(joinedLiveRange)) {
return llvm::all_of(svi->getAllOperands(), [&](const Operand &op) {
// skip type dependent operands.
if (op.isTypeDependent())
return true;
auto phiOp = OwnershipPhiOperand::get(&op);
if (!phiOp)
return false;
return true;
llvm_unreachable("Unhandled joined live range?!");
// Top Level Entrypoint
bool swift::semanticarc::tryConvertOwnedPhisToGuaranteedPhis(Context &ctx) {
bool madeChange = false;
// First freeze our multi-map so we can use it for map queries. Also, setup a
// defer of the reset so we do not forget to reset the map when we are done.
SWIFT_DEFER { ctx.joinedOwnedIntroducerToConsumedOperands.reset(); };
// Now for each phi argument that we have in our multi-map...
SmallVector<OwnershipPhiOperand, 4> incomingValueOperandList;
SmallVector<OwnedValueIntroducer, 4> ownedValueIntroducers;
for (auto pair : ctx.joinedOwnedIntroducerToConsumedOperands.getRange()) {
// First compute the LiveRange for ownershipPhi value. For simplicity, we
// only handle cases now where the result does not have any additional
// ownershipPhi uses.
SILValue joinedIntroducer = pair.first;
OwnershipLiveRange joinedLiveRange(joinedIntroducer);
if (bool(joinedLiveRange.hasUnknownConsumingUse())) {
// Ok, we know that our phi argument /could/ be converted to guaranteed if
// our incoming values are able to be converted to guaranteed. Now for each
// incoming value, compute the incoming values ownership roots and see if
// all of the ownership roots are in our owned incoming value array.
if (!getIncomingJoinedLiveRangeOperands(joinedIntroducer,
incomingValueOperandList)) {
// Grab our list of introducer values paired with this SILArgument. See if
// all of these introducer values were ones that /could/ have been
// eliminated if it was not for the given phi. If all of them are, we can
// optimize!
std::function<Operand *(const Context::ConsumingOperandState)> lambda =
[&](const Context::ConsumingOperandState &state) -> Operand * {
unsigned opNum = state.operandNumber;
if (<SILBasicBlock *>()) {
SILBasicBlock *block = state.parent.get<SILBasicBlock *>();
return &block->getTerminator()->getAllOperands()[opNum];
SILInstruction *inst = state.parent.get<SILInstruction *>();
return &inst->getAllOperands()[opNum];
auto operandsTransformed = makeTransformRange(pair.second, lambda);
if (!canEliminatePhi(operandsTransformed, incomingValueOperandList,
ownedValueIntroducers)) {
// Ok, at this point we know that we can eliminate this phi. First go
// through the list of incomingValueOperandList and stash the value/set the
// operand's stored value to undef. We will hook them back up later.
SmallVector<SILValue, 8> originalIncomingValues;
for (auto &incomingValueOperand : incomingValueOperandList) {
// Then go through all of our owned value introducers, compute their live
// ranges, and eliminate them. We know it is safe to remove them from our
// previous proofs.
// NOTE: If our introducer is a copy_value that is one of our
// originalIncomingValues, we need to update the originalIncomingValue array
// with that value since we are going to delete the copy_value here. This
// creates a complication since we want to binary_search on
// originalIncomingValues to detect this same condition! So, we create a
// list of updates that we apply after we no longer need to perform
// binary_search, but before we start RAUWing things.
SmallVector<std::pair<SILValue, unsigned>, 8> incomingValueUpdates;
for (auto introducer : ownedValueIntroducers) {
SILValue v = introducer.value;
OwnershipLiveRange lr(v);
// For now, we only handle copy_value for simplicity.
// TODO: Add support for load [copy].
if (introducer.kind == OwnedValueIntroducerKind::Copy) {
auto *cvi = cast<CopyValueInst>(v);
// Before we convert from owned to guaranteed, we need to first see if
// cvi is one of our originalIncomingValues. If so, we need to set
// originalIncomingValues to be cvi->getOperand(). Otherwise, weirdness
// results since we are deleting one of our stashed values.
auto iter = find(originalIncomingValues, cvi);
if (iter != originalIncomingValues.end()) {
// We use an auxillary array here so we can continue to bisect on
// original incoming values. Once we are done processing here, we will
// not need that property anymore.
unsigned updateOffset =
std::distance(originalIncomingValues.begin(), iter);
incomingValueUpdates.emplace_back(cvi->getOperand(), updateOffset);
llvm_unreachable("Unhandled optimizable introducer!");
// Now go through and update our original incoming value array now that we
// do not need it to be sorted for bisection purposes.
while (!incomingValueUpdates.empty()) {
auto pair = incomingValueUpdates.pop_back_val();
originalIncomingValues[pair.second] = pair.first;
// Then convert the phi's live range to be guaranteed.
ctx.getDeadEndBlocks(), ctx.lifetimeFrontier, ctx.instModCallbacks);
// Now if our phi operand consumes/forwards its guaranteed input, insert a
// begin_borrow along the incoming value edges. We have to do this after
// converting the incoming values to be guaranteed to avoid tripping
// SILBuilder checks around simple ownership invariants (namely that def/use
// line up) when creating instructions.
assert(incomingValueOperandList.size() == originalIncomingValues.size());
while (!incomingValueOperandList.empty()) {
auto incomingValueOperand = incomingValueOperandList.pop_back_val();
SILValue originalValue = originalIncomingValues.pop_back_val();
if (incomingValueOperand.isGuaranteedConsuming() &&
originalValue.getOwnershipKind() != OwnershipKind::None) {
auto loc = RegularLocation::getAutoGeneratedLocation();
SILBuilderWithScope builder(incomingValueOperand.getInst());
originalValue = builder.createBeginBorrow(loc, originalValue);
madeChange = true;
return madeChange;