CanonicalOSSALifetime.cpp

//===--- CanonicalOSSALifetime.cpp - Canonicalize OSSA value lifetimes ----===//
//
// This source file is part of the Swift.org 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 https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// This top-level API rewrites the extended lifetime of a SILValue:
///
///     bool CanonicalizeOSSALifetime::canonicalizeValueLifetime(SILValue def)
///
/// Each time it's called on a single OSSA value, `def`, it performs three
/// steps:
///
/// 1. Compute "pruned" liveness of def and its copies, ignoring original
///    destroys. Initializes `liveness`.
///
/// 2. Find `def`s final destroy points based on its pruned
///    liveness. Initializes `consumes` and inserts new destroy_value
///    instructions.
///
/// 3. Rewrite `def`s original copies and destroys, inserting new copies where
///    needed. Deletes original copies and destroys and inserts new copies.
///
/// See CanonicalOSSALifetime.h for examples.
///
/// TODO: Enable canonical-ossa-rewrite-borrows to rewrite single-block borrows.
/// Add support for multi-block borrows, load_borrow, and phi by using
/// persistentCopies.
///
/// TODO: If all client passes can maintain block numbers, then the
/// SmallDenseMaps/SetVectors can be replaced with bitsets/sparsesets.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "copy-propagation"

#include "swift/SILOptimizer/Utils/CanonicalOSSALifetime.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/OwnershipUtils.h"
#include "swift/SILOptimizer/Utils/CFGOptUtils.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "swift/SILOptimizer/Utils/ValueLifetime.h"
#include "llvm/ADT/Statistic.h"

using namespace swift;
using llvm::SmallSetVector;

STATISTIC(NumCopiesEliminated, "number of copy_value instructions removed");
STATISTIC(NumDestroysEliminated,
          "number of destroy_value instructions removed");
STATISTIC(NumCopiesGenerated, "number of copy_value instructions created");
STATISTIC(NumDestroysGenerated, "number of destroy_value instructions created");
STATISTIC(NumUnknownUsers, "number of functions with unknown users");

/// This use-def walk must be consistent with the def-use walks performed
/// within the canonicalizeValueLifetime() implementation.
SILValue CanonicalizeOSSALifetime::getCanonicalCopiedDef(SILValue v) {
  while (auto *copy = dyn_cast<CopyValueInst>(v)) {
    auto def = copy->getOperand();
    if (def.getOwnershipKind() == OwnershipKind::Owned) {
      v = def;
      continue;
    }
    if (auto borrowedVal = BorrowedValue(def)) {
      // Any def's that aren't filtered out here must be handled by
      // computeBorrowLiveness.
      switch (borrowedVal.kind) {
      case BorrowedValueKind::Invalid:
        llvm_unreachable("Using invalid case?!");
      case BorrowedValueKind::SILFunctionArgument:
        return def;
      case BorrowedValueKind::BeginBorrow: {
        // TODO: Remove this call to visitLocalScopeEndingUses and the
        // same-block check once computeBorrowLiveness supports multiple blocks.
        auto *defBB = def->getParentBlock();
        if (borrowedVal.visitLocalScopeEndingUses(
              [&](Operand *endBorrow) {
                return endBorrow->getUser()->getParent() == defBB;
              })) {
          return def;
        }
        break;
      }
      case BorrowedValueKind::LoadBorrow:
      case BorrowedValueKind::Phi:
        break;
      }
    }
    // This guaranteed value cannot be handled, treat the copy as an owned
    // live range def instead.
    return copy;
  }
  return v;
}

/// The lifetime extends beyond given consuming use. Copy the value.
///
/// This can set the operand value, but cannot invalidate the use iterator.
static void copyLiveUse(Operand *use) {
  SILInstruction *user = use->getUser();
  SILBuilderWithScope B(user->getIterator());

  auto loc = RegularLocation::getAutoGeneratedLocation(user->getLoc());
  auto *copy = B.createCopyValue(loc, use->get());
  use->set(copy);

  ++NumCopiesGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Copying at last use " << *copy);
}

//===----------------------------------------------------------------------===//
//                        MARK: Rewrite borrow scopes
//===----------------------------------------------------------------------===//

llvm::cl::opt<bool>
    EnableRewriteBorrows("canonical-ossa-rewrite-borrows", llvm::cl::init(false),
                         llvm::cl::desc("Enable rewriting borrow scopes"));

