ScopedAddressUtils.cpp

//===--- ScopedAddressUtils.cpp -------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "swift/SIL/ScopedAddressUtils.h"
#include "swift/SIL/OwnershipUtils.h"
#include "swift/SIL/PrunedLiveness.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SILOptimizer/Utils/InstructionDeleter.h"
#include "swift/SILOptimizer/Utils/OwnershipOptUtils.h"

using namespace swift;

void ScopedAddressValueKind::print(llvm::raw_ostream &os) const {
  switch (value) {
  case ScopedAddressValueKind::Invalid:
    llvm_unreachable("Using invalid case?!");
  case ScopedAddressValueKind::StoreBorrow:
    os << "StoreBorrow";
    return;
  case ScopedAddressValueKind::BeginAccess:
    os << "BeginAccess";
    return;
  }
  llvm_unreachable("Covered switch isn't covered?!");
}

llvm::raw_ostream &swift::operator<<(llvm::raw_ostream &os,
                                     ScopedAddressValueKind kind) {
  kind.print(os);
  return os;
}

bool ScopedAddressValue::isScopeEndingUse(Operand *op) const {
  switch (kind) {
  case ScopedAddressValueKind::Invalid:
    llvm_unreachable("Using invalid case?!");
  case ScopedAddressValueKind::StoreBorrow: {
    if (auto *endBorrow = dyn_cast<EndBorrowInst>(op->getUser())) {
      return endBorrow->getOperand() == value;
    }
    return false;
  }
  case ScopedAddressValueKind::BeginAccess: {
    if (auto *endAccess = dyn_cast<EndAccessInst>(op->getUser())) {
      return endAccess->getOperand() == value;
    }
    return false;
  }
  }
}

bool ScopedAddressValue::visitScopeEndingUses(
    function_ref<bool(Operand *)> visitor) const {
  switch (kind) {
  case ScopedAddressValueKind::Invalid:
    llvm_unreachable("Using invalid case?!");
  case ScopedAddressValueKind::StoreBorrow: {
    for (auto *use : value->getUses()) {
      if (isa<EndBorrowInst>(use->getUser())) {
        if (!visitor(use))
          return false;
      }
    }
    return true;
  }
  case ScopedAddressValueKind::BeginAccess: {
    for (auto *use : value->getUses()) {
      if (isa<EndAccessInst>(use->getUser())) {
        if (!visitor(use))
          return false;
      }
    }
    return true;
  }
  }
}

// Note: This is used to fixup an incomplete address scope, so cannot assume the
// scope's lifetime is already complete. Therefore, it needs to transitively
// process all address uses.
//
// FIXME: this should use the standard recursive lifetime completion
// utility. Otherwise dealing with nested incomplete lifetimes becomes expensive
// and complex. e.g.
//
//   %storeBorrow = store_borrow %_ to %adr
//   %loadBorrow  = load_borrow %storeBorrow
//   apply %f(%loadBorrow) : $@convention(thin) (...) -> Never
//   unreachable
//
AddressUseKind ScopedAddressValue::
computeLiveness(SSAPrunedLiveness &liveness) const {
  SmallVector<Operand *, 4> uses;
  // Collect all uses that need to be enclosed by the scope.
  auto addressKind = findTransitiveUsesForAddress(value, &uses);

  liveness.initializeDef(value);
  for (auto *use : uses) {
    // Update all collected uses as non-lifetime ending.
    liveness.updateForUse(use->getUser(), /* lifetimeEnding */ false);
  }
  visitScopeEndingUses([&](Operand *endOp) {
    liveness.updateForUse(endOp->getUser(), /* isLifetimeEnding */ true);
    return true;
  });
  return addressKind;
}

void ScopedAddressValue::createScopeEnd(SILBasicBlock::iterator insertPt,
                                        SILLocation loc) const {
  switch (kind) {
  case ScopedAddressValueKind::StoreBorrow: {
    SILBuilderWithScope(insertPt).createEndBorrow(loc, value);
    return;
  }
  case ScopedAddressValueKind::BeginAccess: {
    SILBuilderWithScope(insertPt).createEndAccess(loc, value, false);
    return;
  }
  case ScopedAddressValueKind::Invalid:
    llvm_unreachable("Using invalid case?!");
  }
}

