lib/SILOptimizer/ARC/GlobalARCPairingAnalysis.cpp - third_party/swift - Git at Google

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

 #define DEBUG_TYPE "arc-sequence-opts"
 #include "GlobalARCPairingAnalysis.h"
 #include "RefCountState.h"
 #include "GlobalARCSequenceDataflow.h"
 #include "GlobalLoopARCSequenceDataflow.h"
 #include "swift/Basic/BlotMapVector.h"
 #include "swift/Basic/Fallthrough.h"
 #include "swift/SIL/SILBuilder.h"
 #include "swift/SIL/SILVisitor.h"
 #include "swift/SILOptimizer/Utils/Local.h"
 #include "swift/SILOptimizer/PassManager/Transforms.h"
 #include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
 #include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
 #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
 #include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/CommandLine.h"

 using namespace swift;

 //===----------------------------------------------------------------------===//
 //                          ARC Matching Set Builder
 //===----------------------------------------------------------------------===//

 namespace {

 struct MatchingSetFlags {
   bool KnownSafe;
   bool Partial;
 };
 static_assert(std::is_pod<MatchingSetFlags>::value,
               "MatchingSetFlags should be a pod.");

 struct ARCMatchingSetBuilder {
   using TDMapTy = BlotMapVector<SILInstruction *, TopDownRefCountState>;
   using BUMapTy = BlotMapVector<SILInstruction *, BottomUpRefCountState>;

   TDMapTy &TDMap;
   BUMapTy &BUMap;

   llvm::SmallVector<SILInstruction *, 8> NewIncrements;
   llvm::SmallVector<SILInstruction *, 8> NewDecrements;
   bool MatchedPair;
   ARCMatchingSet MatchSet;
   bool PtrIsGuaranteedArg;

   RCIdentityFunctionInfo *RCIA;

 public:
   ARCMatchingSetBuilder(TDMapTy &TDMap, BUMapTy &BUMap,
                         RCIdentityFunctionInfo *RCIA)
     : TDMap(TDMap), BUMap(BUMap), MatchedPair(false),
       PtrIsGuaranteedArg(false), RCIA(RCIA) {}

   void init(SILInstruction *Inst) {
     clear();
     MatchSet.Ptr = RCIA->getRCIdentityRoot(Inst->getOperand(0));

     // If we have a function argument that is guaranteed, set the guaranteed
     // flag so we know that it is always known safe.
     if (auto *A = dyn_cast<SILArgument>(MatchSet.Ptr)) {
       if (A->isFunctionArg()) {
         auto C = A->getParameterInfo().getConvention();
         PtrIsGuaranteedArg = C == ParameterConvention::Direct_Guaranteed;
       }
     }
     NewIncrements.push_back(Inst);
   }

   void clear() {
     MatchSet.clear();
     MatchedPair = false;
     NewIncrements.clear();
     NewDecrements.clear();
   }

   bool matchUpIncDecSetsForPtr();

   // We only allow for get result when this object is invalidated via a move.
   ARCMatchingSet &getResult() {
     return MatchSet;
   }

   bool matchedPair() const { return MatchedPair; }

 private:
   /// Returns .Some(MatchingSetFlags) on success and .None on failure.
   Optional<MatchingSetFlags> matchIncrementsToDecrements();
   Optional<MatchingSetFlags> matchDecrementsToIncrements();
 };

 } // end anonymous namespace

 /// Match retains to releases and return whether or not all of the releases
 /// were known safe.
 Optional<MatchingSetFlags>
 ARCMatchingSetBuilder::matchIncrementsToDecrements() {
   MatchingSetFlags Flags = { true, false };

   // For each increment in our list of new increments.
   //
   // FIXME: Refactor this into its own function.
   for (SILInstruction *Increment : NewIncrements) {
     DEBUG(llvm::dbgs() << "    Looking up state for increment: " << *Increment);

     auto BURefCountState = BUMap.find(Increment);
     assert(BURefCountState != BUMap.end() && "Catch this on debug builds.");
     if (BURefCountState == BUMap.end()) {
       DEBUG(llvm::dbgs() << "        FAILURE! Could not find state for "
             "increment!\n");
       return None;
     }

     DEBUG(llvm::dbgs() << "        SUCCESS! Found state for increment.\n");

     // If we are not tracking a ref count inst for this increment, there is
     // nothing we can pair it with implying we should skip it.
     if (!(*BURefCountState)->second.isTrackingRefCountInst()) {
       DEBUG(llvm::dbgs() << "    SKIPPING INCREMENT! State not tracking any "
             "instruction.\n");
       continue;
     }

     // We need to be known safe over all increments/decrements we are matching up
     // to ignore insertion points.
     bool BUIsKnownSafe = (*BURefCountState)->second.isKnownSafe();
     DEBUG(llvm::dbgs() << "        KNOWNSAFE: "
                        << (BUIsKnownSafe ? "true" : "false") << "\n");
     Flags.KnownSafe &= BUIsKnownSafe;

     // We can only move instructions if we know that we are not partial. We can
     // still delete instructions in such cases though.
     bool BUIsPartial = (*BURefCountState)->second.isPartial();
     DEBUG(llvm::dbgs() << "        PARTIAL: "
                        << (BUIsPartial ? "true" : "false") << "\n");
     Flags.Partial |= BUIsPartial;

     // Now that we know we have an inst, grab the decrement.
     for (auto DecIter : (*BURefCountState)->second.getInstructions()) {
       SILInstruction *Decrement = DecIter;
       DEBUG(llvm::dbgs() << "        Decrement: " << *Decrement);

       // Now grab the increment matched up with the decrement from the bottom up map.
       // If we can't find it, bail we can't match this increment up with anything.
       auto TDRefCountState = TDMap.find(Decrement);
       if (TDRefCountState == TDMap.end()) {
         DEBUG(llvm::dbgs() << "            FAILURE! Could not find state for "
                               "decrement.\n");
         return None;
       }
       DEBUG(llvm::dbgs() << "            SUCCESS! Found state for "
                             "decrement.\n");

       // Make sure the increment we are looking at is also matched to our decrement.
       // Otherwise bail.
       if (!(*TDRefCountState)->second.isTrackingRefCountInst() ||
           !(*TDRefCountState)->second.containsInstruction(Increment)) {
         DEBUG(
             llvm::dbgs() << "            FAILURE! Not tracking instruction or "
                             "found increment that did not match.\n");
         return None;
       }

       // Add the decrement to the decrement to move set. If we don't insert
       // anything, just continue.
       if (!MatchSet.Decrements.insert(Decrement)) {
         DEBUG(llvm::dbgs()
               << "        SKIPPING! Already processed this decrement\n");
         continue;
       }

       // Collect the increment insertion point if it has one.
       for (auto InsertPt : (*TDRefCountState)->second.getInsertPts()) {
         MatchSet.IncrementInsertPts.insert(InsertPt);
       }
       NewDecrements.push_back(Decrement);
     }
   }

   return Flags;
 }

 Optional<MatchingSetFlags>
 ARCMatchingSetBuilder::matchDecrementsToIncrements() {
   MatchingSetFlags Flags = { true, false };

   // For each increment in our list of new increments.
   //
   // FIXME: Refactor this into its own function.
   for (SILInstruction *Decrement : NewDecrements) {
     DEBUG(llvm::dbgs() << "    Looking up state for decrement: " << *Decrement);

     auto TDRefCountState = TDMap.find(Decrement);
     assert(TDRefCountState != TDMap.end() && "Catch this on debug builds.");
     if (TDRefCountState == TDMap.end()) {
       DEBUG(llvm::dbgs() << "        FAILURE! Could not find state for "
             "increment!\n");
       return None;
     }

     DEBUG(llvm::dbgs() << "        SUCCESS! Found state for decrement.\n");

     // If we are not tracking a ref count inst for this increment, there is
     // nothing we can pair it with implying we should skip it.
     if (!(*TDRefCountState)->second.isTrackingRefCountInst()) {
       DEBUG(llvm::dbgs() << "    SKIPPING DECREMENT! State not tracking any "
             "instruction.\n");
       continue;
     }

     // We need to be known safe over all increments/decrements we are matching up
     // to ignore insertion points.
     bool TDIsKnownSafe = (*TDRefCountState)->second.isKnownSafe();
     DEBUG(llvm::dbgs() << "        KNOWNSAFE: "
                        << (TDIsKnownSafe ? "true" : "false") << "\n");
     Flags.KnownSafe &= TDIsKnownSafe;

     // We can only move instructions if we know that we are not partial. We can
     // still delete instructions in such cases though.
     bool TDIsPartial = (*TDRefCountState)->second.isPartial();
     DEBUG(llvm::dbgs() << "        PARTIAL: "
                        << (TDIsPartial ? "true" : "false") << "\n");
     Flags.Partial |= TDIsPartial;

     // Now that we know we have an inst, grab the decrement.
     for (auto IncIter : (*TDRefCountState)->second.getInstructions()) {
       SILInstruction *Increment = IncIter;
       DEBUG(llvm::dbgs() << "        Increment: " << *Increment);

       // Now grab the increment matched up with the decrement from the bottom up map.
       // If we can't find it, bail we can't match this increment up with anything.
       auto BURefCountState = BUMap.find(Increment);
       if (BURefCountState == BUMap.end()) {
         DEBUG(llvm::dbgs() << "            FAILURE! Could not find state for "
                               "increment.\n");
         return None;
       }

       DEBUG(
           llvm::dbgs() << "            SUCCESS! Found state for increment.\n");

       // Make sure the increment we are looking at is also matched to our decrement.
       // Otherwise bail.
       if (!(*BURefCountState)->second.isTrackingRefCountInst() ||
           !(*BURefCountState)->second.containsInstruction(Decrement)) {
         DEBUG(
             llvm::dbgs() << "            FAILURE! Not tracking instruction or "
                             "found increment that did not match.\n");
         return None;
       }

       // Add the decrement to the decrement to move set. If we don't insert
       // anything, just continue.
       if (!MatchSet.Increments.insert(Increment)) {
         DEBUG(llvm::dbgs() << "    SKIPPING! Already processed this increment.\n");
         continue;
       }

       // Collect the decrement insertion point if we have one.
       for (auto InsertPtIter : (*BURefCountState)->second.getInsertPts()) {
         MatchSet.DecrementInsertPts.insert(InsertPtIter);
       }
       NewIncrements.push_back(Increment);
     }
   }

   return Flags;
 }

 /// Visit each retain/release that is matched up to our operand over and over
 /// again until we converge by not adding any more to the set which we can move.
 /// If we find a situation that we cannot handle, we bail and return false. If
 /// we succeed and it is safe to move increment/releases, we return true.
 bool ARCMatchingSetBuilder::matchUpIncDecSetsForPtr() {
   bool KnownSafeTD = true;
   bool KnownSafeBU = true;
   bool Partial = false;

   while (true) {
     DEBUG(llvm::dbgs() << "Attempting to match up increments -> decrements:\n");
     // For each increment in our list of new increments, attempt to match them up
     // with decrements and gather the insertion points of the decrements.
     auto Result = matchIncrementsToDecrements();
     if (!Result) {
       DEBUG(llvm::dbgs() << "    FAILED TO MATCH INCREMENTS -> DECREMENTS!\n");
       return false;
     }
     if (!Result->KnownSafe) {
       DEBUG(llvm::dbgs() << "    NOT KNOWN SAFE!\n");
       KnownSafeTD = false;
     }
     if (Result->Partial) {
       DEBUG(llvm::dbgs() << "    IS PARTIAL!\n");
       Partial = true;
     }
     NewIncrements.clear();

     // If we do not have any decrements to attempt to match up with, bail.
     if (NewDecrements.empty())
       break;

     DEBUG(llvm::dbgs() << "Attempting to match up decrements -> increments:\n");
     Result = matchDecrementsToIncrements();
     if (!Result) {
       DEBUG(llvm::dbgs() << "    FAILED TO MATCH DECREMENTS -> INCREMENTS!\n");
       return false;
     }
     if (!Result->KnownSafe) {
       DEBUG(llvm::dbgs() << "    NOT KNOWN SAFE!\n");
       KnownSafeBU = false;
     }
     if (Result->Partial) {
       DEBUG(llvm::dbgs() << "    IS PARTIAL!\n");
       Partial = true;
     }
     NewDecrements.clear();

     // If we do not have any increment to attempt to match up with again, bail.
     if (NewIncrements.empty())
       break;
   }

   bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU);
   if (UnconditionallySafe) {
     DEBUG(llvm::dbgs() << "UNCONDITIONALLY SAFE! DELETING INSTS.\n");
     MatchSet.IncrementInsertPts.clear();
     MatchSet.DecrementInsertPts.clear();
   } else {
     DEBUG(llvm::dbgs() << "NOT UNCONDITIONALLY SAFE!\n");

   }

   bool HaveIncInsertPts = !MatchSet.IncrementInsertPts.empty();
   bool HaveDecInsertPts = !MatchSet.DecrementInsertPts.empty();

   // If we have insertion points and partial merges, return false to avoid
   // control dependency issues.
   if ((HaveIncInsertPts || HaveDecInsertPts) && Partial) {
     DEBUG(llvm::dbgs() << "Found partial merge and insert pts. Bailing!\n");
     return false;
   }

   // If we have insertion points for increments, but not for decrements (or
   // vis-a-versa), return false. This prevents us from inserting retains and
   // removing releases or vis-a-versa.
   if (HaveIncInsertPts != HaveDecInsertPts)
     return false;

   // If we do not have any insertion points but we do have increments, we must
   // be eliminating pairs.
   if (!HaveIncInsertPts && !MatchSet.Increments.empty())
     MatchedPair = true;

   // Success!
   DEBUG(llvm::dbgs() << "SUCCESS! We can move, remove things.\n");
   return true;
 }

 //===----------------------------------------------------------------------===//
 //                            ARC Pairing Context
 //===----------------------------------------------------------------------===//

 bool ARCPairingContext::performMatching(CodeMotionOrDeleteCallback &Callback) {
   bool MatchedPair = false;

   DEBUG(llvm::dbgs() << "**** Computing ARC Matching Sets for " << F.getName()
                      << " ****\n");

   /// For each increment that we matched to a decrement, try to match it to a
   /// decrement -> increment pair.
   for (auto Pair : IncToDecStateMap) {
     if (!Pair.hasValue())
       continue;

     SILInstruction *Increment = Pair->first;
     if (!Increment)
       continue; // blotted

     DEBUG(llvm::dbgs() << "Constructing Matching Set For: " << *Increment);
     ARCMatchingSetBuilder Builder(DecToIncStateMap, IncToDecStateMap, RCIA);
     Builder.init(Increment);
     if (Builder.matchUpIncDecSetsForPtr()) {
       MatchedPair |= Builder.matchedPair();
       auto &Set = Builder.getResult();
       for (auto *I : Set.Increments)
         IncToDecStateMap.blot(I);
       for (auto *I : Set.Decrements)
         DecToIncStateMap.blot(I);

       // Add the Set to the callback. *NOTE* No instruction destruction can
       // happen here since we may remove instructions that are insertion points
       // for other instructions.
       Callback.processMatchingSet(Set);
     }
   }

   // Then finalize the callback. This is the only place instructions can be
   // deleted.
   Callback.finalize();
   return MatchedPair;
 }

 //===----------------------------------------------------------------------===//
 //                                  Loop ARC
 //===----------------------------------------------------------------------===//

 void LoopARCPairingContext::runOnLoop(SILLoop *L) {
   auto *Region = LRFI->getRegion(L);
   if (processRegion(Region, false, false)) {
     // We do not recompute for now since we only look at the top function level
     // for post dominating releases.
     processRegion(Region, true, false);
   }

   // Now that we have finished processing the loop, summarize the loop.
   Evaluator.summarizeLoop(Region);
 }

 void LoopARCPairingContext::runOnFunction(SILFunction *F) {
   if (processRegion(LRFI->getTopLevelRegion(), false, false)) {
     // We recompute the final post dom release since we may have moved the final
     // post dominated releases.
     processRegion(LRFI->getTopLevelRegion(), true, true);
   }
 }

 bool LoopARCPairingContext::processRegion(const LoopRegion *Region,
                                           bool FreezePostDomReleases,
                                           bool RecomputePostDomReleases) {
   bool MadeChange = false;
   bool NestingDetected = Evaluator.runOnLoop(Region, FreezePostDomReleases,
                                              RecomputePostDomReleases);
   bool MatchedPair = Context.performMatching(Callback);
   MadeChange |= MatchedPair;
   Evaluator.clearLoopState(Region);
   Context.DecToIncStateMap.clear();
   Context.IncToDecStateMap.clear();

   while (NestingDetected && MatchedPair) {
     NestingDetected = Evaluator.runOnLoop(Region, FreezePostDomReleases, false);
     MatchedPair = Context.performMatching(Callback);
     MadeChange |= MatchedPair;
     Evaluator.clearLoopState(Region);
     Context.DecToIncStateMap.clear();
     Context.IncToDecStateMap.clear();
   }

   return MadeChange;
 }
	//===--- GlobalARCPairingAnalysis.cpp - Global ARC Retain Release Pairing -===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See http://swift.org/LICENSE.txt for license information
	// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	#define DEBUG_TYPE "arc-sequence-opts"
	#include "GlobalARCPairingAnalysis.h"
	#include "RefCountState.h"
	#include "GlobalARCSequenceDataflow.h"
	#include "GlobalLoopARCSequenceDataflow.h"
	#include "swift/Basic/BlotMapVector.h"
	#include "swift/Basic/Fallthrough.h"
	#include "swift/SIL/SILBuilder.h"
	#include "swift/SIL/SILVisitor.h"
	#include "swift/SILOptimizer/Utils/Local.h"
	#include "swift/SILOptimizer/PassManager/Transforms.h"
	#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
	#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
	#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
	#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
	#include "llvm/ADT/PointerUnion.h"
	#include "llvm/ADT/SmallPtrSet.h"
	#include "llvm/ADT/MapVector.h"
	#include "llvm/ADT/StringSwitch.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/Support/CommandLine.h"

	using namespace swift;

	//===----------------------------------------------------------------------===//
	// ARC Matching Set Builder
	//===----------------------------------------------------------------------===//

	namespace {

	struct MatchingSetFlags {
	bool KnownSafe;
	bool Partial;
	};
	static_assert(std::is_pod<MatchingSetFlags>::value,
	"MatchingSetFlags should be a pod.");

	struct ARCMatchingSetBuilder {
	using TDMapTy = BlotMapVector<SILInstruction *, TopDownRefCountState>;
	using BUMapTy = BlotMapVector<SILInstruction *, BottomUpRefCountState>;

	TDMapTy &TDMap;
	BUMapTy &BUMap;

	llvm::SmallVector<SILInstruction *, 8> NewIncrements;
	llvm::SmallVector<SILInstruction *, 8> NewDecrements;
	bool MatchedPair;
	ARCMatchingSet MatchSet;
	bool PtrIsGuaranteedArg;

	RCIdentityFunctionInfo *RCIA;

	public:
	ARCMatchingSetBuilder(TDMapTy &TDMap, BUMapTy &BUMap,
	RCIdentityFunctionInfo *RCIA)
	: TDMap(TDMap), BUMap(BUMap), MatchedPair(false),
	PtrIsGuaranteedArg(false), RCIA(RCIA) {}

	void init(SILInstruction *Inst) {
	clear();
	MatchSet.Ptr = RCIA->getRCIdentityRoot(Inst->getOperand(0));

	// If we have a function argument that is guaranteed, set the guaranteed
	// flag so we know that it is always known safe.
	if (auto *A = dyn_cast<SILArgument>(MatchSet.Ptr)) {
	if (A->isFunctionArg()) {
	auto C = A->getParameterInfo().getConvention();
	PtrIsGuaranteedArg = C == ParameterConvention::Direct_Guaranteed;
	}
	}
	NewIncrements.push_back(Inst);
	}

	void clear() {
	MatchSet.clear();
	MatchedPair = false;
	NewIncrements.clear();
	NewDecrements.clear();
	}

	bool matchUpIncDecSetsForPtr();

	// We only allow for get result when this object is invalidated via a move.
	ARCMatchingSet &getResult() {
	return MatchSet;
	}

	bool matchedPair() const { return MatchedPair; }

	private:
	/// Returns .Some(MatchingSetFlags) on success and .None on failure.
	Optional<MatchingSetFlags> matchIncrementsToDecrements();
	Optional<MatchingSetFlags> matchDecrementsToIncrements();
	};

	} // end anonymous namespace

	/// Match retains to releases and return whether or not all of the releases
	/// were known safe.
	Optional<MatchingSetFlags>
	ARCMatchingSetBuilder::matchIncrementsToDecrements() {
	MatchingSetFlags Flags = { true, false };

	// For each increment in our list of new increments.
	//
	// FIXME: Refactor this into its own function.
	for (SILInstruction *Increment : NewIncrements) {
	DEBUG(llvm::dbgs() << " Looking up state for increment: " << *Increment);

	auto BURefCountState = BUMap.find(Increment);
	assert(BURefCountState != BUMap.end() && "Catch this on debug builds.");
	if (BURefCountState == BUMap.end()) {
	DEBUG(llvm::dbgs() << " FAILURE! Could not find state for "
	"increment!\n");
	return None;
	}

	DEBUG(llvm::dbgs() << " SUCCESS! Found state for increment.\n");

	// If we are not tracking a ref count inst for this increment, there is
	// nothing we can pair it with implying we should skip it.
	if (!(*BURefCountState)->second.isTrackingRefCountInst()) {
	DEBUG(llvm::dbgs() << " SKIPPING INCREMENT! State not tracking any "
	"instruction.\n");
	continue;
	}

	// We need to be known safe over all increments/decrements we are matching up
	// to ignore insertion points.
	bool BUIsKnownSafe = (*BURefCountState)->second.isKnownSafe();
	DEBUG(llvm::dbgs() << " KNOWNSAFE: "
	<< (BUIsKnownSafe ? "true" : "false") << "\n");
	Flags.KnownSafe &= BUIsKnownSafe;

	// We can only move instructions if we know that we are not partial. We can
	// still delete instructions in such cases though.
	bool BUIsPartial = (*BURefCountState)->second.isPartial();
	DEBUG(llvm::dbgs() << " PARTIAL: "
	<< (BUIsPartial ? "true" : "false") << "\n");
	Flags.Partial \|= BUIsPartial;

	// Now that we know we have an inst, grab the decrement.
	for (auto DecIter : (*BURefCountState)->second.getInstructions()) {
	SILInstruction *Decrement = DecIter;
	DEBUG(llvm::dbgs() << " Decrement: " << *Decrement);

	// Now grab the increment matched up with the decrement from the bottom up map.
	// If we can't find it, bail we can't match this increment up with anything.
	auto TDRefCountState = TDMap.find(Decrement);
	if (TDRefCountState == TDMap.end()) {
	DEBUG(llvm::dbgs() << " FAILURE! Could not find state for "
	"decrement.\n");
	return None;
	}
	DEBUG(llvm::dbgs() << " SUCCESS! Found state for "
	"decrement.\n");

	// Make sure the increment we are looking at is also matched to our decrement.
	// Otherwise bail.
	if (!(*TDRefCountState)->second.isTrackingRefCountInst() \|\|
	!(*TDRefCountState)->second.containsInstruction(Increment)) {
	DEBUG(
	llvm::dbgs() << " FAILURE! Not tracking instruction or "
	"found increment that did not match.\n");
	return None;
	}

	// Add the decrement to the decrement to move set. If we don't insert
	// anything, just continue.
	if (!MatchSet.Decrements.insert(Decrement)) {
	DEBUG(llvm::dbgs()
	<< " SKIPPING! Already processed this decrement\n");
	continue;
	}

	// Collect the increment insertion point if it has one.
	for (auto InsertPt : (*TDRefCountState)->second.getInsertPts()) {
	MatchSet.IncrementInsertPts.insert(InsertPt);
	}
	NewDecrements.push_back(Decrement);
	}
	}

	return Flags;
	}

	Optional<MatchingSetFlags>
	ARCMatchingSetBuilder::matchDecrementsToIncrements() {
	MatchingSetFlags Flags = { true, false };

	// For each increment in our list of new increments.
	//
	// FIXME: Refactor this into its own function.
	for (SILInstruction *Decrement : NewDecrements) {
	DEBUG(llvm::dbgs() << " Looking up state for decrement: " << *Decrement);

	auto TDRefCountState = TDMap.find(Decrement);
	assert(TDRefCountState != TDMap.end() && "Catch this on debug builds.");
	if (TDRefCountState == TDMap.end()) {
	DEBUG(llvm::dbgs() << " FAILURE! Could not find state for "
	"increment!\n");
	return None;
	}

	DEBUG(llvm::dbgs() << " SUCCESS! Found state for decrement.\n");

	// If we are not tracking a ref count inst for this increment, there is
	// nothing we can pair it with implying we should skip it.
	if (!(*TDRefCountState)->second.isTrackingRefCountInst()) {
	DEBUG(llvm::dbgs() << " SKIPPING DECREMENT! State not tracking any "
	"instruction.\n");
	continue;
	}

	// We need to be known safe over all increments/decrements we are matching up
	// to ignore insertion points.
	bool TDIsKnownSafe = (*TDRefCountState)->second.isKnownSafe();
	DEBUG(llvm::dbgs() << " KNOWNSAFE: "
	<< (TDIsKnownSafe ? "true" : "false") << "\n");
	Flags.KnownSafe &= TDIsKnownSafe;

	// We can only move instructions if we know that we are not partial. We can
	// still delete instructions in such cases though.
	bool TDIsPartial = (*TDRefCountState)->second.isPartial();
	DEBUG(llvm::dbgs() << " PARTIAL: "
	<< (TDIsPartial ? "true" : "false") << "\n");
	Flags.Partial \|= TDIsPartial;

	// Now that we know we have an inst, grab the decrement.
	for (auto IncIter : (*TDRefCountState)->second.getInstructions()) {
	SILInstruction *Increment = IncIter;
	DEBUG(llvm::dbgs() << " Increment: " << *Increment);

	// Now grab the increment matched up with the decrement from the bottom up map.
	// If we can't find it, bail we can't match this increment up with anything.
	auto BURefCountState = BUMap.find(Increment);
	if (BURefCountState == BUMap.end()) {
	DEBUG(llvm::dbgs() << " FAILURE! Could not find state for "
	"increment.\n");
	return None;
	}

	DEBUG(
	llvm::dbgs() << " SUCCESS! Found state for increment.\n");

	// Make sure the increment we are looking at is also matched to our decrement.
	// Otherwise bail.
	if (!(*BURefCountState)->second.isTrackingRefCountInst() \|\|
	!(*BURefCountState)->second.containsInstruction(Decrement)) {
	DEBUG(
	llvm::dbgs() << " FAILURE! Not tracking instruction or "
	"found increment that did not match.\n");
	return None;
	}

	// Add the decrement to the decrement to move set. If we don't insert
	// anything, just continue.
	if (!MatchSet.Increments.insert(Increment)) {
	DEBUG(llvm::dbgs() << " SKIPPING! Already processed this increment.\n");
	continue;
	}

	// Collect the decrement insertion point if we have one.
	for (auto InsertPtIter : (*BURefCountState)->second.getInsertPts()) {
	MatchSet.DecrementInsertPts.insert(InsertPtIter);
	}
	NewIncrements.push_back(Increment);
	}
	}

	return Flags;
	}

	/// Visit each retain/release that is matched up to our operand over and over
	/// again until we converge by not adding any more to the set which we can move.
	/// If we find a situation that we cannot handle, we bail and return false. If
	/// we succeed and it is safe to move increment/releases, we return true.
	bool ARCMatchingSetBuilder::matchUpIncDecSetsForPtr() {
	bool KnownSafeTD = true;
	bool KnownSafeBU = true;
	bool Partial = false;

	while (true) {
	DEBUG(llvm::dbgs() << "Attempting to match up increments -> decrements:\n");
	// For each increment in our list of new increments, attempt to match them up
	// with decrements and gather the insertion points of the decrements.
	auto Result = matchIncrementsToDecrements();
	if (!Result) {
	DEBUG(llvm::dbgs() << " FAILED TO MATCH INCREMENTS -> DECREMENTS!\n");
	return false;
	}
	if (!Result->KnownSafe) {
	DEBUG(llvm::dbgs() << " NOT KNOWN SAFE!\n");
	KnownSafeTD = false;
	}
	if (Result->Partial) {
	DEBUG(llvm::dbgs() << " IS PARTIAL!\n");
	Partial = true;
	}
	NewIncrements.clear();

	// If we do not have any decrements to attempt to match up with, bail.
	if (NewDecrements.empty())
	break;

	DEBUG(llvm::dbgs() << "Attempting to match up decrements -> increments:\n");
	Result = matchDecrementsToIncrements();
	if (!Result) {
	DEBUG(llvm::dbgs() << " FAILED TO MATCH DECREMENTS -> INCREMENTS!\n");
	return false;
	}
	if (!Result->KnownSafe) {
	DEBUG(llvm::dbgs() << " NOT KNOWN SAFE!\n");
	KnownSafeBU = false;
	}
	if (Result->Partial) {
	DEBUG(llvm::dbgs() << " IS PARTIAL!\n");
	Partial = true;
	}
	NewDecrements.clear();

	// If we do not have any increment to attempt to match up with again, bail.
	if (NewIncrements.empty())
	break;
	}

	bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU);
	if (UnconditionallySafe) {
	DEBUG(llvm::dbgs() << "UNCONDITIONALLY SAFE! DELETING INSTS.\n");
	MatchSet.IncrementInsertPts.clear();
	MatchSet.DecrementInsertPts.clear();
	} else {
	DEBUG(llvm::dbgs() << "NOT UNCONDITIONALLY SAFE!\n");

	}

	bool HaveIncInsertPts = !MatchSet.IncrementInsertPts.empty();
	bool HaveDecInsertPts = !MatchSet.DecrementInsertPts.empty();

	// If we have insertion points and partial merges, return false to avoid
	// control dependency issues.
	if ((HaveIncInsertPts \|\| HaveDecInsertPts) && Partial) {
	DEBUG(llvm::dbgs() << "Found partial merge and insert pts. Bailing!\n");
	return false;
	}

	// If we have insertion points for increments, but not for decrements (or
	// vis-a-versa), return false. This prevents us from inserting retains and
	// removing releases or vis-a-versa.
	if (HaveIncInsertPts != HaveDecInsertPts)
	return false;

	// If we do not have any insertion points but we do have increments, we must
	// be eliminating pairs.
	if (!HaveIncInsertPts && !MatchSet.Increments.empty())
	MatchedPair = true;

	// Success!
	DEBUG(llvm::dbgs() << "SUCCESS! We can move, remove things.\n");
	return true;
	}

	//===----------------------------------------------------------------------===//
	// ARC Pairing Context
	//===----------------------------------------------------------------------===//

	bool ARCPairingContext::performMatching(CodeMotionOrDeleteCallback &Callback) {
	bool MatchedPair = false;

	DEBUG(llvm::dbgs() << "**** Computing ARC Matching Sets for " << F.getName()
	<< " ****\n");

	/// For each increment that we matched to a decrement, try to match it to a
	/// decrement -> increment pair.
	for (auto Pair : IncToDecStateMap) {
	if (!Pair.hasValue())
	continue;

	SILInstruction *Increment = Pair->first;
	if (!Increment)
	continue; // blotted

	DEBUG(llvm::dbgs() << "Constructing Matching Set For: " << *Increment);
	ARCMatchingSetBuilder Builder(DecToIncStateMap, IncToDecStateMap, RCIA);
	Builder.init(Increment);
	if (Builder.matchUpIncDecSetsForPtr()) {
	MatchedPair \|= Builder.matchedPair();
	auto &Set = Builder.getResult();
	for (auto *I : Set.Increments)
	IncToDecStateMap.blot(I);
	for (auto *I : Set.Decrements)
	DecToIncStateMap.blot(I);

	// Add the Set to the callback. NOTE No instruction destruction can
	// happen here since we may remove instructions that are insertion points
	// for other instructions.
	Callback.processMatchingSet(Set);
	}
	}

	// Then finalize the callback. This is the only place instructions can be
	// deleted.
	Callback.finalize();
	return MatchedPair;
	}

	//===----------------------------------------------------------------------===//
	// Loop ARC
	//===----------------------------------------------------------------------===//

	void LoopARCPairingContext::runOnLoop(SILLoop *L) {
	auto *Region = LRFI->getRegion(L);
	if (processRegion(Region, false, false)) {
	// We do not recompute for now since we only look at the top function level
	// for post dominating releases.
	processRegion(Region, true, false);
	}

	// Now that we have finished processing the loop, summarize the loop.
	Evaluator.summarizeLoop(Region);
	}

	void LoopARCPairingContext::runOnFunction(SILFunction *F) {
	if (processRegion(LRFI->getTopLevelRegion(), false, false)) {
	// We recompute the final post dom release since we may have moved the final
	// post dominated releases.
	processRegion(LRFI->getTopLevelRegion(), true, true);
	}
	}

	bool LoopARCPairingContext::processRegion(const LoopRegion *Region,
	bool FreezePostDomReleases,
	bool RecomputePostDomReleases) {
	bool MadeChange = false;
	bool NestingDetected = Evaluator.runOnLoop(Region, FreezePostDomReleases,
	RecomputePostDomReleases);
	bool MatchedPair = Context.performMatching(Callback);
	MadeChange \|= MatchedPair;
	Evaluator.clearLoopState(Region);
	Context.DecToIncStateMap.clear();
	Context.IncToDecStateMap.clear();

	while (NestingDetected && MatchedPair) {
	NestingDetected = Evaluator.runOnLoop(Region, FreezePostDomReleases, false);
	MatchedPair = Context.performMatching(Callback);
	MadeChange \|= MatchedPair;
	Evaluator.clearLoopState(Region);
	Context.DecToIncStateMap.clear();
	Context.IncToDecStateMap.clear();
	}

	return MadeChange;
	}