lib/SILOptimizer/Utils/CanonicalizeInstruction.cpp - third_party/swift - Git at Google

 //===--- CanonicalizeInstruction.cpp - canonical SIL peepholes ------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2019 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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// SSA-peephole transformations that yield a more canonical SIL representation.
 ///
 /// A superset of simplifyInstruction.
 ///
 //===----------------------------------------------------------------------===//

 // CanonicalizeInstruction defines a default DEBUG_TYPE: "sil-canonicalize"

 #include "swift/SILOptimizer/Utils/CanonicalizeInstruction.h"
 #include "swift/SIL/DebugUtils.h"
 #include "swift/SIL/InstructionUtils.h"
 #include "swift/SIL/Projection.h"
 #include "swift/SIL/SILBuilder.h"
 #include "swift/SIL/SILFunction.h"
 #include "swift/SIL/SILInstruction.h"
 #include "swift/SILOptimizer/Analysis/SimplifyInstruction.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Debug.h"

 using namespace swift;

 // STATISTIC uses the default DEBUG_TYPE.
 #define DEBUG_TYPE CanonicalizeInstruction::defaultDebugType
 STATISTIC(NumSimplified, "Number of instructions simplified");

 // Tracing within the implementation can also be activiated by the pass.
 #undef DEBUG_TYPE
 #define DEBUG_TYPE pass.debugType

 // Vtable anchor.
 CanonicalizeInstruction::~CanonicalizeInstruction() {}

 // Helper to delete an instruction, or mark it for deletion.
 //
 // Return an iterator to the next non-deleted instruction. The incoming iterator
 // may already have advanced beyond 'inst'.
 static SILBasicBlock::iterator killInstruction(SILInstruction *inst,
                                                SILBasicBlock::iterator nextII,
                                                CanonicalizeInstruction &pass) {
   if (nextII == inst->getIterator())
     ++nextII;
   pass.killInstruction(inst);
   return nextII;
 }

 // Helper to delete, or mark for deletion, an instruction with potential debug
 // or end of scope uses. All "real" uses must already be removed.
 //
 // fix_lifetime uses are not currently handled here. They are generally
 // (incorrectly) treated as "incidental" uses, but no canonicalizations need
 // them yet.
 static SILBasicBlock::iterator
 killInstAndIncidentalUses(SingleValueInstruction *inst,
                           SILBasicBlock::iterator nextII,
                           CanonicalizeInstruction &pass) {
   while (!inst->use_empty()) {
     auto *user = inst->use_begin()->getUser();
     assert(user->isDebugInstruction() || isEndOfScopeMarker(user));
     nextII = killInstruction(user, nextII, pass);
   }
   return killInstruction(inst, nextII, pass);
 }

 //===----------------------------------------------------------------------===//
 //                          Instruction Simplification
 //===----------------------------------------------------------------------===//

 // If simplification is successful, return a valid iterator to the next
 // intruction that wasn't erased.
 static Optional<SILBasicBlock::iterator>
 simplifyAndReplace(SILInstruction *inst, CanonicalizeInstruction &pass) {
   SILValue result = simplifyInstruction(inst);
   if (!result)
     return None;

   ++NumSimplified;

   LLVM_DEBUG(llvm::dbgs() << "Simplify Old = " << *inst
                           << "    New = " << *result << '\n');

   // Erase the simplified instruction and any instructions that end its
   // scope. Nothing needs to be added to the worklist except for Result,
   // because the instruction and all non-replaced users will be deleted.
   auto nextII = replaceAllSimplifiedUsesAndErase(
       inst, result,
       [&pass](SILInstruction *deleted) { pass.killInstruction(deleted); },
       [&pass](SILInstruction *newInst) { pass.notifyNewInstruction(newInst); },
       &pass.deadEndBlocks);

   // Push the new instruction and any users onto the worklist.
   pass.notifyHasNewUsers(result);
   return nextII;
 }

 //===----------------------------------------------------------------------===//
 //                        Canonicalize Memory Operations
 //===----------------------------------------------------------------------===//

 namespace {

 struct LoadOperation {
   llvm::PointerUnion<LoadInst *, LoadBorrowInst *> value;

   LoadOperation(SILInstruction *input) : value(nullptr) {
     if (auto *li = dyn_cast<LoadInst>(input)) {
       value = li;
       return;
     }

     if (auto *lbi = dyn_cast<LoadBorrowInst>(input)) {
       value = lbi;
       return;
     }
   }

   operator bool() const { return !value.isNull(); }

   SingleValueInstruction *operator*() const {
     if (value.is<LoadInst *>())
       return value.get<LoadInst *>();
     return value.get<LoadBorrowInst *>();
   }

   const SingleValueInstruction *operator->() const {
     if (value.is<LoadInst *>())
       return value.get<LoadInst *>();
     return value.get<LoadBorrowInst *>();
   }

   SingleValueInstruction *operator->() {
     if (value.is<LoadInst *>())
       return value.get<LoadInst *>();
     return value.get<LoadBorrowInst *>();
   }

   Optional<LoadOwnershipQualifier> getOwnershipQualifier() const {
     if (auto *lbi = value.dyn_cast<LoadBorrowInst *>()) {
       return None;
     }

     return value.get<LoadInst *>()->getOwnershipQualifier();
   }
 };

 } // anonymous namespace

 // Replace all uses of an original struct or tuple extract instruction with the
 // given load instruction. The caller ensures that the load only loads the
 // extracted field.
 //
 // \p extract has the form:
 // (struct_extract (load %base), #field)
 //
 // \p loadInst has the form:
 // (load (struct_element_addr %base, #field)
 static void replaceUsesOfExtract(SingleValueInstruction *extract,
                                  LoadOperation loadInst,
                                  CanonicalizeInstruction &pass) {
   assert(extract->getType() == loadInst->getType());

   SingleValueInstruction *loadedVal = *loadInst;
   if (auto qual = loadInst.getOwnershipQualifier()) {
     if (*qual == LoadOwnershipQualifier::Copy) {
       // Borrow the load-copied subelement, with precisely the same scope as
       // the aggregate borrow.
       assert(extract->getNumOperands() == 1);
       auto *origBorrow = cast<BeginBorrowInst>(extract->getOperand(0));
       auto *newBorrow = SILBuilderWithScope(origBorrow)
                             .createBeginBorrow(loadInst->getLoc(), *loadInst);
       pass.notifyNewInstruction(newBorrow);

       assert(extract == origBorrow->getSingleNonEndingUse()->getUser());
       for (auto *origEnd : origBorrow->getEndBorrows()) {
         auto *endBorrow = SILBuilderWithScope(origEnd).createEndBorrow(
             origEnd->getLoc(), newBorrow);
         pass.notifyNewInstruction(endBorrow);
       }
       loadedVal = newBorrow;
     }
   }
   LLVM_DEBUG(llvm::dbgs() << "Replacing " << *extract << "    with "
                           << *loadedVal << "\n");
   extract->replaceAllUsesWith(loadedVal);
 }

 // Given a load with multiple struct_extracts/tuple_extracts and no other uses,
 // canonicalize the load into several (struct_element_addr (load)) pairs.
 //
 // (struct_extract (load %base))
 //   ->
 // (load (struct_element_addr %base, #field)
 //
 // TODO: Consider handling LoadBorrowInst.
 static SILBasicBlock::iterator
 splitAggregateLoad(LoadOperation loadInst, CanonicalizeInstruction &pass) {
   // Keep track of the next iterator after any newly added or to-be-deleted
   // instructions. This must be valid regardless of whether the pass immediately
   // deletes the instructions or simply records them for later deletion.
   auto nextII = std::next(loadInst->getIterator());

   bool needsBorrow;
   if (auto qual = loadInst.getOwnershipQualifier()) {
     switch (*qual) {
     case LoadOwnershipQualifier::Unqualified:
     case LoadOwnershipQualifier::Trivial:
       needsBorrow = false;
       break;
     case LoadOwnershipQualifier::Copy:
       needsBorrow = true;
       break;
     case LoadOwnershipQualifier::Take:
       // TODO: To handle a "take", we would need to generate additional destroys
       // for any fields that aren't already extracted. This would be
       // out-of-place for this transform, and I'm not sure if this a case that
       // needs to be handled in CanonicalizeInstruction.
       return nextII;
     }
   } else {
     // If we don't have a qual, we have a borrow.
     needsBorrow = false;
   }

   struct ProjInstPair {
     Projection proj;
     SingleValueInstruction *extract;

     // When sorting, just look at the projection and ignore the instruction.
     // Including the instruction address in the sort key would be
     // nondeterministic.
     bool operator<(const ProjInstPair &rhs) const { return proj < rhs.proj; }
   };

   // Add load projections to a projection list.
   llvm::SmallVector<ProjInstPair, 8> projections;
   llvm::SmallVector<BeginBorrowInst *, 8> borrows;
   llvm::SmallVector<SILInstruction *, 8> lifetimeEndingInsts;
   for (auto *use : getNonDebugUses(*loadInst)) {
     auto *user = use->getUser();
     if (needsBorrow) {
       if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
         lifetimeEndingInsts.push_back(destroy);
         continue;
       }
       auto *borrow = dyn_cast<BeginBorrowInst>(user);
       if (!borrow)
         return nextII;

       // The transformation below also assumes a single borrow use.
       auto *borrowedOper = borrow->getSingleNonEndingUse();
       if (!borrowedOper)
         return nextII;

       borrows.push_back(borrow);
       user = borrowedOper->getUser();
     } else {
       if (isa<EndBorrowInst>(user) &&
           !loadInst.getOwnershipQualifier().hasValue()) {
         lifetimeEndingInsts.push_back(user);
         continue;
       }
     }

     // If we have any non SEI, TEI instruction, don't do anything here.
     if (!isa<StructExtractInst>(user) && !isa<TupleExtractInst>(user))
       return nextII;

     auto extract = cast<SingleValueInstruction>(user);
     projections.push_back({Projection(extract), extract});
   }
   // Sort the list so projections with the same value decl and tuples with the
   // same indices will be processed together. This makes it easy to reuse the
   // load from the first such projection for all subsequent projections on the
   // same value decl or index.
   std::sort(projections.begin(), projections.end());

   // If the original load is dead, then do not delete it before
   // diagnostics. Doing so would suppress DefiniteInitialization in cases like:
   //
   // struct S {
   //   let a: Int
   //   init() {
   //     _ = a // must be diagnosed as use before initialization
   //     a = 0
   //   }
   // }
   //
   // However, if the load has any projections, it must be deleted, otherwise
   // exclusivity checking is too strict:
   //
   // extension S {
   //   mutating func foo() {
   //     _ = a // Must be diagnosed as a read of self.a only not the whole self.
   //   }
   // }
   //
   // TODO: This logic subtly anticipates SILGen behavior. In the future, change
   // SILGen to avoid emitting the full load and never delete loads in Raw SIL.
   if (projections.empty() && loadInst->getModule().getStage() == SILStage::Raw)
     return nextII;

   // Create a new address projection instruction and load instruction for each
   // unique projection.
   Projection *lastProj = nullptr;
   Optional<LoadOperation> lastNewLoad;
   for (auto &pair : projections) {
     auto &proj = pair.proj;
     auto *extract = pair.extract;

     // If this projection is the same as the last projection we processed, just
     // replace all uses of the projection with the load we created previously.
     if (lastProj && proj == *lastProj) {
       replaceUsesOfExtract(extract, *lastNewLoad, pass);
       nextII = killInstruction(extract, nextII, pass);
       continue;
     }

     // This is a unique projection. Create the new address projection and load.
     lastProj = &proj;
     // Insert new instructions before the original load.
     SILBuilderWithScope LoadBuilder(*loadInst);
     auto *projInst =
         proj.createAddressProjection(LoadBuilder, loadInst->getLoc(),
                                      loadInst->getOperand(0))
             .get();
     pass.notifyNewInstruction(projInst);

     // When loading a trivial subelement, convert ownership.
     Optional<LoadOwnershipQualifier> loadOwnership =
         loadInst.getOwnershipQualifier();
     if (loadOwnership.hasValue()) {
       if (*loadOwnership != LoadOwnershipQualifier::Unqualified &&
           projInst->getType().isTrivial(*projInst->getFunction()))
         loadOwnership = LoadOwnershipQualifier::Trivial;
     } else {
       if (projInst->getType().isTrivial(*projInst->getFunction()))
         loadOwnership = LoadOwnershipQualifier::Trivial;
     }

     if (loadOwnership) {
       lastNewLoad =
           LoadBuilder.createLoad(loadInst->getLoc(), projInst, *loadOwnership);
     } else {
       lastNewLoad = LoadBuilder.createLoadBorrow(loadInst->getLoc(), projInst);
     }
     pass.notifyNewInstruction(**lastNewLoad);

     if (loadOwnership) {
       if (*loadOwnership == LoadOwnershipQualifier::Copy) {
         // Destroy the loaded value wherever the aggregate load was destroyed.
         assert(loadInst.getOwnershipQualifier() ==
                LoadOwnershipQualifier::Copy);
         for (SILInstruction *destroy : lifetimeEndingInsts) {
           auto *newInst = SILBuilderWithScope(destroy).createDestroyValue(
               destroy->getLoc(), **lastNewLoad);
           pass.notifyNewInstruction(newInst);
         }
       }
     } else {
       for (SILInstruction *destroy : lifetimeEndingInsts) {
         auto *newInst = SILBuilderWithScope(destroy).createEndBorrow(
             destroy->getLoc(), **lastNewLoad);
         pass.notifyNewInstruction(newInst);
       }
     }
     replaceUsesOfExtract(extract, *lastNewLoad, pass);
     nextII = killInstruction(extract, nextII, pass);
   }

   // Remove the now unused borrows.
   for (auto *borrow : borrows)
     nextII = killInstAndIncidentalUses(borrow, nextII, pass);

   // Erase the old load.
   for (auto *destroy : lifetimeEndingInsts)
     nextII = killInstruction(destroy, nextII, pass);

   return killInstAndIncidentalUses(*loadInst, nextII, pass);
 }

 // Given a store within a single property struct, recursively form the parent
 // struct values and promote the store to the outer struct type.
 //
 // (store (struct_element_addr %base) object)
 //   ->
 // (store %base (struct object))
 //
 // TODO: supporting enums here would be very easy. The main thing is adding
 // support in `createAggFromFirstLevelProjections`.
 // Note: we will not be able to support tuples because we cannot have a
 // single-element tuple.
 static SILBasicBlock::iterator
 broadenSingleElementStores(StoreInst *storeInst,
                            CanonicalizeInstruction &pass) {
   // Keep track of the next iterator after any newly added or to-be-deleted
   // instructions. This must be valid regardless of whether the pass immediately
   // deletes the instructions or simply records them for later deletion.
   auto nextII = std::next(storeInst->getIterator());
   auto *f = storeInst->getFunction();

   ProjectionPath projections(storeInst->getDest()->getType());
   SILValue op = storeInst->getDest();
   while (isa<StructElementAddrInst>(op)) {
     auto *inst = cast<SingleValueInstruction>(op);
     SILValue baseAddr = inst->getOperand(0);
     SILType baseAddrType = baseAddr->getType();
     auto *decl = baseAddrType.getStructOrBoundGenericStruct();
     assert(
       !decl->isResilient(f->getModule().getSwiftModule(),
                          f->getResilienceExpansion()) &&
         "This code assumes resilient structs can not have fragile fields. If "
         "this assert is hit, this has been changed. Please update this code.");

     // Bail if the store's destination is not a struct_element_addr or if the
     // store's destination (%base) is not a loadable type. If %base is not a
     // loadable type, we can't create it as a struct later on.
     // If our aggregate has unreferenced storage then we can never prove if it
     // actually has a single field.
     if (!baseAddrType.isLoadable(*f) ||
         baseAddrType.aggregateHasUnreferenceableStorage() ||
         decl->getStoredProperties().size() != 1)
       break;

     projections.push_back(Projection(inst));
     op = baseAddr;
   }

   // If we couldn't create a projection, bail.
   if (projections.empty())
     return nextII;

   // Now work our way back up. At this point we know all operations we are going
   // to do succeed (cast<SingleValueInst>, createAggFromFirstLevelProjections,
   // etc.) so we can omit null checks. We should not bail at this point (we
   // could create a double consume, or worse).
   SILBuilderWithScope builder(storeInst);
   SILValue result = storeInst->getSrc();
   SILValue storeAddr = storeInst->getDest();
   for (Projection proj : llvm::reverse(projections)) {
     storeAddr = cast<SingleValueInstruction>(storeAddr)->getOperand(0);
     result = proj.createAggFromFirstLevelProjections(
                      builder, storeInst->getLoc(),
                      storeAddr->getType().getObjectType(), {result})
                  .get();
   }

   // Store the new struct-wrapped value into the final base address.
   builder.createStore(storeInst->getLoc(), result, storeAddr,
                       storeInst->getOwnershipQualifier());

   // Erase the original store.
   return killInstruction(storeInst, nextII, pass);
 }

 //===----------------------------------------------------------------------===//
 //                            Simple ARC Peepholes
 //===----------------------------------------------------------------------===//

 static SILBasicBlock::iterator
 eliminateSimpleCopies(CopyValueInst *cvi, CanonicalizeInstruction &pass) {
   auto next = std::next(cvi->getIterator());

   // Eliminate copies that only have destroy_value uses.
   SmallVector<DestroyValueInst *, 8> destroys;
   for (auto *use : getNonDebugUses(cvi)) {
     if (auto *dvi = dyn_cast<DestroyValueInst>(use->getUser())) {
       destroys.push_back(dvi);
       continue;
     }
     return next;
   }

   while (!destroys.empty()) {
     next = killInstruction(destroys.pop_back_val(), next, pass);
   }

   next = killInstAndIncidentalUses(cvi, next, pass);
   return next;
 }

 static SILBasicBlock::iterator
 eliminateSimpleBorrows(BeginBorrowInst *bbi, CanonicalizeInstruction &pass) {
   auto next = std::next(bbi->getIterator());

   // We know that our borrow is completely within the lifetime of its base value
   // if the borrow is never reborrowed. We check for reborrows and do not
   // optimize such cases. Otherwise, we can eliminate our borrow and instead use
   // our operand.
   auto base = bbi->getOperand();
   auto baseOwnership = base.getOwnershipKind();
   SmallVector<EndBorrowInst *, 8> endBorrows;
   for (auto *use : getNonDebugUses(bbi)) {
     if (auto *ebi = dyn_cast<EndBorrowInst>(use->getUser())) {
       endBorrows.push_back(ebi);
       continue;
     }

     // Otherwise, if we have a use that is non-lifetime ending and can accept
     // our base ownership, continue.
     if (!use->isLifetimeEnding() && use->canAcceptKind(baseOwnership))
       continue;

     return next;
   }

   while (!endBorrows.empty()) {
     next = killInstruction(endBorrows.pop_back_val(), next, pass);
   }
   bbi->replaceAllUsesWith(base);
   pass.notifyHasNewUsers(base);
   return killInstruction(bbi, next, pass);
 }

 /// Delete any result having forwarding instruction that only has destroy_value
 /// and debug_value uses.
 static SILBasicBlock::iterator
 eliminateUnneededForwardingUnarySingleValueInst(SingleValueInstruction *inst,
                                                 CanonicalizeInstruction &pass) {
   auto next = std::next(inst->getIterator());

   for (auto *use : getNonDebugUses(inst))
     if (!isa<DestroyValueInst>(use->getUser()))
       return next;
   deleteAllDebugUses(inst);
   SILValue op = inst->getOperand(0);
   inst->replaceAllUsesWith(op);
   pass.notifyHasNewUsers(op);
   return killInstruction(inst, next, pass);
 }

 static Optional<SILBasicBlock::iterator>
 tryEliminateUnneededForwardingInst(SILInstruction *i,
                                    CanonicalizeInstruction &pass) {
   assert(isa<OwnershipForwardingInst>(i) &&
          "Must be an ownership forwarding inst");
   if (auto *svi = dyn_cast<SingleValueInstruction>(i))
     if (svi->getNumOperands() == 1)
       return eliminateUnneededForwardingUnarySingleValueInst(svi, pass);

   return None;
 }

 //===----------------------------------------------------------------------===//
 //                            Top-Level Entry Point
 //===----------------------------------------------------------------------===//

 SILBasicBlock::iterator
 CanonicalizeInstruction::canonicalize(SILInstruction *inst) {
   if (auto nextII = simplifyAndReplace(inst, *this))
     return nextII.getValue();

   if (auto li = LoadOperation(inst)) {
     return splitAggregateLoad(li, *this);
   }

   if (auto *storeInst = dyn_cast<StoreInst>(inst)) {
     return broadenSingleElementStores(storeInst, *this);
   }

   if (auto *cvi = dyn_cast<CopyValueInst>(inst))
     return eliminateSimpleCopies(cvi, *this);

   if (auto *bbi = dyn_cast<BeginBorrowInst>(inst))
     return eliminateSimpleBorrows(bbi, *this);

   // If we have ownership and are not in raw SIL, eliminate unneeded forwarding
   // insts. We don't do this in raw SIL as not to disturb the codegen read by
   // diagnostics.
   auto *fn = inst->getFunction();
   if (fn->hasOwnership() && fn->getModule().getStage() != SILStage::Raw) {
     if (isa<OwnershipForwardingInst>(inst))
       if (auto newNext = tryEliminateUnneededForwardingInst(inst, *this))
         return *newNext;
   }

   // Skip ahead.
   return std::next(inst->getIterator());
 }
	//===--- CanonicalizeInstruction.cpp - canonical SIL peepholes ------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2019 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
	//
	//===----------------------------------------------------------------------===//
	///
	/// SSA-peephole transformations that yield a more canonical SIL representation.
	///
	/// A superset of simplifyInstruction.
	///
	//===----------------------------------------------------------------------===//

	// CanonicalizeInstruction defines a default DEBUG_TYPE: "sil-canonicalize"

	#include "swift/SILOptimizer/Utils/CanonicalizeInstruction.h"
	#include "swift/SIL/DebugUtils.h"
	#include "swift/SIL/InstructionUtils.h"
	#include "swift/SIL/Projection.h"
	#include "swift/SIL/SILBuilder.h"
	#include "swift/SIL/SILFunction.h"
	#include "swift/SIL/SILInstruction.h"
	#include "swift/SILOptimizer/Analysis/SimplifyInstruction.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/Support/Debug.h"

	using namespace swift;

	// STATISTIC uses the default DEBUG_TYPE.
	#define DEBUG_TYPE CanonicalizeInstruction::defaultDebugType
	STATISTIC(NumSimplified, "Number of instructions simplified");

	// Tracing within the implementation can also be activiated by the pass.
	#undef DEBUG_TYPE
	#define DEBUG_TYPE pass.debugType

	// Vtable anchor.
	CanonicalizeInstruction::~CanonicalizeInstruction() {}

	// Helper to delete an instruction, or mark it for deletion.
	//
	// Return an iterator to the next non-deleted instruction. The incoming iterator
	// may already have advanced beyond 'inst'.
	static SILBasicBlock::iterator killInstruction(SILInstruction *inst,
	SILBasicBlock::iterator nextII,
	CanonicalizeInstruction &pass) {
	if (nextII == inst->getIterator())
	++nextII;
	pass.killInstruction(inst);
	return nextII;
	}

	// Helper to delete, or mark for deletion, an instruction with potential debug
	// or end of scope uses. All "real" uses must already be removed.
	//
	// fix_lifetime uses are not currently handled here. They are generally
	// (incorrectly) treated as "incidental" uses, but no canonicalizations need
	// them yet.
	static SILBasicBlock::iterator
	killInstAndIncidentalUses(SingleValueInstruction *inst,
	SILBasicBlock::iterator nextII,
	CanonicalizeInstruction &pass) {
	while (!inst->use_empty()) {
	auto *user = inst->use_begin()->getUser();
	assert(user->isDebugInstruction() \|\| isEndOfScopeMarker(user));
	nextII = killInstruction(user, nextII, pass);
	}
	return killInstruction(inst, nextII, pass);
	}

	//===----------------------------------------------------------------------===//
	// Instruction Simplification
	//===----------------------------------------------------------------------===//

	// If simplification is successful, return a valid iterator to the next
	// intruction that wasn't erased.
	static Optional<SILBasicBlock::iterator>
	simplifyAndReplace(SILInstruction *inst, CanonicalizeInstruction &pass) {
	SILValue result = simplifyInstruction(inst);
	if (!result)
	return None;

	++NumSimplified;

	LLVM_DEBUG(llvm::dbgs() << "Simplify Old = " << *inst
	<< " New = " << *result << '\n');

	// Erase the simplified instruction and any instructions that end its
	// scope. Nothing needs to be added to the worklist except for Result,
	// because the instruction and all non-replaced users will be deleted.
	auto nextII = replaceAllSimplifiedUsesAndErase(
	inst, result,
	[&pass](SILInstruction *deleted) { pass.killInstruction(deleted); },
	[&pass](SILInstruction *newInst) { pass.notifyNewInstruction(newInst); },
	&pass.deadEndBlocks);

	// Push the new instruction and any users onto the worklist.
	pass.notifyHasNewUsers(result);
	return nextII;
	}

	//===----------------------------------------------------------------------===//
	// Canonicalize Memory Operations
	//===----------------------------------------------------------------------===//

	namespace {

	struct LoadOperation {
	llvm::PointerUnion<LoadInst , LoadBorrowInst > value;

	LoadOperation(SILInstruction *input) : value(nullptr) {
	if (auto *li = dyn_cast<LoadInst>(input)) {
	value = li;
	return;
	}

	if (auto *lbi = dyn_cast<LoadBorrowInst>(input)) {
	value = lbi;
	return;
	}
	}

	operator bool() const { return !value.isNull(); }

	SingleValueInstruction operator() const {
	if (value.is<LoadInst *>())
	return value.get<LoadInst *>();
	return value.get<LoadBorrowInst *>();
	}

	const SingleValueInstruction *operator->() const {
	if (value.is<LoadInst *>())
	return value.get<LoadInst *>();
	return value.get<LoadBorrowInst *>();
	}

	SingleValueInstruction *operator->() {
	if (value.is<LoadInst *>())
	return value.get<LoadInst *>();
	return value.get<LoadBorrowInst *>();
	}

	Optional<LoadOwnershipQualifier> getOwnershipQualifier() const {
	if (auto lbi = value.dyn_cast<LoadBorrowInst >()) {
	return None;
	}

	return value.get<LoadInst *>()->getOwnershipQualifier();
	}
	};

	} // anonymous namespace

	// Replace all uses of an original struct or tuple extract instruction with the
	// given load instruction. The caller ensures that the load only loads the
	// extracted field.
	//
	// \p extract has the form:
	// (struct_extract (load %base), #field)
	//
	// \p loadInst has the form:
	// (load (struct_element_addr %base, #field)
	static void replaceUsesOfExtract(SingleValueInstruction *extract,
	LoadOperation loadInst,
	CanonicalizeInstruction &pass) {
	assert(extract->getType() == loadInst->getType());

	SingleValueInstruction loadedVal = loadInst;
	if (auto qual = loadInst.getOwnershipQualifier()) {
	if (*qual == LoadOwnershipQualifier::Copy) {
	// Borrow the load-copied subelement, with precisely the same scope as
	// the aggregate borrow.
	assert(extract->getNumOperands() == 1);
	auto *origBorrow = cast<BeginBorrowInst>(extract->getOperand(0));
	auto *newBorrow = SILBuilderWithScope(origBorrow)
	.createBeginBorrow(loadInst->getLoc(), *loadInst);
	pass.notifyNewInstruction(newBorrow);

	assert(extract == origBorrow->getSingleNonEndingUse()->getUser());
	for (auto *origEnd : origBorrow->getEndBorrows()) {
	auto *endBorrow = SILBuilderWithScope(origEnd).createEndBorrow(
	origEnd->getLoc(), newBorrow);
	pass.notifyNewInstruction(endBorrow);
	}
	loadedVal = newBorrow;
	}
	}
	LLVM_DEBUG(llvm::dbgs() << "Replacing " << *extract << " with "
	<< *loadedVal << "\n");
	extract->replaceAllUsesWith(loadedVal);
	}

	// Given a load with multiple struct_extracts/tuple_extracts and no other uses,
	// canonicalize the load into several (struct_element_addr (load)) pairs.
	//
	// (struct_extract (load %base))
	// ->
	// (load (struct_element_addr %base, #field)
	//
	// TODO: Consider handling LoadBorrowInst.
	static SILBasicBlock::iterator
	splitAggregateLoad(LoadOperation loadInst, CanonicalizeInstruction &pass) {
	// Keep track of the next iterator after any newly added or to-be-deleted
	// instructions. This must be valid regardless of whether the pass immediately
	// deletes the instructions or simply records them for later deletion.
	auto nextII = std::next(loadInst->getIterator());

	bool needsBorrow;
	if (auto qual = loadInst.getOwnershipQualifier()) {
	switch (*qual) {
	case LoadOwnershipQualifier::Unqualified:
	case LoadOwnershipQualifier::Trivial:
	needsBorrow = false;
	break;
	case LoadOwnershipQualifier::Copy:
	needsBorrow = true;
	break;
	case LoadOwnershipQualifier::Take:
	// TODO: To handle a "take", we would need to generate additional destroys
	// for any fields that aren't already extracted. This would be
	// out-of-place for this transform, and I'm not sure if this a case that
	// needs to be handled in CanonicalizeInstruction.
	return nextII;
	}
	} else {
	// If we don't have a qual, we have a borrow.
	needsBorrow = false;
	}

	struct ProjInstPair {
	Projection proj;
	SingleValueInstruction *extract;

	// When sorting, just look at the projection and ignore the instruction.
	// Including the instruction address in the sort key would be
	// nondeterministic.
	bool operator<(const ProjInstPair &rhs) const { return proj < rhs.proj; }
	};

	// Add load projections to a projection list.
	llvm::SmallVector<ProjInstPair, 8> projections;
	llvm::SmallVector<BeginBorrowInst *, 8> borrows;
	llvm::SmallVector<SILInstruction *, 8> lifetimeEndingInsts;
	for (auto use : getNonDebugUses(loadInst)) {
	auto *user = use->getUser();
	if (needsBorrow) {
	if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
	lifetimeEndingInsts.push_back(destroy);
	continue;
	}
	auto *borrow = dyn_cast<BeginBorrowInst>(user);
	if (!borrow)
	return nextII;

	// The transformation below also assumes a single borrow use.
	auto *borrowedOper = borrow->getSingleNonEndingUse();
	if (!borrowedOper)
	return nextII;

	borrows.push_back(borrow);
	user = borrowedOper->getUser();
	} else {
	if (isa<EndBorrowInst>(user) &&
	!loadInst.getOwnershipQualifier().hasValue()) {
	lifetimeEndingInsts.push_back(user);
	continue;
	}
	}

	// If we have any non SEI, TEI instruction, don't do anything here.
	if (!isa<StructExtractInst>(user) && !isa<TupleExtractInst>(user))
	return nextII;

	auto extract = cast<SingleValueInstruction>(user);
	projections.push_back({Projection(extract), extract});
	}
	// Sort the list so projections with the same value decl and tuples with the
	// same indices will be processed together. This makes it easy to reuse the
	// load from the first such projection for all subsequent projections on the
	// same value decl or index.
	std::sort(projections.begin(), projections.end());

	// If the original load is dead, then do not delete it before
	// diagnostics. Doing so would suppress DefiniteInitialization in cases like:
	//
	// struct S {
	// let a: Int
	// init() {
	// _ = a // must be diagnosed as use before initialization
	// a = 0
	// }
	// }
	//
	// However, if the load has any projections, it must be deleted, otherwise
	// exclusivity checking is too strict:
	//
	// extension S {
	// mutating func foo() {
	// _ = a // Must be diagnosed as a read of self.a only not the whole self.
	// }
	// }
	//
	// TODO: This logic subtly anticipates SILGen behavior. In the future, change
	// SILGen to avoid emitting the full load and never delete loads in Raw SIL.
	if (projections.empty() && loadInst->getModule().getStage() == SILStage::Raw)
	return nextII;

	// Create a new address projection instruction and load instruction for each
	// unique projection.
	Projection *lastProj = nullptr;
	Optional<LoadOperation> lastNewLoad;
	for (auto &pair : projections) {
	auto &proj = pair.proj;
	auto *extract = pair.extract;

	// If this projection is the same as the last projection we processed, just
	// replace all uses of the projection with the load we created previously.
	if (lastProj && proj == *lastProj) {
	replaceUsesOfExtract(extract, *lastNewLoad, pass);
	nextII = killInstruction(extract, nextII, pass);
	continue;
	}

	// This is a unique projection. Create the new address projection and load.
	lastProj = &proj;
	// Insert new instructions before the original load.
	SILBuilderWithScope LoadBuilder(*loadInst);
	auto *projInst =
	proj.createAddressProjection(LoadBuilder, loadInst->getLoc(),
	loadInst->getOperand(0))
	.get();
	pass.notifyNewInstruction(projInst);

	// When loading a trivial subelement, convert ownership.
	Optional<LoadOwnershipQualifier> loadOwnership =
	loadInst.getOwnershipQualifier();
	if (loadOwnership.hasValue()) {
	if (*loadOwnership != LoadOwnershipQualifier::Unqualified &&
	projInst->getType().isTrivial(*projInst->getFunction()))
	loadOwnership = LoadOwnershipQualifier::Trivial;
	} else {
	if (projInst->getType().isTrivial(*projInst->getFunction()))
	loadOwnership = LoadOwnershipQualifier::Trivial;
	}

	if (loadOwnership) {
	lastNewLoad =
	LoadBuilder.createLoad(loadInst->getLoc(), projInst, *loadOwnership);
	} else {
	lastNewLoad = LoadBuilder.createLoadBorrow(loadInst->getLoc(), projInst);
	}
	pass.notifyNewInstruction(**lastNewLoad);

	if (loadOwnership) {
	if (*loadOwnership == LoadOwnershipQualifier::Copy) {
	// Destroy the loaded value wherever the aggregate load was destroyed.
	assert(loadInst.getOwnershipQualifier() ==
	LoadOwnershipQualifier::Copy);
	for (SILInstruction *destroy : lifetimeEndingInsts) {
	auto *newInst = SILBuilderWithScope(destroy).createDestroyValue(
	destroy->getLoc(), **lastNewLoad);
	pass.notifyNewInstruction(newInst);
	}
	}
	} else {
	for (SILInstruction *destroy : lifetimeEndingInsts) {
	auto *newInst = SILBuilderWithScope(destroy).createEndBorrow(
	destroy->getLoc(), **lastNewLoad);
	pass.notifyNewInstruction(newInst);
	}
	}
	replaceUsesOfExtract(extract, *lastNewLoad, pass);
	nextII = killInstruction(extract, nextII, pass);
	}

	// Remove the now unused borrows.
	for (auto *borrow : borrows)
	nextII = killInstAndIncidentalUses(borrow, nextII, pass);

	// Erase the old load.
	for (auto *destroy : lifetimeEndingInsts)
	nextII = killInstruction(destroy, nextII, pass);

	return killInstAndIncidentalUses(*loadInst, nextII, pass);
	}

	// Given a store within a single property struct, recursively form the parent
	// struct values and promote the store to the outer struct type.
	//
	// (store (struct_element_addr %base) object)
	// ->
	// (store %base (struct object))
	//
	// TODO: supporting enums here would be very easy. The main thing is adding
	// support in `createAggFromFirstLevelProjections`.
	// Note: we will not be able to support tuples because we cannot have a
	// single-element tuple.
	static SILBasicBlock::iterator
	broadenSingleElementStores(StoreInst *storeInst,
	CanonicalizeInstruction &pass) {
	// Keep track of the next iterator after any newly added or to-be-deleted
	// instructions. This must be valid regardless of whether the pass immediately
	// deletes the instructions or simply records them for later deletion.
	auto nextII = std::next(storeInst->getIterator());
	auto *f = storeInst->getFunction();

	ProjectionPath projections(storeInst->getDest()->getType());
	SILValue op = storeInst->getDest();
	while (isa<StructElementAddrInst>(op)) {
	auto *inst = cast<SingleValueInstruction>(op);
	SILValue baseAddr = inst->getOperand(0);
	SILType baseAddrType = baseAddr->getType();
	auto *decl = baseAddrType.getStructOrBoundGenericStruct();
	assert(
	!decl->isResilient(f->getModule().getSwiftModule(),
	f->getResilienceExpansion()) &&
	"This code assumes resilient structs can not have fragile fields. If "
	"this assert is hit, this has been changed. Please update this code.");

	// Bail if the store's destination is not a struct_element_addr or if the
	// store's destination (%base) is not a loadable type. If %base is not a
	// loadable type, we can't create it as a struct later on.
	// If our aggregate has unreferenced storage then we can never prove if it
	// actually has a single field.
	if (!baseAddrType.isLoadable(*f) \|\|
	baseAddrType.aggregateHasUnreferenceableStorage() \|\|
	decl->getStoredProperties().size() != 1)
	break;

	projections.push_back(Projection(inst));
	op = baseAddr;
	}

	// If we couldn't create a projection, bail.
	if (projections.empty())
	return nextII;

	// Now work our way back up. At this point we know all operations we are going
	// to do succeed (cast<SingleValueInst>, createAggFromFirstLevelProjections,
	// etc.) so we can omit null checks. We should not bail at this point (we
	// could create a double consume, or worse).
	SILBuilderWithScope builder(storeInst);
	SILValue result = storeInst->getSrc();
	SILValue storeAddr = storeInst->getDest();
	for (Projection proj : llvm::reverse(projections)) {
	storeAddr = cast<SingleValueInstruction>(storeAddr)->getOperand(0);
	result = proj.createAggFromFirstLevelProjections(
	builder, storeInst->getLoc(),
	storeAddr->getType().getObjectType(), {result})
	.get();
	}

	// Store the new struct-wrapped value into the final base address.
	builder.createStore(storeInst->getLoc(), result, storeAddr,
	storeInst->getOwnershipQualifier());

	// Erase the original store.
	return killInstruction(storeInst, nextII, pass);
	}

	//===----------------------------------------------------------------------===//
	// Simple ARC Peepholes
	//===----------------------------------------------------------------------===//

	static SILBasicBlock::iterator
	eliminateSimpleCopies(CopyValueInst *cvi, CanonicalizeInstruction &pass) {
	auto next = std::next(cvi->getIterator());

	// Eliminate copies that only have destroy_value uses.
	SmallVector<DestroyValueInst *, 8> destroys;
	for (auto *use : getNonDebugUses(cvi)) {
	if (auto *dvi = dyn_cast<DestroyValueInst>(use->getUser())) {
	destroys.push_back(dvi);
	continue;
	}
	return next;
	}

	while (!destroys.empty()) {
	next = killInstruction(destroys.pop_back_val(), next, pass);
	}

	next = killInstAndIncidentalUses(cvi, next, pass);
	return next;
	}

	static SILBasicBlock::iterator
	eliminateSimpleBorrows(BeginBorrowInst *bbi, CanonicalizeInstruction &pass) {
	auto next = std::next(bbi->getIterator());

	// We know that our borrow is completely within the lifetime of its base value
	// if the borrow is never reborrowed. We check for reborrows and do not
	// optimize such cases. Otherwise, we can eliminate our borrow and instead use
	// our operand.
	auto base = bbi->getOperand();
	auto baseOwnership = base.getOwnershipKind();
	SmallVector<EndBorrowInst *, 8> endBorrows;
	for (auto *use : getNonDebugUses(bbi)) {
	if (auto *ebi = dyn_cast<EndBorrowInst>(use->getUser())) {
	endBorrows.push_back(ebi);
	continue;
	}

	// Otherwise, if we have a use that is non-lifetime ending and can accept
	// our base ownership, continue.
	if (!use->isLifetimeEnding() && use->canAcceptKind(baseOwnership))
	continue;

	return next;
	}

	while (!endBorrows.empty()) {
	next = killInstruction(endBorrows.pop_back_val(), next, pass);
	}
	bbi->replaceAllUsesWith(base);
	pass.notifyHasNewUsers(base);
	return killInstruction(bbi, next, pass);
	}

	/// Delete any result having forwarding instruction that only has destroy_value
	/// and debug_value uses.
	static SILBasicBlock::iterator
	eliminateUnneededForwardingUnarySingleValueInst(SingleValueInstruction *inst,
	CanonicalizeInstruction &pass) {
	auto next = std::next(inst->getIterator());

	for (auto *use : getNonDebugUses(inst))
	if (!isa<DestroyValueInst>(use->getUser()))
	return next;
	deleteAllDebugUses(inst);
	SILValue op = inst->getOperand(0);
	inst->replaceAllUsesWith(op);
	pass.notifyHasNewUsers(op);
	return killInstruction(inst, next, pass);
	}

	static Optional<SILBasicBlock::iterator>
	tryEliminateUnneededForwardingInst(SILInstruction *i,
	CanonicalizeInstruction &pass) {
	assert(isa<OwnershipForwardingInst>(i) &&
	"Must be an ownership forwarding inst");
	if (auto *svi = dyn_cast<SingleValueInstruction>(i))
	if (svi->getNumOperands() == 1)
	return eliminateUnneededForwardingUnarySingleValueInst(svi, pass);

	return None;
	}

	//===----------------------------------------------------------------------===//
	// Top-Level Entry Point
	//===----------------------------------------------------------------------===//

	SILBasicBlock::iterator
	CanonicalizeInstruction::canonicalize(SILInstruction *inst) {
	if (auto nextII = simplifyAndReplace(inst, *this))
	return nextII.getValue();

	if (auto li = LoadOperation(inst)) {
	return splitAggregateLoad(li, *this);
	}

	if (auto *storeInst = dyn_cast<StoreInst>(inst)) {
	return broadenSingleElementStores(storeInst, *this);
	}

	if (auto *cvi = dyn_cast<CopyValueInst>(inst))
	return eliminateSimpleCopies(cvi, *this);

	if (auto *bbi = dyn_cast<BeginBorrowInst>(inst))
	return eliminateSimpleBorrows(bbi, *this);

	// If we have ownership and are not in raw SIL, eliminate unneeded forwarding
	// insts. We don't do this in raw SIL as not to disturb the codegen read by
	// diagnostics.
	auto *fn = inst->getFunction();
	if (fn->hasOwnership() && fn->getModule().getStage() != SILStage::Raw) {
	if (isa<OwnershipForwardingInst>(inst))
	if (auto newNext = tryEliminateUnneededForwardingInst(inst, *this))
	return *newNext;
	}

	// Skip ahead.
	return std::next(inst->getIterator());
	}