void ScopedAddressValue::endScopeAtLivenessBoundary(
    SSAPrunedLiveness *liveness) const {
  // If no users exist, create scope ending instruction immediately after the
  // scoped address value.
  if (liveness->empty()) {
    createScopeEnd(value->getNextInstruction()->getIterator(),
                   RegularLocation::getAutoGeneratedLocation());
    return;
  }

  PrunedLivenessBoundary scopedAddressBoundary;
  liveness->computeBoundary(scopedAddressBoundary);
  // Go over the boundary and create scope ending instructions.
  scopedAddressBoundary.visitInsertionPoints(
      [&](SILBasicBlock::iterator insertPt) {
        createScopeEnd(insertPt, RegularLocation::getAutoGeneratedLocation());
      });
}

bool swift::hasOtherStoreBorrowsInLifetime(StoreBorrowInst *storeBorrow,
                                           SSAPrunedLiveness *liveness,
                                           DeadEndBlocks *deadEndBlocks) {
  SmallVector<StoreBorrowInst *, 4> otherStoreBorrows;
  // Collect all other store_borrows to the destination of \p storeBorrow
  for (auto *destUse : storeBorrow->getDest()->getUses()) {
    if (auto *user = dyn_cast<StoreBorrowInst>(destUse->getUser())) {
      if (user == storeBorrow) {
        continue;
      }
      otherStoreBorrows.push_back(user);
    }
  }

  for (auto *otherStoreBorrow : otherStoreBorrows) {
    // Return true, if otherStoreBorrow was in \p storeBorrow's scope
    if (liveness->isWithinBoundary(otherStoreBorrow)) {
      return true;
    }
  }
  return false;
}

bool swift::extendStoreBorrow(StoreBorrowInst *sbi,
                              SmallVectorImpl<Operand *> &newUses,
                              DeadEndBlocks *deadEndBlocks,
                              InstModCallbacks callbacks) {
  ScopedAddressValue scopedAddress(sbi);

  SmallVector<SILBasicBlock *, 4> discoveredBlocks;
  SSAPrunedLiveness storeBorrowLiveness(&discoveredBlocks);
  
  AddressUseKind useKind = scopedAddress.computeLiveness(storeBorrowLiveness);

  // If all new uses are within store_borrow boundary, no need for extension.
  if (storeBorrowLiveness.areUsesWithinBoundary(newUses, deadEndBlocks)) {
    return true;
  }

  if (useKind != AddressUseKind::NonEscaping) {
    return false;
  }

  // store_borrow extension is possible only when there are no other
  // store_borrows to the same destination within the store_borrow's lifetime
  // built from newUsers.
  if (hasOtherStoreBorrowsInLifetime(sbi, &storeBorrowLiveness,
                                     deadEndBlocks)) {
    return false;
  }

  InstModCallbacks tempCallbacks = callbacks;
  InstructionDeleter deleter(std::move(tempCallbacks));
  GuaranteedOwnershipExtension borrowExtension(deleter, *deadEndBlocks,
                                               sbi->getFunction());
  auto status = borrowExtension.checkBorrowExtension(
      BorrowedValue(sbi->getSrc()), newUses);
  if (status == GuaranteedOwnershipExtension::Invalid) {
    return false;
  }

  borrowExtension.transform(status);

  SmallVector<Operand *, 4> endBorrowUses;
  // Collect old scope-ending instructions.
  scopedAddress.visitScopeEndingUses([&](Operand *op) {
    endBorrowUses.push_back(op);
    return true;
  });

  for (auto *use : newUses) {
    // Update newUsers as non-lifetime ending.
    storeBorrowLiveness.updateForUse(use->getUser(),
                                     /* lifetimeEnding */ false);
  }

  // Add new scope-ending instructions.
  scopedAddress.endScopeAtLivenessBoundary(&storeBorrowLiveness);

  // Remove old scope-ending instructions.
  for (auto *endBorrowUse : endBorrowUses) {
    callbacks.deleteInst(endBorrowUse->getUser());
  }

  return true;
}

void ScopedAddressValue::print(llvm::raw_ostream &os) const {
  os << "ScopedAddressIntroducingValue:\n"
        "Kind: "
     << kind
     << "\n"
        "Value: "
     << value;
}

llvm::raw_ostream &swift::operator<<(llvm::raw_ostream &os,
                                     const ScopedAddressValue &value) {
  value.print(os);
  return os;
}