bool CanonicalizeOSSALifetime::computeBorrowLiveness() {
  auto borrowedVal = BorrowedValue(currentDef);
  if (!borrowedVal) {
    return false;
  }
  switch (borrowedVal.kind) {
  case BorrowedValueKind::Invalid:
    llvm_unreachable("Used invalid");
  case BorrowedValueKind::SILFunctionArgument:
    // For efficiency, function arguments skip liveness.
    return true;
  case BorrowedValueKind::LoadBorrow:
  case BorrowedValueKind::Phi:
    // TODO: Canonicalize load_borrow scope and phi once consolidateBorrowScope
    // can handle persistentCopies.
    return false;
  case BorrowedValueKind::BeginBorrow:
    break;
  }
  if (!EnableRewriteBorrows) {
    return false;
  }
  // Note that there is no need to look through any reborrows. The reborrowed
  // value is considered a separate lifetime for canonicalization. Any copies of
  // the reborrowed value will not be rewritten when canonicalizing the current
  // borrow scope because they are "hidden" behind the reborrow.
  borrowedVal.visitLocalScopeEndingUses([this](Operand *use) {
    liveness.updateForUse(use->getUser(), /*lifetimeEnding*/ true);
    return true;
  });

  // TODO: Fix getCanonicalCopiedDef to allow multi-block borrows and remove
  // this assert. This should only be done once consolidateBorrowScope can
  // handle persistentCopies, otherwise we may end up generating more dynamic
  // copies than the non-canonical form.
  assert(liveness.numLiveBlocks() == 1);
  return true;
}

// Create a copy for outer uses of the borrow scope introduced by
// currentDef. This copy should only be used by outer uses in the same block
// as the borrow scope.
//
// To use an existing outer copy, we could find its earliest consume. But the
// new copy will immediately canonicalized and a canonical begin_borrow scope
// have no outside uses of its first block.
static CopyValueInst *createOuterCopy(BeginBorrowInst *beginBorrow) {
  SILBuilderWithScope B(beginBorrow);

  auto loc = RegularLocation::getAutoGeneratedLocation(beginBorrow->getLoc());
  auto *copy = B.createCopyValue(loc, beginBorrow->getOperand());

  ++NumCopiesGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Outer copy " << *copy);

  return copy;
}

