lib/LLVMPasses/LLVMARCContract.cpp - third_party/swift - Git at Google

 //===--- LLVMARCContract.cpp ----------------------------------------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 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
 //
 //===----------------------------------------------------------------------===//

 #define DEBUG_TYPE "swift-arc-contract"
 #include "swift/LLVMPasses/Passes.h"
 #include "ARCEntryPointBuilder.h"
 #include "LLVMARCOpts.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"

 using namespace llvm;
 using namespace swift;
 using swift::SwiftARCContract;

 STATISTIC(NumNoopDeleted,
           "Number of no-op swift calls eliminated");
 STATISTIC(NumRetainReleasesEliminatedByMergingIntoRetainReleaseN,
           "Number of retain/release eliminated by merging into "
           "retain_n/release_n");
 STATISTIC(NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN,
           "Number of retain/release eliminated by merging into "
           "unknownObjectRetain_n/unknownObjectRelease_n");
 STATISTIC(NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN,
           "Number of bridge retain/release eliminated by merging into "
           "bridgeRetain_n/bridgeRelease_n");

 /// Pimpl implementation of SwiftARCContractPass.
 namespace {

 struct LocalState {
   TinyPtrVector<CallInst *> RetainList;
   TinyPtrVector<CallInst *> ReleaseList;
   TinyPtrVector<CallInst *> UnknownObjectRetainList;
   TinyPtrVector<CallInst *> UnknownObjectReleaseList;
   TinyPtrVector<CallInst *> BridgeRetainList;
   TinyPtrVector<CallInst *> BridgeReleaseList;
 };

 /// This implements the very late (just before code generation) lowering
 /// processes that we do to expose low level performance optimizations and take
 /// advantage of special features of the ABI.  These expansion steps can foil
 /// the general mid-level optimizer, so they are done very, very, late.
 ///
 /// Optimizations include:
 ///
 ///   - Merging together retain and release calls into retain_n, release_n
 ///   - calls.
 ///
 /// Coming into this function, we assume that the code is in canonical form:
 /// none of these calls have any uses of their return values.
 class SwiftARCContractImpl {
   /// Was a change made while running the optimization.
   bool Changed;

   /// Swift RC Identity.
   SwiftRCIdentity *RC;

   /// The function that we are processing.
   Function &F;

   /// The entry point builder that is used to construct ARC entry points.
   ARCEntryPointBuilder B;
 public:
   SwiftARCContractImpl(Function &InF, SwiftRCIdentity *InRC)
     : Changed(false), RC(InRC), F(InF), B(F) {}

   // The top level run routine of the pass.
   bool run();

 private:
   /// Perform the RRN Optimization given the current state that we are
   /// tracking. This is called at the end of BBs and if we run into an unknown
   /// call.
   void
   performRRNOptimization(DenseMap<Value *, LocalState> &PtrToLocalStateMap);
 };

 } // end anonymous namespace

 // FIXME: This method is pretty long since it is actually several smaller
 // optimizations that have been copied/pasted over time. This should be split
 // into those smaller (currently inline) functions.
 void SwiftARCContractImpl::
 performRRNOptimization(DenseMap<Value *, LocalState> &PtrToLocalStateMap) {
   // Go through all of our pointers and merge all of the retains with the
   // first retain we saw and all of the releases with the last release we saw.
   llvm::Value *O = nullptr;
   for (auto &P : PtrToLocalStateMap) {
     auto &RetainList = P.second.RetainList;
     if (RetainList.size() > 1) {
       // Create the retainN call right by the first retain.
       B.setInsertPoint(RetainList[0]);
       O = RetainList[0]->getArgOperand(0);
       auto *RI = RetainList[0];
       for (auto R : RetainList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       B.createRetainN(RC->getSwiftRCIdentityRoot(O), RetainList.size(), RI);

       // Replace all uses of the retain instructions with our new retainN and
       // then delete them.
       for (auto *Inst : RetainList) {
         Inst->eraseFromParent();
         NumRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     RetainList.clear();

     auto &ReleaseList = P.second.ReleaseList;
     if (ReleaseList.size() > 1) {
       // Create the releaseN call right by the last release.
       auto *OldCI = ReleaseList[ReleaseList.size() - 1];
       B.setInsertPoint(OldCI);
       O = OldCI->getArgOperand(0);
       auto *RI = OldCI;
       for (auto R : ReleaseList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       B.createReleaseN(RC->getSwiftRCIdentityRoot(O), ReleaseList.size(), RI);

       // Remove all old release instructions.
       for (auto *Inst : ReleaseList) {
         Inst->eraseFromParent();
         NumRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     ReleaseList.clear();

     auto &UnknownObjectRetainList = P.second.UnknownObjectRetainList;
     if (UnknownObjectRetainList.size() > 1) {
       // Create the retainN call right by the first retain.
       B.setInsertPoint(UnknownObjectRetainList[0]);
       O = UnknownObjectRetainList[0]->getArgOperand(0);
       auto *RI = UnknownObjectRetainList[0];
       for (auto R : UnknownObjectRetainList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       B.createUnknownObjectRetainN(RC->getSwiftRCIdentityRoot(O),
                                    UnknownObjectRetainList.size(), RI);

       // Replace all uses of the retain instructions with our new retainN and
       // then delete them.
       for (auto *Inst : UnknownObjectRetainList) {
         Inst->eraseFromParent();
         NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     UnknownObjectRetainList.clear();

     auto &UnknownObjectReleaseList = P.second.UnknownObjectReleaseList;
     if (UnknownObjectReleaseList.size() > 1) {
       // Create the releaseN call right by the last release.
       auto *OldCI =
           UnknownObjectReleaseList[UnknownObjectReleaseList.size() - 1];
       B.setInsertPoint(OldCI);
       O = OldCI->getArgOperand(0);
       auto *RI = OldCI;
       for (auto R : UnknownObjectReleaseList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       B.createUnknownObjectReleaseN(RC->getSwiftRCIdentityRoot(O),
                                     UnknownObjectReleaseList.size(), RI);

       // Remove all old release instructions.
       for (auto *Inst : UnknownObjectReleaseList) {
         Inst->eraseFromParent();
         NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     UnknownObjectReleaseList.clear();

     auto &BridgeRetainList = P.second.BridgeRetainList;
     if (BridgeRetainList.size() > 1) {
       // Create the releaseN call right by the first retain.
       auto *OldCI = BridgeRetainList[0];
       B.setInsertPoint(OldCI);
       O = OldCI->getArgOperand(0);
       auto *RI = OldCI;
       for (auto R : BridgeRetainList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       // Bridge retain may modify the input reference before forwarding it.
       auto *I = B.createBridgeRetainN(RC->getSwiftRCIdentityRoot(O),
                                       BridgeRetainList.size(), RI);

       // Remove all old retain instructions.
       for (auto *Inst : BridgeRetainList) {
         // We may need to perform a pointer cast here to ensure that the output
         // type of the retainN matches the output type. This can come up in
         // cases where types have been obfuscated in some way. In such a case,
         // we need the inert point to be at the retain location.
         B.setInsertPoint(Inst);
         Inst->replaceAllUsesWith(B.maybeCast(I, Inst->getType()));
         Inst->eraseFromParent();
         NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     BridgeRetainList.clear();

     auto &BridgeReleaseList = P.second.BridgeReleaseList;
     if (BridgeReleaseList.size() > 1) {
       // Create the releaseN call right by the last release.
       auto *OldCI = BridgeReleaseList[BridgeReleaseList.size() - 1];
       B.setInsertPoint(OldCI);
       O = OldCI->getArgOperand(0);
       auto *RI = OldCI;
       for (auto R : BridgeReleaseList) {
         if (B.isAtomic(R)) {
           RI = R;
           break;
         }
       }
       B.createBridgeReleaseN(RC->getSwiftRCIdentityRoot(O),
                               BridgeReleaseList.size(), RI);

       // Remove all old release instructions.
       for (auto *Inst : BridgeReleaseList) {
         Inst->eraseFromParent();
         NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
       }

       NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
     }
     BridgeReleaseList.clear();
   }
 }


 bool SwiftARCContractImpl::run() {
   // intra-BB retain/release merging.
   DenseMap<Value *, LocalState> PtrToLocalStateMap;
   for (BasicBlock &BB : F) {
     for (auto II = BB.begin(), IE = BB.end(); II != IE; ) {
       // Preincrement iterator to avoid iteration issues in the loop.
       Instruction &Inst = *II++;

       auto Kind = classifyInstruction(Inst);
       switch (Kind) {
       // These instructions should not reach here based on the pass ordering.
       // i.e. LLVMARCOpt -> LLVMContractOpt.
       case RT_RetainN:
       case RT_UnknownObjectRetainN:
       case RT_BridgeRetainN:
       case RT_ReleaseN:
       case RT_UnknownObjectReleaseN:
       case RT_BridgeReleaseN:
         llvm_unreachable("These are only created by LLVMARCContract !");
       // Delete all fix lifetime and end borrow instructions. After llvm-ir they
       // have no use and show up as calls in the final binary.
       case RT_FixLifetime:
       case RT_EndBorrow:
         Inst.eraseFromParent();
         ++NumNoopDeleted;
         continue;
       case RT_Retain: {
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.RetainList.push_back(CI);
         continue;
       }
       case RT_UnknownObjectRetain: {
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.UnknownObjectRetainList.push_back(CI);
         continue;
       }
       case RT_Release: {
         // Stash any releases that we see.
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.ReleaseList.push_back(CI);
         continue;
       }
       case RT_UnknownObjectRelease: {
         // Stash any releases that we see.
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.UnknownObjectReleaseList.push_back(CI);
         continue;
       }
       case RT_BridgeRetain: {
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.BridgeRetainList.push_back(CI);
         continue;
       }
       case RT_BridgeRelease: {
         auto *CI = cast<CallInst>(&Inst);
         auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

         LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
         LocalEntry.BridgeReleaseList.push_back(CI);
         continue;
       }
       case RT_Unknown:
       case RT_AllocObject:
       case RT_NoMemoryAccessed:
       case RT_RetainUnowned:
       case RT_CheckUnowned:
       case RT_ObjCRelease:
       case RT_ObjCRetain:
         break;
       }

       if (Kind != RT_Unknown)
         continue;

       // If we have an unknown call, we need to create any retainN calls we
       // have seen. The reason why is that we do not want to move retains,
       // releases over isUniquelyReferenced calls. Specifically imagine this:
       //
       // retain(x); unknown(x); release(x); isUniquelyReferenced(x); retain(x);
       //
       // In this case we would with this optimization merge the last retain
       // with the first. This would then create an additional copy. The
       // release side of this is:
       //
       // retain(x); unknown(x); release(x); isUniquelyReferenced(x); release(x);
       //
       // Again in such a case by merging the first release with the second
       // release, we would be introducing an additional copy.
       //
       // Thus if we see an unknown call we merge together all retains and
       // releases before. This could be made more aggressive through
       // appropriate alias analysis and usage of LLVM's function attributes to
       // determine that a function does not touch globals.
       performRRNOptimization(PtrToLocalStateMap);
     }

     // Perform the RRNOptimization.
     performRRNOptimization(PtrToLocalStateMap);
     PtrToLocalStateMap.clear();
   }

   return Changed;
 }

 bool SwiftARCContract::runOnFunction(Function &F) {
   RC = &getAnalysis<SwiftRCIdentity>();
   return SwiftARCContractImpl(F, RC).run();
 }

 char SwiftARCContract::ID = 0;
 INITIALIZE_PASS_BEGIN(SwiftARCContract,
                       "swift-arc-contract", "Swift ARC contraction",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(SwiftRCIdentity)
 INITIALIZE_PASS_END(SwiftARCContract,
                     "swift-arc-contract", "Swift ARC contraction",
                     false, false)

 llvm::FunctionPass *swift::createSwiftARCContractPass() {
   initializeSwiftARCContractPass(*llvm::PassRegistry::getPassRegistry());
   return new SwiftARCContract();
 }

 void SwiftARCContract::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
   AU.addRequired<SwiftRCIdentity>();
   AU.setPreservesCFG();
 }
	//===--- LLVMARCContract.cpp ----------------------------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 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
	//
	//===----------------------------------------------------------------------===//

	#define DEBUG_TYPE "swift-arc-contract"
	#include "swift/LLVMPasses/Passes.h"
	#include "ARCEntryPointBuilder.h"
	#include "LLVMARCOpts.h"
	#include "llvm/ADT/TinyPtrVector.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/IR/Verifier.h"
	#include "llvm/Transforms/Utils/SSAUpdater.h"

	using namespace llvm;
	using namespace swift;
	using swift::SwiftARCContract;

	STATISTIC(NumNoopDeleted,
	"Number of no-op swift calls eliminated");
	STATISTIC(NumRetainReleasesEliminatedByMergingIntoRetainReleaseN,
	"Number of retain/release eliminated by merging into "
	"retain_n/release_n");
	STATISTIC(NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN,
	"Number of retain/release eliminated by merging into "
	"unknownObjectRetain_n/unknownObjectRelease_n");
	STATISTIC(NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN,
	"Number of bridge retain/release eliminated by merging into "
	"bridgeRetain_n/bridgeRelease_n");

	/// Pimpl implementation of SwiftARCContractPass.
	namespace {

	struct LocalState {
	TinyPtrVector<CallInst *> RetainList;
	TinyPtrVector<CallInst *> ReleaseList;
	TinyPtrVector<CallInst *> UnknownObjectRetainList;
	TinyPtrVector<CallInst *> UnknownObjectReleaseList;
	TinyPtrVector<CallInst *> BridgeRetainList;
	TinyPtrVector<CallInst *> BridgeReleaseList;
	};

	/// This implements the very late (just before code generation) lowering
	/// processes that we do to expose low level performance optimizations and take
	/// advantage of special features of the ABI. These expansion steps can foil
	/// the general mid-level optimizer, so they are done very, very, late.
	///
	/// Optimizations include:
	///
	/// - Merging together retain and release calls into retain_n, release_n
	/// - calls.
	///
	/// Coming into this function, we assume that the code is in canonical form:
	/// none of these calls have any uses of their return values.
	class SwiftARCContractImpl {
	/// Was a change made while running the optimization.
	bool Changed;

	/// Swift RC Identity.
	SwiftRCIdentity *RC;

	/// The function that we are processing.
	Function &F;

	/// The entry point builder that is used to construct ARC entry points.
	ARCEntryPointBuilder B;
	public:
	SwiftARCContractImpl(Function &InF, SwiftRCIdentity *InRC)
	: Changed(false), RC(InRC), F(InF), B(F) {}

	// The top level run routine of the pass.
	bool run();

	private:
	/// Perform the RRN Optimization given the current state that we are
	/// tracking. This is called at the end of BBs and if we run into an unknown
	/// call.
	void
	performRRNOptimization(DenseMap<Value *, LocalState> &PtrToLocalStateMap);
	};

	} // end anonymous namespace

	// FIXME: This method is pretty long since it is actually several smaller
	// optimizations that have been copied/pasted over time. This should be split
	// into those smaller (currently inline) functions.
	void SwiftARCContractImpl::
	performRRNOptimization(DenseMap<Value *, LocalState> &PtrToLocalStateMap) {
	// Go through all of our pointers and merge all of the retains with the
	// first retain we saw and all of the releases with the last release we saw.
	llvm::Value *O = nullptr;
	for (auto &P : PtrToLocalStateMap) {
	auto &RetainList = P.second.RetainList;
	if (RetainList.size() > 1) {
	// Create the retainN call right by the first retain.
	B.setInsertPoint(RetainList[0]);
	O = RetainList[0]->getArgOperand(0);
	auto *RI = RetainList[0];
	for (auto R : RetainList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	B.createRetainN(RC->getSwiftRCIdentityRoot(O), RetainList.size(), RI);

	// Replace all uses of the retain instructions with our new retainN and
	// then delete them.
	for (auto *Inst : RetainList) {
	Inst->eraseFromParent();
	NumRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	RetainList.clear();

	auto &ReleaseList = P.second.ReleaseList;
	if (ReleaseList.size() > 1) {
	// Create the releaseN call right by the last release.
	auto *OldCI = ReleaseList[ReleaseList.size() - 1];
	B.setInsertPoint(OldCI);
	O = OldCI->getArgOperand(0);
	auto *RI = OldCI;
	for (auto R : ReleaseList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	B.createReleaseN(RC->getSwiftRCIdentityRoot(O), ReleaseList.size(), RI);

	// Remove all old release instructions.
	for (auto *Inst : ReleaseList) {
	Inst->eraseFromParent();
	NumRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	ReleaseList.clear();

	auto &UnknownObjectRetainList = P.second.UnknownObjectRetainList;
	if (UnknownObjectRetainList.size() > 1) {
	// Create the retainN call right by the first retain.
	B.setInsertPoint(UnknownObjectRetainList[0]);
	O = UnknownObjectRetainList[0]->getArgOperand(0);
	auto *RI = UnknownObjectRetainList[0];
	for (auto R : UnknownObjectRetainList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	B.createUnknownObjectRetainN(RC->getSwiftRCIdentityRoot(O),
	UnknownObjectRetainList.size(), RI);

	// Replace all uses of the retain instructions with our new retainN and
	// then delete them.
	for (auto *Inst : UnknownObjectRetainList) {
	Inst->eraseFromParent();
	NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	UnknownObjectRetainList.clear();

	auto &UnknownObjectReleaseList = P.second.UnknownObjectReleaseList;
	if (UnknownObjectReleaseList.size() > 1) {
	// Create the releaseN call right by the last release.
	auto *OldCI =
	UnknownObjectReleaseList[UnknownObjectReleaseList.size() - 1];
	B.setInsertPoint(OldCI);
	O = OldCI->getArgOperand(0);
	auto *RI = OldCI;
	for (auto R : UnknownObjectReleaseList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	B.createUnknownObjectReleaseN(RC->getSwiftRCIdentityRoot(O),
	UnknownObjectReleaseList.size(), RI);

	// Remove all old release instructions.
	for (auto *Inst : UnknownObjectReleaseList) {
	Inst->eraseFromParent();
	NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumUnknownObjectRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	UnknownObjectReleaseList.clear();

	auto &BridgeRetainList = P.second.BridgeRetainList;
	if (BridgeRetainList.size() > 1) {
	// Create the releaseN call right by the first retain.
	auto *OldCI = BridgeRetainList[0];
	B.setInsertPoint(OldCI);
	O = OldCI->getArgOperand(0);
	auto *RI = OldCI;
	for (auto R : BridgeRetainList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	// Bridge retain may modify the input reference before forwarding it.
	auto *I = B.createBridgeRetainN(RC->getSwiftRCIdentityRoot(O),
	BridgeRetainList.size(), RI);

	// Remove all old retain instructions.
	for (auto *Inst : BridgeRetainList) {
	// We may need to perform a pointer cast here to ensure that the output
	// type of the retainN matches the output type. This can come up in
	// cases where types have been obfuscated in some way. In such a case,
	// we need the inert point to be at the retain location.
	B.setInsertPoint(Inst);
	Inst->replaceAllUsesWith(B.maybeCast(I, Inst->getType()));
	Inst->eraseFromParent();
	NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	BridgeRetainList.clear();

	auto &BridgeReleaseList = P.second.BridgeReleaseList;
	if (BridgeReleaseList.size() > 1) {
	// Create the releaseN call right by the last release.
	auto *OldCI = BridgeReleaseList[BridgeReleaseList.size() - 1];
	B.setInsertPoint(OldCI);
	O = OldCI->getArgOperand(0);
	auto *RI = OldCI;
	for (auto R : BridgeReleaseList) {
	if (B.isAtomic(R)) {
	RI = R;
	break;
	}
	}
	B.createBridgeReleaseN(RC->getSwiftRCIdentityRoot(O),
	BridgeReleaseList.size(), RI);

	// Remove all old release instructions.
	for (auto *Inst : BridgeReleaseList) {
	Inst->eraseFromParent();
	NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN++;
	}

	NumBridgeRetainReleasesEliminatedByMergingIntoRetainReleaseN--;
	}
	BridgeReleaseList.clear();
	}
	}


	bool SwiftARCContractImpl::run() {
	// intra-BB retain/release merging.
	DenseMap<Value *, LocalState> PtrToLocalStateMap;
	for (BasicBlock &BB : F) {
	for (auto II = BB.begin(), IE = BB.end(); II != IE; ) {
	// Preincrement iterator to avoid iteration issues in the loop.
	Instruction &Inst = *II++;

	auto Kind = classifyInstruction(Inst);
	switch (Kind) {
	// These instructions should not reach here based on the pass ordering.
	// i.e. LLVMARCOpt -> LLVMContractOpt.
	case RT_RetainN:
	case RT_UnknownObjectRetainN:
	case RT_BridgeRetainN:
	case RT_ReleaseN:
	case RT_UnknownObjectReleaseN:
	case RT_BridgeReleaseN:
	llvm_unreachable("These are only created by LLVMARCContract !");
	// Delete all fix lifetime and end borrow instructions. After llvm-ir they
	// have no use and show up as calls in the final binary.
	case RT_FixLifetime:
	case RT_EndBorrow:
	Inst.eraseFromParent();
	++NumNoopDeleted;
	continue;
	case RT_Retain: {
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.RetainList.push_back(CI);
	continue;
	}
	case RT_UnknownObjectRetain: {
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.UnknownObjectRetainList.push_back(CI);
	continue;
	}
	case RT_Release: {
	// Stash any releases that we see.
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.ReleaseList.push_back(CI);
	continue;
	}
	case RT_UnknownObjectRelease: {
	// Stash any releases that we see.
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.UnknownObjectReleaseList.push_back(CI);
	continue;
	}
	case RT_BridgeRetain: {
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.BridgeRetainList.push_back(CI);
	continue;
	}
	case RT_BridgeRelease: {
	auto *CI = cast<CallInst>(&Inst);
	auto *ArgVal = RC->getSwiftRCIdentityRoot(CI->getArgOperand(0));

	LocalState &LocalEntry = PtrToLocalStateMap[ArgVal];
	LocalEntry.BridgeReleaseList.push_back(CI);
	continue;
	}
	case RT_Unknown:
	case RT_AllocObject:
	case RT_NoMemoryAccessed:
	case RT_RetainUnowned:
	case RT_CheckUnowned:
	case RT_ObjCRelease:
	case RT_ObjCRetain:
	break;
	}

	if (Kind != RT_Unknown)
	continue;

	// If we have an unknown call, we need to create any retainN calls we
	// have seen. The reason why is that we do not want to move retains,
	// releases over isUniquelyReferenced calls. Specifically imagine this:
	//
	// retain(x); unknown(x); release(x); isUniquelyReferenced(x); retain(x);
	//
	// In this case we would with this optimization merge the last retain
	// with the first. This would then create an additional copy. The
	// release side of this is:
	//
	// retain(x); unknown(x); release(x); isUniquelyReferenced(x); release(x);
	//
	// Again in such a case by merging the first release with the second
	// release, we would be introducing an additional copy.
	//
	// Thus if we see an unknown call we merge together all retains and
	// releases before. This could be made more aggressive through
	// appropriate alias analysis and usage of LLVM's function attributes to
	// determine that a function does not touch globals.
	performRRNOptimization(PtrToLocalStateMap);
	}

	// Perform the RRNOptimization.
	performRRNOptimization(PtrToLocalStateMap);
	PtrToLocalStateMap.clear();
	}

	return Changed;
	}

	bool SwiftARCContract::runOnFunction(Function &F) {
	RC = &getAnalysis<SwiftRCIdentity>();
	return SwiftARCContractImpl(F, RC).run();
	}

	char SwiftARCContract::ID = 0;
	INITIALIZE_PASS_BEGIN(SwiftARCContract,
	"swift-arc-contract", "Swift ARC contraction",
	false, false)
	INITIALIZE_PASS_DEPENDENCY(SwiftRCIdentity)
	INITIALIZE_PASS_END(SwiftARCContract,
	"swift-arc-contract", "Swift ARC contraction",
	false, false)

	llvm::FunctionPass *swift::createSwiftARCContractPass() {
	initializeSwiftARCContractPass(*llvm::PassRegistry::getPassRegistry());
	return new SwiftARCContract();
	}

	void SwiftARCContract::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
	AU.addRequired<SwiftRCIdentity>();
	AU.setPreservesCFG();
	}