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/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) {
   // FIXME: temporarily bypass simplification untill all simplifications
   // preserve ownership SIL.
   if (inst->getFunction()->hasOwnership())
     return None;

   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); });

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

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

 // 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,
                                  LoadInst *loadInst,
                                  CanonicalizeInstruction &pass) {
   assert(extract->getType() == loadInst->getType());

   SingleValueInstruction *loadedVal = loadInst;
   if (loadInst->getOwnershipQualifier() == 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(LoadInst *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;
   switch (loadInst->getOwnershipQualifier()) {
   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 SILGenCleanup.
     return nextII;
   }
   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<DestroyValueInst *, 8> destroys;
   for (auto *use : getNonDebugUses(loadInst)) {
     auto *user = use->getUser();
     if (needsBorrow) {
       if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
         destroys.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();
     }
     // 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;
   LoadInst *lastNewLoad = nullptr;
   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())
             .get();
     pass.notifyNewInstruction(projInst);

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

     lastNewLoad =
         LoadBuilder.createLoad(loadInst->getLoc(), projInst, loadOwnership);
     pass.notifyNewInstruction(lastNewLoad);

     if (loadOwnership == LoadOwnershipQualifier::Copy) {
       // Destroy the loaded value wherever the aggregate load was destroyed.
       assert(loadInst->getOwnershipQualifier() == LoadOwnershipQualifier::Copy);
       for (DestroyValueInst *destroy : destroys) {
         SILBuilderWithScope(destroy).createDestroyValue(destroy->getLoc(),
                                                         lastNewLoad);
         pass.notifyNewInstruction(destroy);
       }
     }
     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 : destroys)
     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))
 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());

   // Bail if the store's destination is not a struct_element_addr.
   auto *sea = dyn_cast<StructElementAddrInst>(storeInst->getDest());
   if (!sea)
     return nextII;

   auto *f = storeInst->getFunction();

   // Continue up the struct_element_addr chain, as long as each struct only has
   // a single property, creating StoreInsts along the way.
   SILBuilderWithScope builder(storeInst);

   SILValue result = storeInst->getSrc();
   SILValue baseAddr = sea->getOperand();
   SILValue storeAddr;
   while (true) {
     SILType baseAddrType = baseAddr->getType();

     // If our aggregate has unreferenced storage then we can never prove if it
     // actually has a single field.
     if (baseAddrType.aggregateHasUnreferenceableStorage())
       break;

     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.");

     // NOTE: If this is ever changed to support enums, we must check for address
     // only types here. For structs we do not have to check since a single
     // element struct with a loadable element can never be address only. We
     // additionally do not have to worry about our input value being address
     // only since we are storing into it.
     if (decl->getStoredProperties().size() != 1)
       break;

     // Update the store location now that we know it is safe.
     storeAddr = baseAddr;

     // Otherwise, create the struct.
     result = builder.createStruct(storeInst->getLoc(),
                                   baseAddrType.getObjectType(), result);

     // See if we have another struct_element_addr we can strip off. If we don't
     // then this as much as we can promote.
     sea = dyn_cast<StructElementAddrInst>(sea->getOperand());
     if (!sea)
       break;
     baseAddr = sea->getOperand();
   }
   // If we failed to create any structs, bail.
   if (result == storeInst->getSrc())
     return nextII;

   // 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);
 }

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

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

   if (auto *loadInst = dyn_cast<LoadInst>(inst))
     return splitAggregateLoad(loadInst, *this);

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

   // 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/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) {
	// FIXME: temporarily bypass simplification untill all simplifications
	// preserve ownership SIL.
	if (inst->getFunction()->hasOwnership())
	return None;

	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); });

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

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

	// 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,
	LoadInst *loadInst,
	CanonicalizeInstruction &pass) {
	assert(extract->getType() == loadInst->getType());

	SingleValueInstruction *loadedVal = loadInst;
	if (loadInst->getOwnershipQualifier() == 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(LoadInst *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;
	switch (loadInst->getOwnershipQualifier()) {
	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 SILGenCleanup.
	return nextII;
	}
	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<DestroyValueInst *, 8> destroys;
	for (auto *use : getNonDebugUses(loadInst)) {
	auto *user = use->getUser();
	if (needsBorrow) {
	if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
	destroys.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();
	}
	// 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;
	LoadInst *lastNewLoad = nullptr;
	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())
	.get();
	pass.notifyNewInstruction(projInst);

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

	lastNewLoad =
	LoadBuilder.createLoad(loadInst->getLoc(), projInst, loadOwnership);
	pass.notifyNewInstruction(lastNewLoad);

	if (loadOwnership == LoadOwnershipQualifier::Copy) {
	// Destroy the loaded value wherever the aggregate load was destroyed.
	assert(loadInst->getOwnershipQualifier() == LoadOwnershipQualifier::Copy);
	for (DestroyValueInst *destroy : destroys) {
	SILBuilderWithScope(destroy).createDestroyValue(destroy->getLoc(),
	lastNewLoad);
	pass.notifyNewInstruction(destroy);
	}
	}
	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 : destroys)
	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))
	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());

	// Bail if the store's destination is not a struct_element_addr.
	auto *sea = dyn_cast<StructElementAddrInst>(storeInst->getDest());
	if (!sea)
	return nextII;

	auto *f = storeInst->getFunction();

	// Continue up the struct_element_addr chain, as long as each struct only has
	// a single property, creating StoreInsts along the way.
	SILBuilderWithScope builder(storeInst);

	SILValue result = storeInst->getSrc();
	SILValue baseAddr = sea->getOperand();
	SILValue storeAddr;
	while (true) {
	SILType baseAddrType = baseAddr->getType();

	// If our aggregate has unreferenced storage then we can never prove if it
	// actually has a single field.
	if (baseAddrType.aggregateHasUnreferenceableStorage())
	break;

	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.");

	// NOTE: If this is ever changed to support enums, we must check for address
	// only types here. For structs we do not have to check since a single
	// element struct with a loadable element can never be address only. We
	// additionally do not have to worry about our input value being address
	// only since we are storing into it.
	if (decl->getStoredProperties().size() != 1)
	break;

	// Update the store location now that we know it is safe.
	storeAddr = baseAddr;

	// Otherwise, create the struct.
	result = builder.createStruct(storeInst->getLoc(),
	baseAddrType.getObjectType(), result);

	// See if we have another struct_element_addr we can strip off. If we don't
	// then this as much as we can promote.
	sea = dyn_cast<StructElementAddrInst>(sea->getOperand());
	if (!sea)
	break;
	baseAddr = sea->getOperand();
	}
	// If we failed to create any structs, bail.
	if (result == storeInst->getSrc())
	return nextII;

	// 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);
	}

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

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

	if (auto *loadInst = dyn_cast<LoadInst>(inst))
	return splitAggregateLoad(loadInst, *this);

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

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