// If this succeeds, then all uses of the borrowed value outside the borrow
// scope will be rewritten to use an outer copy, and all remaining uses of the
// borrowed value will be confined to the borrow scope.
//
// TODO: Canonicalize multi-block borrow scopes, load_borrow scope, and phi
// borrow scopes by adding one copy per block to persistentCopies for
// each block that dominates an outer use.
bool CanonicalizeOSSALifetime::consolidateBorrowScope() {
  if (isa<SILFunctionArgument>(currentDef)) {
    return true;
  }
  // Gather all outer uses before rewriting any to avoid scanning any basic
  // block more than once.
  SmallVector<Operand *, 8> outerUses;
  llvm::SmallPtrSet<SILInstruction *, 8> outerUseInsts;
  auto isUserInLiveOutBlock = [&](SILInstruction *user) {
    // TODO: enable isUserInLiveOutBlock once we support multi-block borrows
    // return (liveness.getBlockLiveness(user->getParent())
    //        == PrunedLiveBlocks::LiveOut);
    return false;
  };
  auto recordOuterUse = [&](Operand *use) {
    // If the user's block is LiveOut, then it is definitely within the borrow
    // scope, so there's no need to record it.
    if (isUserInLiveOutBlock(use->getUser())) {
      return;
    }
    outerUses.push_back(use);
    outerUseInsts.insert(use->getUser());
  };
  // getCanonicalCopiedDef ensures that if currentDef is a guaranteed value,
  // then it is a borrow scope introducer.
  assert(BorrowedValue(currentDef).isLocalScope());

  // This def-use traversal is similar to
  // findExtendedTransitiveGuaranteedUses(), however, to cover the canonical
  // lifetime, it looks through copies. It also considered uses within the
  // introduced borrow scope itself (instead of simply visiting the scope-ending
  // uses). It does not, however, look into nested borrow scopes uses, since
  // nested scopes are canonicalized independently.
  defUseWorklist.clear();
  defUseWorklist.insert(currentDef);
  while (!defUseWorklist.empty()) {
    SILValue value = defUseWorklist.pop_back_val();
    for (Operand *use : value->getUses()) {
      auto *user = use->getUser();
      // Recurse through copies.
      if (auto *copy = dyn_cast<CopyValueInst>(user)) {
        defUseWorklist.insert(copy);
        continue;
      }
      // Note: debug_value uses are handled like normal uses here. They should
      // be stripped later if required when handling outerCopy or
      // persistentCopies.

      switch (use->getOperandOwnership()) {
      case OperandOwnership::NonUse:
        break;
      case OperandOwnership::TrivialUse:
        llvm_unreachable("this operand cannot handle ownership");

      case OperandOwnership::InteriorPointer:
      case OperandOwnership::ForwardingBorrow:
      case OperandOwnership::EndBorrow:
      case OperandOwnership::Reborrow:
        // Ignore uses that must be within the borrow scope.
        // Rewriting does not look through reborrowed values--it considers them
        // part of a separate lifetime.
        break;

      case OperandOwnership::ForwardingUnowned:
      case OperandOwnership::PointerEscape:
        // Pointer escapes are only allowed if they use the guaranteed value,
        // which means that the escaped value must be confied to the current
        // borrow scope.
        if (use->get().getOwnershipKind() != OwnershipKind::Guaranteed)
          return false;
        break;

      case OperandOwnership::InstantaneousUse:
      case OperandOwnership::UnownedInstantaneousUse:
      case OperandOwnership::BitwiseEscape:
      case OperandOwnership::ForwardingConsume:
      case OperandOwnership::DestroyingConsume:
        recordOuterUse(use);
        break;
      case OperandOwnership::Borrow:
        BorrowingOperand borrowOper(use);
        assert(borrowOper && "BorrowingOperand must handle OperandOwnership");
        recordOuterUse(use);
        // For borrows, record the scope-ending instructions in addition to the
        // borrow instruction outer use points. The logic below to check whether
        // a borrow scope is an outer use must visit the same set of uses.
        borrowOper.visitExtendedScopeEndingUses([&](Operand *endBorrow) {
          if (!isUserInLiveOutBlock(endBorrow->getUser())) {
            outerUseInsts.insert(endBorrow->getUser());
          }
          return true;
        });
        break;
      }
    } // end switch OperandOwnership
  } // end def-use traversal

  auto *beginBorrow = cast<BeginBorrowInst>(currentDef);
  SmallVector<SILInstruction *, 1> scopeEndingInst;
  BorrowedValue(beginBorrow).getLocalScopeEndingInstructions(scopeEndingInst);
  assert(scopeEndingInst.size() == 1 && "expected single-block borrow");
  // Remove outer uses that occur before the end of the borrow scope by
  // forward iterating from begin_borrow to end_borrow.
  for (auto instIter = beginBorrow->getIterator(),
            endIter = scopeEndingInst[0]->getIterator();
       instIter != endIter; ++instIter) {
    outerUseInsts.erase(&*instIter);
  }
  if (outerUseInsts.empty()) {
    return true;
  }
  // Rewrite the outer uses and record lifetime-ending uses.
  SmallVector<Operand *, 4> consumingUses;
  SmallPtrSet<SILInstruction *, 4> unclaimedConsumingUsers;
  this->outerCopy = createOuterCopy(beginBorrow);
  for (Operand *use : outerUses) {
    if (!outerUseInsts.count(use->getUser())) {
      // The immediate use is within this borrow scope.
      BorrowingOperand borrowOper(use);
      if (borrowOper.kind == BorrowingOperandKind::Invalid) {
        continue;
      }
      // For sub-borrows also check that the scope-ending instructions are
      // within the scope.
      if (borrowOper.visitExtendedScopeEndingUses([&](Operand *endBorrow) {
            return !outerUseInsts.count(endBorrow->getUser());
          })) {
        continue;
      }
    }
    LLVM_DEBUG(llvm::dbgs() << "  Use of outer copy " << *use->getUser());
    use->set(outerCopy);
    if (use->isLifetimeEnding()) {
      consumingUses.push_back(use);
      unclaimedConsumingUsers.insert(use->getUser());
    }
  }
  // Insert a destroy on the outer copy's lifetime frontier, or claim an
  // existing consume.
  ValueLifetimeAnalysis lifetimeAnalysis(outerCopy, outerUseInsts);
  ValueLifetimeAnalysis::Frontier frontier;
  bool result = lifetimeAnalysis.computeFrontier(
      frontier, ValueLifetimeAnalysis::DontModifyCFG, deBlocks);
  assert(result);
  while (!frontier.empty()) {
    auto *insertPt = frontier.pop_back_val();
    if (unclaimedConsumingUsers.erase(&*std::prev(insertPt->getIterator()))) {
      continue;
    }
    SILBuilderWithScope(insertPt).createDestroyValue(insertPt->getLoc(),
                                                     outerCopy);
  }
  // Add copies for consuming users of outerCopy.
  for (auto *use : consumingUses) {
    // If the user is still in the unclaimedConsumingUsers set, then it does not
    // end the outer copy's lifetime and therefore requires a copy. Only one
    // operand can be claimed as ending the lifetime, so return its user to the
    // unclaimedConsumingUsers set after skipping the first copy.
    auto iterAndInserted = unclaimedConsumingUsers.insert(use->getUser());
    if (!iterAndInserted.second) {
      copyLiveUse(use);
    }
  }
  return true;
}

//===----------------------------------------------------------------------===//
//                    MARK: Step 1. Compute pruned liveness
//===----------------------------------------------------------------------===//

bool CanonicalizeOSSALifetime::computeCanonicalLiveness() {
  defUseWorklist.clear();
  defUseWorklist.insert(currentDef);
  while (!defUseWorklist.empty()) {
    SILValue value = defUseWorklist.pop_back_val();
    for (Operand *use : value->getUses()) {
      auto *user = use->getUser();

      // Recurse through copies.
      if (auto *copy = dyn_cast<CopyValueInst>(user)) {
        defUseWorklist.insert(copy);
        continue;
      }
      // Handle debug_value instructions separately.
      if (pruneDebugMode) {
        if (auto *dvi = dyn_cast<DebugValueInst>(user)) {
          // Only instructions potentially outside current pruned liveness are
          // interesting.
          if (liveness.getBlockLiveness(dvi->getParent())
              != PrunedLiveBlocks::LiveOut) {
            recordDebugValue(dvi);
          }
          continue;
        }
      }
      switch (use->getOperandOwnership()) {
      case OperandOwnership::NonUse:
        break;
      case OperandOwnership::TrivialUse:
        llvm_unreachable("this operand cannot handle ownership");

      // Conservatively treat a conversion to an unowned value as a pointer
      // escape. Is it legal to canonicalize ForwardingUnowned?
      case OperandOwnership::ForwardingUnowned:
      case OperandOwnership::PointerEscape:
        return false;
      case OperandOwnership::InstantaneousUse:
      case OperandOwnership::UnownedInstantaneousUse:
      case OperandOwnership::BitwiseEscape:
        liveness.updateForUse(user, /*lifetimeEnding*/ false);
        break;
      case OperandOwnership::ForwardingConsume:
        recordConsumingUse(use);
        liveness.updateForUse(user, /*lifetimeEnding*/ true);
        break;
      case OperandOwnership::DestroyingConsume:
        // destroy_value does not force pruned liveness (but store etc. does).
        if (!isa<DestroyValueInst>(user)) {
          liveness.updateForUse(user, /*lifetimeEnding*/ true);
        }
        recordConsumingUse(use);
        break;
      case OperandOwnership::Borrow:
        if (!liveness.updateForBorrowingOperand(use))
          return false;
        break;
      case OperandOwnership::InteriorPointer:
      case OperandOwnership::ForwardingBorrow:
      case OperandOwnership::EndBorrow:
      case OperandOwnership::Reborrow:
        llvm_unreachable("operand kind cannot take an owned value");
      }
    }
  }
  return true;
}

// Return true if \p inst is an end_access whose access scope overlaps the end
// of the pruned live range. This means that a hoisted destroy might execute
// within the access scope which previously executed outside the access scope.
//
// Not overlapping (ignored):
//
//     %def
//     use %def     // pruned liveness ends here
//     begin_access // access scope unrelated to def
//     end_access
//
// Overlapping (must extend pruned liveness):
//
//     %def
//     begin_access // access scope unrelated to def
//     use %def     // pruned liveness ends here
//     end_access
//
// Overlapping (must extend pruned liveness):
//
//     begin_access // access scope unrelated to def
//     %def
//     use %def     // pruned liveness ends here
//     end_access
//
bool CanonicalizeOSSALifetime::
endsAccessOverlappingPrunedBoundary(SILInstruction *inst) {
  if (isa<EndUnpairedAccessInst>(inst)) {
    return true;
  }
  auto *endAccess = dyn_cast<EndAccessInst>(inst);
  if (!endAccess) {
    return false;
  }
  auto *beginAccess = endAccess->getBeginAccess();
  SILBasicBlock *beginBB = beginAccess->getParent();
  switch (liveness.getBlockLiveness(beginBB)) {
  case PrunedLiveBlocks::LiveOut:
    // Found partial overlap of the form:
    //     currentDef
    //     beginAccess
    //     br...
    //   bb...
    //     use
    //     endAccess
    return true;
  case PrunedLiveBlocks::LiveWithin:
    // Check for partial overlap of this form where beginAccess and the last use
    // are in the same block:
    //     currentDef
    //     beginAccess
    //     use
    //     endAccess
    if (std::find_if(std::next(beginAccess->getIterator()), beginBB->end(),
                     [this](SILInstruction &nextInst) {
                       return liveness.isInterestingUser(&nextInst)
                         != PrunedLiveness::NonUser;
                     }) != beginBB->end()) {
      // An interesting use after the beginAccess means overlap.
      return true;
    }
    return false;
  case PrunedLiveBlocks::Dead:
    // Check for partial overlap of this form where beginAccess and currentDef
    // are in different blocks:
    //     beginAccess
    //     br...
    //  bb...
    //     currentDef
    //     endAccess
    //
    // Since beginAccess is not within the canonical live range, its access
    // scope overlaps only if there is a path from beginAccess to currentDef
    // that does not pass through endAccess. endAccess is dominated by
    // both currentDef and begin_access. Therefore, such a path only exists if
    // beginAccess dominates currentDef.
    DominanceInfo *domInfo = dominanceAnalysis->get(inst->getFunction());
    return domInfo->properlyDominates(beginAccess->getParent(),
                                      getCurrentDef()->getParentBlock());
  }
}

// Find all overlapping access scopes and extend pruned liveness to cover them:
//
// This may also unnecessarily, but conservatively extend liveness over some
// originally overlapping access, such as:
//
//     begin_access // access scope unrelated to def
//     %def
//     use %def
//     destroy %def
//     end_access
//
// Or:
//
//     %def
//     begin_access // access scope unrelated to def
//     use %def
//     destroy %def
//     end_access
//
// To minimize unnecessary lifetime extension, only search for end_access
// within dead blocks that are backward reachable from an original destroy.
//
// Note that lifetime extension is iterative because adding a new liveness use
// may create new overlapping access scopes. This can happen because there is no
// guarantee of strict stack discpline across unrelated access. For example:
//
//     %def
//     begin_access A
//     use %def        // Initial pruned lifetime boundary
//     begin_access B
//     end_access A    // Lifetime boundary after first extension
//     end_access B    // Lifetime boundary after second extension
//     destroy %def
//
// If the lifetime extension did not iterate, then def would be destroyed within
// B's access scope when originally it was destroyed outside that scope.
void CanonicalizeOSSALifetime::extendLivenessThroughOverlappingAccess() {
  this->accessBlocks = accessBlockAnalysis->get(getCurrentDef()->getFunction());

  // Visit each original consuming use or destroy as the starting point for a
  // backward CFG traversal. This traversal must only visit blocks within the
  // original extended lifetime.
  bool changed = true;
  while (changed) {
    changed = false;
    blockWorklist.clear();
    blockWorklist.insert(consumingBlocks.begin(), consumingBlocks.end());
    // This worklist is also a visited set, so we never pop the entries.
    for (unsigned blockIdx = 0; blockIdx < blockWorklist.size(); ++blockIdx) {
      SILBasicBlock *bb = blockWorklist[blockIdx];
      auto blockLiveness = liveness.getBlockLiveness(bb);
      // Ignore blocks within pruned liveness.
      if (blockLiveness == PrunedLiveBlocks::LiveOut) {
        continue;
      }
      if (blockLiveness == PrunedLiveBlocks::Dead) {
        // Continue searching upward to find the pruned liveness boundary.
        for (auto *predBB : bb->getPredecessorBlocks()) {
          blockWorklist.insert(predBB);
        }
        // Otherwise, ignore dead blocks with no nonlocal end_access.
        if (!accessBlocks->containsNonLocalEndAccess(bb)) {
          continue;
        }
      }
      bool blockHasUse = (blockLiveness == PrunedLiveBlocks::LiveWithin);
      // Find the latest partially overlapping access scope, if one exists:
      //     use %def // pruned liveness ends here
      //     end_access
      for (auto &inst : llvm::reverse(*bb)) {
        // Stop at the latest use. An earlier end_access does not overlap.
        if (blockHasUse && liveness.isInterestingUser(&inst)) {
          break;
        }
        if (endsAccessOverlappingPrunedBoundary(&inst)) {
          liveness.updateForUse(&inst, /*lifetimeEnding*/ false);
          changed = true;
          break;
        }
      }
      // If liveness changed, might as well restart CFG traversal.
      if (changed) {
        break;
      }
    }
  }
}

//===----------------------------------------------------------------------===//
// MARK: Step 2. Find the destroy points of the current def based on the pruned
// liveness computed in Step 1.
//===----------------------------------------------------------------------===//

/// The liveness boundary is at a CFG edge `predBB` -> `succBB`, meaning that
/// `currentDef` is live out of at least one other `predBB` successor.
///
/// Create and record a final destroy_value at the beginning of `succBB`
/// (assuming no critical edges).
void CanonicalizeOSSALifetime::insertDestroyOnCFGEdge(
  SILBasicBlock *predBB, SILBasicBlock *succBB, bool needsPoison) {

  assert(succBB->getSinglePredecessorBlock() == predBB
         && "value is live-out on another predBB successor: critical edge?");

  auto pos = succBB->begin();
  // TODO: to improve debugability, consider advancing the poison position ahead
  // of operations that are known not to access weak references.
  SILBuilderWithScope builder(pos);
  auto loc = RegularLocation::getAutoGeneratedLocation(pos->getLoc());
  auto *di = builder.createDestroyValue(loc, currentDef, needsPoison);

  consumes.recordFinalConsume(di);

  ++NumDestroysGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Destroy on edge " << *di);
}

/// This liveness boundary is within a basic block at the given position.
///
/// Create a final destroy, immediately after `pos`.
static void insertDestroyAtInst(SILBasicBlock::iterator pos,
                                DestroyValueInst *existingDestroy,
                                SILValue def, bool needsPoison,
                                CanonicalOSSAConsumeInfo &consumes) {
  if (existingDestroy) {
    for (; pos != existingDestroy->getIterator(); ++pos) {
      if (auto *debugVal = dyn_cast<DebugValueInst>(&*pos)) {
        consumes.popDebugAfterConsume(debugVal);
      }
    }
    consumes.recordFinalConsume(existingDestroy);
    // Avoid resetting poison just in case this runs twice.
    if (needsPoison) {
      existingDestroy->setPoisonRefs(true);
    }
    return;
  }
  SILBuilderWithScope builder(pos);
  auto loc = RegularLocation::getAutoGeneratedLocation((*pos).getLoc());
  auto *di = builder.createDestroyValue(loc, def, needsPoison);
  consumes.recordFinalConsume(di);

  ++NumDestroysGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Destroy at last use " << *di);
}

// The pruned liveness boundary is within the given basic block. Find the
// block's last use. If the last use consumes the value, record it as a
// destroy. Otherwise, insert a new destroy_value.
//
// TODO: This has become quite a hack. Instead, the final liveness boundary
// should be returned in a data structure along with summary information about
// each block. Then any special logic for handling existing destroys, debug
// values, and poison should be applied to that block summary which can provide
// the input to rewriteCopies.
void CanonicalizeOSSALifetime::findOrInsertDestroyInBlock(SILBasicBlock *bb) {
  auto *defInst = currentDef->getDefiningInstruction();
  DestroyValueInst *existingDestroy = nullptr;
  bool existingDestroyNeedsPoison = false;
  // needsPoison is true as soon as an existingDestroy is seen, but sticky.
  bool needsPoison = false;
  auto instIter = bb->getTerminator()->getIterator();
  while (true) {
    auto *inst = &*instIter;

    if (pruneDebugMode) {
      if (auto *dvi = dyn_cast<DebugValueInst>(inst)) {
        if (debugValues.erase(dvi))
          consumes.recordDebugAfterConsume(dvi);
      }
    }
    switch (liveness.isInterestingUser(inst)) {
    case PrunedLiveness::NonUser:
      break;
    case PrunedLiveness::NonLifetimeEndingUse:
      // Insert a destroy after this non-consuming use.
      if (isa<TermInst>(inst)) {
        for (auto &succ : bb->getSuccessors()) {
          insertDestroyOnCFGEdge(bb, succ, poisonRefsMode);
          setChanged();
        }
      } else {
        if (existingDestroy) {
          needsPoison = existingDestroyNeedsPoison;
        }
        insertDestroyAtInst(std::next(instIter), existingDestroy, currentDef,
                            needsPoison, consumes);
        setChanged();
      }
      return;
    case PrunedLiveness::LifetimeEndingUse:
      if (!needsPoison) {
        // This use becomes a final consume.
        consumes.recordFinalConsume(inst);
        return;
      }
      // If a destroy needs poison, simply make it so.
      auto *destroy = dyn_cast<DestroyValueInst>(inst);
      // Reuse an existing one if we need to.
      if (!destroy) {
        destroy = existingDestroy;
        needsPoison = existingDestroyNeedsPoison;
      }
      if (destroy) {
        destroy->setPoisonRefs(needsPoison);
        consumes.recordFinalConsume(destroy);
        return;
      }
      // Put this in the set of final consumes that need poison injection.
      consumes.recordNeedsPoison(inst);
      return;
    }
    // This is not a potential last user. Keep scanning.
    // Allow lifetimes to be artificially extended up to the next call. The goal
    // is to prevent repeated destroy rewriting without inhibiting optimization.
    if (ApplySite::isa(inst)) {
      existingDestroy = nullptr;
    } else if (!existingDestroy) {
      if (auto *destroy = dyn_cast<DestroyValueInst>(inst)) {
        auto destroyDef = CanonicalizeOSSALifetime::getCanonicalCopiedDef(
            destroy->getOperand());
        if (destroyDef == currentDef) {
          existingDestroy = destroy;
          // If this destroy is reused, it is not poisoned.
          existingDestroyNeedsPoison = needsPoison;
          if (poisonRefsMode) {
            // Any earlier consume will be poisoned.
            needsPoison = true;
          }
        }
      }
    }
    if (instIter == bb->begin()) {
      assert(cast<SILArgument>(currentDef)->getParent() == bb);
      if (existingDestroy) {
        needsPoison = existingDestroyNeedsPoison;
      }
      insertDestroyAtInst(instIter, existingDestroy, currentDef, needsPoison,
                          consumes);
      setChanged();
      return;
    }
    --instIter;
    // If the original def is reached, this is a dead live range. Insert a
    // destroy immediately after the def.
    if (&*instIter == defInst) {
      if (existingDestroy) {
        needsPoison = existingDestroyNeedsPoison;
      }
      insertDestroyAtInst(std::next(instIter), existingDestroy, currentDef,
                          needsPoison, consumes);
      setChanged();
      return;
    }
  }
}

/// Populate `consumes` with the final destroy points once copies are
/// eliminated. This only applies to owned values.
///
/// Observations:
/// - currentDef must be postdominated by some subset of its
///   consuming uses, including destroys on all return paths.
/// - The postdominating consumes cannot be within nested loops.
/// - Any blocks in nested loops are now marked LiveOut.
void CanonicalizeOSSALifetime::findOrInsertDestroys() {
  this->accessBlocks = accessBlockAnalysis->get(getCurrentDef()->getFunction());

  // Visit each original consuming use or destroy as the starting point for a
  // backward CFG traversal.
  blockWorklist.clear();
  blockWorklist.insert(consumingBlocks.begin(), consumingBlocks.end());
  // This worklist is also a visited set, so we never pop the entries.
  for (unsigned blockIdx = 0; blockIdx < blockWorklist.size(); ++blockIdx) {
    // Process each block that has not been visited and is not LiveOut.
    SILBasicBlock *bb = blockWorklist[blockIdx];
    switch (liveness.getBlockLiveness(bb)) {
    case PrunedLiveBlocks::LiveOut:
      // A lifetimeEndBlock may be determined to be LiveOut after analyzing the
      // extended  It is irrelevent for finding the boundary.
      break;
    case PrunedLiveBlocks::LiveWithin: {
      // The liveness boundary is inside this block. Insert a final destroy
      // inside the block if it doesn't already have one.
      findOrInsertDestroyInBlock(bb);
      break;
    }
    case PrunedLiveBlocks::Dead:
      // Continue searching upward to find the pruned liveness boundary.
      for (auto *predBB : bb->getPredecessorBlocks()) {
        if (liveness.getBlockLiveness(predBB) == PrunedLiveBlocks::LiveOut) {
          insertDestroyOnCFGEdge(predBB, bb, poisonRefsMode);
          setChanged();
        } else {
          if (poisonRefsMode) {
            remnantLiveOutBlocks.insert(predBB);
          }
          blockWorklist.insert(predBB);
        }
      }
      break;
    }
  }
}

//===----------------------------------------------------------------------===//
// MARK: Step 3. Rewrite copies and destroys
//===----------------------------------------------------------------------===//

/// Revisit the def-use chain of currentDef. Mark unneeded original
/// copies and destroys for deletion. Insert new copies for interior uses that
/// require ownership of the used operand.
void CanonicalizeOSSALifetime::rewriteCopies() {
  bool isOwned = currentDef.getOwnershipKind() == OwnershipKind::Owned;
  assert((!isOwned || !consumes.hasPersistentCopies())
         && "persistent copies use borrowed values");

  SmallSetVector<SILInstruction *, 8> instsToDelete;
  defUseWorklist.clear();

  // Visit each operand in the def-use chain.
  //
  // Return true if the operand can use the current definition. Return false if
  // it requires a copy.
  auto visitUse = [&](Operand *use) {
    auto *user = use->getUser();
    // Recurse through copies.
    if (auto *copy = dyn_cast<CopyValueInst>(user)) {
      if (!consumes.isPersistentCopy(copy)) {
        defUseWorklist.insert(copy);
        return true;
      }
    }
    if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
      // If this destroy was marked as a final destroy, ignore it; otherwise,
      // delete it.
      if (!consumes.claimConsume(destroy)) {
        instsToDelete.insert(destroy);
        LLVM_DEBUG(llvm::dbgs() << "  Removing " << *destroy);
        ++NumDestroysEliminated;
      }
      // If another destroy is reachable on this path, then poison this
      // destroy. It will already be poisoned if it was inserted on a CFG edge
      // or another destroy occurs later in the same block.
      if (!destroy->poisonRefs()
          && remnantLiveOutBlocks.count(destroy->getParent())) {
        destroy->setPoisonRefs(true);
      }
      return true;
    }

    // Nonconsuming uses do not need copies and cannot be marked as destroys.
    // A lifetime-ending use here must be a consume because EndBorrow/Reborrow
    // uses have been filtered out.
    if (!use->isLifetimeEnding())
      return true;

    // If this use was not marked as a final destroy *or* this is not the first
    // consumed operand we visited, then it needs a copy.
    if (!consumes.claimConsume(user))
      return false;

    // Final consumes that need poison, also need a copy.
    if (consumes.needsPoison(user))
      return false;

    // If another destroy is reachable on this path, then this consume needs
    // poison even though findOrInsertDestroyInBlock didn't know that.
    if (remnantLiveOutBlocks.count(user->getParent())) {
      consumes.recordNeedsPoison(user);
      return false;
    }
    return true;
  };

  // Perform a def-use traversal, visiting each use operand.
  for (auto useIter = currentDef->use_begin(), endIter = currentDef->use_end();
       useIter != endIter;) {
    Operand *use = *useIter++;
    // A direct lifetime-ending use of a guaranteed value (EndBorrow or
    // Reborrow), never needs a copy.
    if (!isOwned && use->isLifetimeEnding()) {
      continue;
    }
    if (!visitUse(use)) {
      copyLiveUse(use);
      setChanged();
    }
  }
  while (!defUseWorklist.empty()) {
    CopyValueInst *srcCopy = cast<CopyValueInst>(defUseWorklist.pop_back_val());
    // Recurse through copies while replacing their uses.
    Operand *reusedCopyOp = nullptr;
    for (auto useIter = srcCopy->use_begin(); useIter != srcCopy->use_end();) {
      Operand *use = *useIter++;
      if (!visitUse(use)) {
        if (!reusedCopyOp && srcCopy->getParent() == use->getParentBlock()) {
          reusedCopyOp = use;
        } else {
          copyLiveUse(use);
          setChanged();
        }
      }
    }
    if (!(reusedCopyOp && srcCopy->hasOneUse())) {
      setChanged();
      srcCopy->replaceAllUsesWith(srcCopy->getOperand());
      if (reusedCopyOp) {
        reusedCopyOp->set(srcCopy);
      } else {
        if (instsToDelete.insert(srcCopy)) {
          LLVM_DEBUG(llvm::dbgs() << "  Removing " << *srcCopy);
          ++NumCopiesEliminated;
        }
      }
    }
  }
  assert(!consumes.hasUnclaimedConsumes());

  // Insert destroys wherever poison is needed. This may recover more debug
  // values, erasing them from the debugValues set.
  injectPoison();

  // Add any debug_values from Dead blocks into the debugAfterConsume set.
  for (auto *dvi : debugValues) {
    if (liveness.getBlockLiveness(dvi->getParent()) == PrunedLiveBlocks::Dead) {
      consumes.recordDebugAfterConsume(dvi);
    }
  }

  // Remove any dead, non-recovered debug_values.
  for (auto *dvi : consumes.getDebugInstsAfterConsume()) {
    LLVM_DEBUG(llvm::dbgs() << "  Removing debug_value: " << *dvi);
    dvi->eraseFromParent();
  }

  // Remove the leftover copy_value and destroy_value instructions.
  if (!instsToDelete.empty()) {
    recursivelyDeleteTriviallyDeadInstructions(instsToDelete.takeVector(),
                                               /*force=*/true);
    setChanged();
  }
}

/// Insert poison destroys after each consume that needs poison.
void CanonicalizeOSSALifetime::injectPoison() {
  for (SILInstruction *consume : consumes.getNeedsPoisonConsumes()) {
    auto createDestroy = [&](SILBuilder &builder) {
      auto loc = RegularLocation::getAutoGeneratedLocation(
        builder.getInsertionPoint()->getLoc());
      auto *di = builder.createDestroyValue(loc, currentDef,
                                            /*needsPoison*/ true);
    
      ++NumDestroysGenerated;
      LLVM_DEBUG(llvm::dbgs() << "  Destroy at last use " << *di);
    };
    if (auto *branch = dyn_cast<BranchInst>(consume)) {
      // At a phi, destroy the value before branching.
      //
      // A copy must have been created for the branch operand during
      // rewriteCopies (but there's no easy way to assert that here).
      SILBuilderWithScope builder(branch);
      createDestroy(builder);
    } else {
      // For normal instructions and non-phi block terminators, destroy the
      // value after the operation.
      SILBuilderWithScope::insertAfter(consume, createDestroy);
    }
  }
}

//===----------------------------------------------------------------------===//
//                            MARK: Top-Level API
//===----------------------------------------------------------------------===//

/// True if \p def should be canonicalized in poisonRefs mode.
///
/// Currently, we only handle owned values because, for now, the goal is to
/// shorten lifetimes to mimic -O behavior, not to remove copies.
///
/// IRGen must also have support for injecting poison into values of this type.
bool shouldCanonicalizeWithPoison(SILValue def) {
  assert(def->getType().isObject() && "only SIL values are canonicalized");
  auto objectTy = def->getType().unwrapOptionalType();

  // TODO: Handle structs, enums, and tuples.
  //
  // TODO: Functions are not currently handled because of closure lifetime
  // bugs. Noescape closures don't always have a dependence.
  return objectTy.isAnyClassReferenceType();
}

bool CanonicalizeOSSALifetime::canonicalizeValueLifetime(SILValue def) {
  LLVM_DEBUG(llvm::dbgs() << "  Canonicalizing: " << def);

  switch (def.getOwnershipKind()) {
  case OwnershipKind::None:
  case OwnershipKind::Unowned:
  case OwnershipKind::Any:
    return false;
  case OwnershipKind::Guaranteed:
    // The goal of poisonRefsMode is only to hoist destroys, not remove copies.
    if (poisonRefsMode)
      return false;

    initDef(def);
    if (!computeBorrowLiveness()) {
      clearLiveness();
      return false;
    }
    // Set outerCopy and persistentCopies and rewrite uses
    // outside the scope.
    if (!consolidateBorrowScope()) {
      clearLiveness();
      return false;
    }
    // Invalidate book-keeping before deleting instructions.
    clearLiveness();
    // Rewrite copies and delete extra destroys within the scope.
    assert(!consumes.hasFinalConsumes());
    rewriteCopies();
    return true;
  case OwnershipKind::Owned:
    if (poisonRefsMode && !shouldCanonicalizeWithPoison(def))
      return false;

    initDef(def);
    // Step 1: compute liveness
    if (!computeCanonicalLiveness()) {
      clearLiveness();
      return false;
    }
    extendLivenessThroughOverlappingAccess();
    // Step 2: record final destroys
    findOrInsertDestroys();
    // Step 3: rewrite copies and delete extra destroys
    rewriteCopies();

    clearLiveness();
    consumes.clear();
    return true;
  }
}

//===----------------------------------------------------------------------===//
//                              MARK: Debugging
//===----------------------------------------------------------------------===//

SWIFT_ASSERT_ONLY_DECL(
  void CanonicalOSSAConsumeInfo::dump() const {
    llvm::dbgs() << "Consumes:";
    for (auto &blockAndInst : finalBlockConsumes) {
      llvm::dbgs() << "  " << *blockAndInst.getSecond();
    }
  })