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

 //===--- RCStateTransitionVisitors.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 "arc-sequence-opts"
 #include "RCStateTransitionVisitors.h"
 #include "ARCBBState.h"
 #include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
 #include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
 #include "llvm/Support/Debug.h"

 using namespace swift;

 namespace {

 using ARCBBState = ARCSequenceDataflowEvaluator::ARCBBState;

 } // end anonymous namespace


 //===----------------------------------------------------------------------===//
 //                             Utilities
 //===----------------------------------------------------------------------===//

 /// Return true if this instruction is the epilogue release for the \p Arg.
 /// false otherwise.
 static bool isOwnedArgumentEpilogueRelease(SILInstruction *I, SILValue Arg,
                                            EpilogueARCFunctionInfo *EAFI) {
   auto Releases =
     EAFI->computeEpilogueARCInstructions(
             EpilogueARCContext::EpilogueARCKind::Release, Arg);
   return Releases.size() && Releases.count(I);
 }

 static bool isGuaranteedSafetyByEpilogueRelease(SILInstruction *I, SILValue Arg,
                                                 EpilogueARCFunctionInfo *EAFI) {
   auto Releases =
     EAFI->computeEpilogueARCInstructions(
             EpilogueARCContext::EpilogueARCKind::Release, Arg);
   return Releases.size() && !Releases.count(I);
 }

 //===----------------------------------------------------------------------===//
 //                      BottomUpRCStateTransitionVisitor
 //===----------------------------------------------------------------------===//

 template <class ARCState>
 BottomUpDataflowRCStateVisitor<ARCState>::BottomUpDataflowRCStateVisitor(
     RCIdentityFunctionInfo *RCFI, EpilogueARCFunctionInfo *EAFI,
     ARCState &State, bool FreezeOwnedArgEpilogueReleases,
     IncToDecStateMapTy &IncToDecStateMap,
     ImmutablePointerSetFactory<SILInstruction> &SetFactory)
     : RCFI(RCFI), EAFI(EAFI), DataflowState(State),
       FreezeOwnedArgEpilogueReleases(FreezeOwnedArgEpilogueReleases),
       IncToDecStateMap(IncToDecStateMap), SetFactory(SetFactory) {}

 template <class ARCState>
 typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
 BottomUpDataflowRCStateVisitor<ARCState>::
 visitAutoreleasePoolCall(SILNode *N) {
   DataflowState.clear();

   // We just cleared our BB State so we have no more possible effects.
   return DataflowResult(RCStateTransitionDataflowResultKind::NoEffects);
 }

 // private helper method since C++ does not have extensions... *sigh*.
 //
 // TODO: This needs a better name.
 template <class ARCState>
 static bool isKnownSafe(BottomUpDataflowRCStateVisitor<ARCState> *State,
                         SILInstruction *I, SILValue Op) {
   // If we are running with 'frozen' owned arg releases, check if we have a
   // frozen use in the side table. If so, this release must be known safe.
   if (State->FreezeOwnedArgEpilogueReleases)
     if (isGuaranteedSafetyByEpilogueRelease(I, Op, State->EAFI))
       return true;

   // A guaranteed function argument is guaranteed to outlive the function we are
   // processing. So bottom up for such a parameter, we are always known safe.
   if (auto *Arg = dyn_cast<SILFunctionArgument>(Op)) {
     if (Arg->hasConvention(SILArgumentConvention::Direct_Guaranteed)) {
       return true;
     }
   }

   // If Op is a load from an in_guaranteed parameter, it is guaranteed as well.
   if (auto *LI = dyn_cast<LoadInst>(Op)) {
     SILValue RCIdentity = State->RCFI->getRCIdentityRoot(LI->getOperand());
     if (auto *Arg = dyn_cast<SILFunctionArgument>(RCIdentity)) {
       if (Arg->hasConvention(SILArgumentConvention::Indirect_In_Guaranteed)) {
         return true;
       }
     }
   }

   return false;
 }

 template <class ARCState>
 typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
 BottomUpDataflowRCStateVisitor<ARCState>::visitStrongDecrement(SILNode *N) {
   auto *I = dyn_cast<SILInstruction>(N);
   if (!I)
     return DataflowResult();

   SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));

   // If this instruction is a post dominating release, skip it so we don't pair
   // it up with anything. Do make sure that it does not effect any other
   // instructions.
   if (FreezeOwnedArgEpilogueReleases && isOwnedArgumentEpilogueRelease(I, Op, EAFI))
     return DataflowResult(Op);

   BottomUpRefCountState &State = DataflowState.getBottomUpRefCountState(Op);
   bool NestingDetected = State.initWithMutatorInst(SetFactory.get(I), RCFI);

   if (isKnownSafe(this, I, Op)) {
     State.updateKnownSafe(true);
   }

   LLVM_DEBUG(llvm::dbgs() << "    REF COUNT DECREMENT! Known Safe: "
                           << (State.isKnownSafe() ? "yes" : "no") << "\n");

   // Continue on to see if our reference decrement could potentially affect
   // any other pointers via a use or a decrement.
   return DataflowResult(Op, NestingDetected);
 }

 template <class ARCState>
 typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
 BottomUpDataflowRCStateVisitor<ARCState>::visitStrongIncrement(SILNode *N) {
   auto *I = dyn_cast<SILInstruction>(N);
   if (!I)
     return DataflowResult();

   // Look up the state associated with its operand...
   SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
   auto &RefCountState = DataflowState.getBottomUpRefCountState(Op);

   LLVM_DEBUG(llvm::dbgs() << "    REF COUNT INCREMENT!\n");

   // If we find a state initialized with a matching increment, pair this
   // decrement with a copy of the ref count state and then clear the ref
   // count state in preparation for any future pairs we may see on the same
   // pointer.
   if (RefCountState.isRefCountInstMatchedToTrackedInstruction(I)) {
     // Copy the current value of ref count state into the result map.
     IncToDecStateMap[I] = RefCountState;
     LLVM_DEBUG(llvm::dbgs() << "    MATCHING DECREMENT:"
                             << RefCountState.getRCRoot());

     // Clear the ref count state so it can be used for future pairs we may
     // see.
     RefCountState.clear();
   }
 #ifndef NDEBUG
   else {
     if (RefCountState.isTrackingRefCountInst()) {
       LLVM_DEBUG(llvm::dbgs() << "    FAILED MATCH DECREMENT:"
                               << RefCountState.getRCRoot());
     } else {
       LLVM_DEBUG(llvm::dbgs() << "    FAILED MATCH DECREMENT. Not tracking a "
                                  "decrement.\n");
     }
   }
 #endif
   return DataflowResult(Op);
 }

 //===----------------------------------------------------------------------===//
 //                       TopDownDataflowRCStateVisitor
 //===----------------------------------------------------------------------===//

 template <class ARCState>
 TopDownDataflowRCStateVisitor<ARCState>::TopDownDataflowRCStateVisitor(
     RCIdentityFunctionInfo *RCFI, ARCState &DataflowState,
     DecToIncStateMapTy &DecToIncStateMap,
     ImmutablePointerSetFactory<SILInstruction> &SetFactory)
     : RCFI(RCFI), DataflowState(DataflowState),
       DecToIncStateMap(DecToIncStateMap), SetFactory(SetFactory) {}

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitAutoreleasePoolCall(SILNode *N) {
   DataflowState.clear();
   // We just cleared our BB State so we have no more possible effects.
   return DataflowResult(RCStateTransitionDataflowResultKind::NoEffects);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::visitStrongDecrement(SILNode *N) {
   auto *I = dyn_cast<SILInstruction>(N);
   if (!I)
     return DataflowResult();

   // Look up the state associated with I's operand...
   SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
   auto &RefCountState = DataflowState.getTopDownRefCountState(Op);

   LLVM_DEBUG(llvm::dbgs() << "    REF COUNT DECREMENT!\n");

   // If we are tracking an increment on the ref count root associated with
   // the decrement and the decrement matches, pair this decrement with a
   // copy of the increment state and then clear the original increment state
   // so that we are ready to process further values.
   if (RefCountState.isRefCountInstMatchedToTrackedInstruction(I)) {
     // Copy the current value of ref count state into the result map.
     DecToIncStateMap[I] = RefCountState;
     LLVM_DEBUG(llvm::dbgs() << "    MATCHING INCREMENT:\n"
                             << RefCountState.getRCRoot());

     // Clear the ref count state in preparation for more pairs.
     RefCountState.clear();
   }
 #if NDEBUG
   else {
     if (RefCountState.isTrackingRefCountInst()) {
       LLVM_DEBUG(llvm::dbgs() << "    FAILED MATCH INCREMENT:\n"
                               << RefCountState.getValue());
     } else {
       LLVM_DEBUG(llvm::dbgs() << "    FAILED MATCH. NO INCREMENT.\n");
     }
   }
 #endif

   // Otherwise we continue processing the reference count decrement to see if
   // the decrement can affect any other pointers that we are tracking.
   return DataflowResult(Op);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::visitStrongIncrement(SILNode *N) {
   auto *I = dyn_cast<SILInstruction>(N);
   if (!I)
     return DataflowResult();

   // Map the increment's operand to a newly initialized or reinitialized ref
   // count state and continue...
   SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
   auto &State = DataflowState.getTopDownRefCountState(Op);
   bool NestingDetected = State.initWithMutatorInst(SetFactory.get(I), RCFI);

   LLVM_DEBUG(llvm::dbgs() << "    REF COUNT INCREMENT! Known Safe: "
                           << (State.isKnownSafe() ? "yes" : "no") << "\n");

   // Continue processing in case this increment could be a CanUse for a
   // different pointer.
   return DataflowResult(Op, NestingDetected);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::visitStrongEntranceArgument(
     SILFunctionArgument *Arg) {
   LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE ARGUMENT: " << *Arg);

   if (!Arg->hasConvention(SILArgumentConvention::Direct_Owned)) {
     LLVM_DEBUG(llvm::dbgs() << "    Not owned! Bailing!\n");
     return DataflowResult();
   }

   LLVM_DEBUG(llvm::dbgs() << "    Initializing state.\n");

   auto &State = DataflowState.getTopDownRefCountState(Arg);
   State.initWithArg(Arg);

   return DataflowResult();
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitStrongEntranceApply(ApplyInst *AI) {
   LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE APPLY: " << *AI);

   // We should have checked earlier that AI has an owned result value. To
   // prevent mistakes, assert that here.
 #ifndef NDEBUG
   bool hasOwnedResult = false;
   for (auto result : AI->getSubstCalleeConv().getDirectSILResults()) {
     if (result.getConvention() == ResultConvention::Owned)
       hasOwnedResult = true;
   }
   assert(hasOwnedResult && "Expected AI to be Owned here");
 #endif

   // Otherwise, return a dataflow result containing a +1.
   LLVM_DEBUG(llvm::dbgs() << "    Initializing state.\n");

   auto &State = DataflowState.getTopDownRefCountState(AI);
   State.initWithEntranceInst(SetFactory.get(AI), AI);

   return DataflowResult(AI);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::visitStrongEntrancePartialApply(
     PartialApplyInst *PAI) {
   LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE PARTIAL APPLY: " << *PAI);

   // Rreturn a dataflow result containing a +1.
   LLVM_DEBUG(llvm::dbgs() << "    Initializing state.\n");

   auto &State = DataflowState.getTopDownRefCountState(PAI);
   State.initWithEntranceInst(SetFactory.get(PAI), PAI);

   return DataflowResult(PAI);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitStrongEntranceAllocRef(AllocRefInst *ARI) {
   // Alloc refs always introduce new references at +1.
   TopDownRefCountState &State = DataflowState.getTopDownRefCountState(ARI);
   State.initWithEntranceInst(SetFactory.get(ARI), ARI);

   return DataflowResult(ARI);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitStrongEntranceAllocRefDynamic(AllocRefDynamicInst *ARI) {
   // Alloc ref dynamic always introduce references at +1.
   auto &State = DataflowState.getTopDownRefCountState(ARI);
   State.initWithEntranceInst(SetFactory.get(ARI), ARI);

   return DataflowResult(ARI);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitStrongAllocBox(AllocBoxInst *ABI) {
   // Alloc box introduces a ref count of +1 on its container.
   auto &State = DataflowState.getTopDownRefCountState(ABI);
   State.initWithEntranceInst(SetFactory.get(ABI), ABI);
   return DataflowResult(ABI);
 }

 template <class ARCState>
 typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
 TopDownDataflowRCStateVisitor<ARCState>::
 visitStrongEntrance(SILNode *N) {
   if (auto *Arg = dyn_cast<SILFunctionArgument>(N))
     return visitStrongEntranceArgument(Arg);

   if (auto *AI = dyn_cast<ApplyInst>(N))
     return visitStrongEntranceApply(AI);

   if (auto *ARI = dyn_cast<AllocRefInst>(N))
     return visitStrongEntranceAllocRef(ARI);

   if (auto *ARI = dyn_cast<AllocRefDynamicInst>(N))
     return visitStrongEntranceAllocRefDynamic(ARI);

   if (auto *ABI = dyn_cast<AllocBoxInst>(N))
     return visitStrongAllocBox(ABI);

   if (auto *PAI = dyn_cast<PartialApplyInst>(N))
     return visitStrongEntrancePartialApply(PAI);

   return DataflowResult();
 }

 //===----------------------------------------------------------------------===//
 //                           Template Instantiation
 //===----------------------------------------------------------------------===//

 namespace swift {

 template class BottomUpDataflowRCStateVisitor<ARCBBState>;
 template class BottomUpDataflowRCStateVisitor<ARCRegionState>;
 template class TopDownDataflowRCStateVisitor<ARCBBState>;
 template class TopDownDataflowRCStateVisitor<ARCRegionState>;

 } // namespace swift
	//===--- RCStateTransitionVisitors.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 "arc-sequence-opts"
	#include "RCStateTransitionVisitors.h"
	#include "ARCBBState.h"
	#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
	#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
	#include "llvm/Support/Debug.h"

	using namespace swift;

	namespace {

	using ARCBBState = ARCSequenceDataflowEvaluator::ARCBBState;

	} // end anonymous namespace


	//===----------------------------------------------------------------------===//
	// Utilities
	//===----------------------------------------------------------------------===//

	/// Return true if this instruction is the epilogue release for the \p Arg.
	/// false otherwise.
	static bool isOwnedArgumentEpilogueRelease(SILInstruction *I, SILValue Arg,
	EpilogueARCFunctionInfo *EAFI) {
	auto Releases =
	EAFI->computeEpilogueARCInstructions(
	EpilogueARCContext::EpilogueARCKind::Release, Arg);
	return Releases.size() && Releases.count(I);
	}

	static bool isGuaranteedSafetyByEpilogueRelease(SILInstruction *I, SILValue Arg,
	EpilogueARCFunctionInfo *EAFI) {
	auto Releases =
	EAFI->computeEpilogueARCInstructions(
	EpilogueARCContext::EpilogueARCKind::Release, Arg);
	return Releases.size() && !Releases.count(I);
	}

	//===----------------------------------------------------------------------===//
	// BottomUpRCStateTransitionVisitor
	//===----------------------------------------------------------------------===//

	template <class ARCState>
	BottomUpDataflowRCStateVisitor<ARCState>::BottomUpDataflowRCStateVisitor(
	RCIdentityFunctionInfo RCFI, EpilogueARCFunctionInfo EAFI,
	ARCState &State, bool FreezeOwnedArgEpilogueReleases,
	IncToDecStateMapTy &IncToDecStateMap,
	ImmutablePointerSetFactory<SILInstruction> &SetFactory)
	: RCFI(RCFI), EAFI(EAFI), DataflowState(State),
	FreezeOwnedArgEpilogueReleases(FreezeOwnedArgEpilogueReleases),
	IncToDecStateMap(IncToDecStateMap), SetFactory(SetFactory) {}

	template <class ARCState>
	typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
	BottomUpDataflowRCStateVisitor<ARCState>::
	visitAutoreleasePoolCall(SILNode *N) {
	DataflowState.clear();

	// We just cleared our BB State so we have no more possible effects.
	return DataflowResult(RCStateTransitionDataflowResultKind::NoEffects);
	}

	// private helper method since C++ does not have extensions... sigh.
	//
	// TODO: This needs a better name.
	template <class ARCState>
	static bool isKnownSafe(BottomUpDataflowRCStateVisitor<ARCState> *State,
	SILInstruction *I, SILValue Op) {
	// If we are running with 'frozen' owned arg releases, check if we have a
	// frozen use in the side table. If so, this release must be known safe.
	if (State->FreezeOwnedArgEpilogueReleases)
	if (isGuaranteedSafetyByEpilogueRelease(I, Op, State->EAFI))
	return true;

	// A guaranteed function argument is guaranteed to outlive the function we are
	// processing. So bottom up for such a parameter, we are always known safe.
	if (auto *Arg = dyn_cast<SILFunctionArgument>(Op)) {
	if (Arg->hasConvention(SILArgumentConvention::Direct_Guaranteed)) {
	return true;
	}
	}

	// If Op is a load from an in_guaranteed parameter, it is guaranteed as well.
	if (auto *LI = dyn_cast<LoadInst>(Op)) {
	SILValue RCIdentity = State->RCFI->getRCIdentityRoot(LI->getOperand());
	if (auto *Arg = dyn_cast<SILFunctionArgument>(RCIdentity)) {
	if (Arg->hasConvention(SILArgumentConvention::Indirect_In_Guaranteed)) {
	return true;
	}
	}
	}

	return false;
	}

	template <class ARCState>
	typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
	BottomUpDataflowRCStateVisitor<ARCState>::visitStrongDecrement(SILNode *N) {
	auto *I = dyn_cast<SILInstruction>(N);
	if (!I)
	return DataflowResult();

	SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));

	// If this instruction is a post dominating release, skip it so we don't pair
	// it up with anything. Do make sure that it does not effect any other
	// instructions.
	if (FreezeOwnedArgEpilogueReleases && isOwnedArgumentEpilogueRelease(I, Op, EAFI))
	return DataflowResult(Op);

	BottomUpRefCountState &State = DataflowState.getBottomUpRefCountState(Op);
	bool NestingDetected = State.initWithMutatorInst(SetFactory.get(I), RCFI);

	if (isKnownSafe(this, I, Op)) {
	State.updateKnownSafe(true);
	}

	LLVM_DEBUG(llvm::dbgs() << " REF COUNT DECREMENT! Known Safe: "
	<< (State.isKnownSafe() ? "yes" : "no") << "\n");

	// Continue on to see if our reference decrement could potentially affect
	// any other pointers via a use or a decrement.
	return DataflowResult(Op, NestingDetected);
	}

	template <class ARCState>
	typename BottomUpDataflowRCStateVisitor<ARCState>::DataflowResult
	BottomUpDataflowRCStateVisitor<ARCState>::visitStrongIncrement(SILNode *N) {
	auto *I = dyn_cast<SILInstruction>(N);
	if (!I)
	return DataflowResult();

	// Look up the state associated with its operand...
	SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
	auto &RefCountState = DataflowState.getBottomUpRefCountState(Op);

	LLVM_DEBUG(llvm::dbgs() << " REF COUNT INCREMENT!\n");

	// If we find a state initialized with a matching increment, pair this
	// decrement with a copy of the ref count state and then clear the ref
	// count state in preparation for any future pairs we may see on the same
	// pointer.
	if (RefCountState.isRefCountInstMatchedToTrackedInstruction(I)) {
	// Copy the current value of ref count state into the result map.
	IncToDecStateMap[I] = RefCountState;
	LLVM_DEBUG(llvm::dbgs() << " MATCHING DECREMENT:"
	<< RefCountState.getRCRoot());

	// Clear the ref count state so it can be used for future pairs we may
	// see.
	RefCountState.clear();
	}
	#ifndef NDEBUG
	else {
	if (RefCountState.isTrackingRefCountInst()) {
	LLVM_DEBUG(llvm::dbgs() << " FAILED MATCH DECREMENT:"
	<< RefCountState.getRCRoot());
	} else {
	LLVM_DEBUG(llvm::dbgs() << " FAILED MATCH DECREMENT. Not tracking a "
	"decrement.\n");
	}
	}
	#endif
	return DataflowResult(Op);
	}

	//===----------------------------------------------------------------------===//
	// TopDownDataflowRCStateVisitor
	//===----------------------------------------------------------------------===//

	template <class ARCState>
	TopDownDataflowRCStateVisitor<ARCState>::TopDownDataflowRCStateVisitor(
	RCIdentityFunctionInfo *RCFI, ARCState &DataflowState,
	DecToIncStateMapTy &DecToIncStateMap,
	ImmutablePointerSetFactory<SILInstruction> &SetFactory)
	: RCFI(RCFI), DataflowState(DataflowState),
	DecToIncStateMap(DecToIncStateMap), SetFactory(SetFactory) {}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitAutoreleasePoolCall(SILNode *N) {
	DataflowState.clear();
	// We just cleared our BB State so we have no more possible effects.
	return DataflowResult(RCStateTransitionDataflowResultKind::NoEffects);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::visitStrongDecrement(SILNode *N) {
	auto *I = dyn_cast<SILInstruction>(N);
	if (!I)
	return DataflowResult();

	// Look up the state associated with I's operand...
	SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
	auto &RefCountState = DataflowState.getTopDownRefCountState(Op);

	LLVM_DEBUG(llvm::dbgs() << " REF COUNT DECREMENT!\n");

	// If we are tracking an increment on the ref count root associated with
	// the decrement and the decrement matches, pair this decrement with a
	// copy of the increment state and then clear the original increment state
	// so that we are ready to process further values.
	if (RefCountState.isRefCountInstMatchedToTrackedInstruction(I)) {
	// Copy the current value of ref count state into the result map.
	DecToIncStateMap[I] = RefCountState;
	LLVM_DEBUG(llvm::dbgs() << " MATCHING INCREMENT:\n"
	<< RefCountState.getRCRoot());

	// Clear the ref count state in preparation for more pairs.
	RefCountState.clear();
	}
	#if NDEBUG
	else {
	if (RefCountState.isTrackingRefCountInst()) {
	LLVM_DEBUG(llvm::dbgs() << " FAILED MATCH INCREMENT:\n"
	<< RefCountState.getValue());
	} else {
	LLVM_DEBUG(llvm::dbgs() << " FAILED MATCH. NO INCREMENT.\n");
	}
	}
	#endif

	// Otherwise we continue processing the reference count decrement to see if
	// the decrement can affect any other pointers that we are tracking.
	return DataflowResult(Op);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::visitStrongIncrement(SILNode *N) {
	auto *I = dyn_cast<SILInstruction>(N);
	if (!I)
	return DataflowResult();

	// Map the increment's operand to a newly initialized or reinitialized ref
	// count state and continue...
	SILValue Op = RCFI->getRCIdentityRoot(I->getOperand(0));
	auto &State = DataflowState.getTopDownRefCountState(Op);
	bool NestingDetected = State.initWithMutatorInst(SetFactory.get(I), RCFI);

	LLVM_DEBUG(llvm::dbgs() << " REF COUNT INCREMENT! Known Safe: "
	<< (State.isKnownSafe() ? "yes" : "no") << "\n");

	// Continue processing in case this increment could be a CanUse for a
	// different pointer.
	return DataflowResult(Op, NestingDetected);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::visitStrongEntranceArgument(
	SILFunctionArgument *Arg) {
	LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE ARGUMENT: " << *Arg);

	if (!Arg->hasConvention(SILArgumentConvention::Direct_Owned)) {
	LLVM_DEBUG(llvm::dbgs() << " Not owned! Bailing!\n");
	return DataflowResult();
	}

	LLVM_DEBUG(llvm::dbgs() << " Initializing state.\n");

	auto &State = DataflowState.getTopDownRefCountState(Arg);
	State.initWithArg(Arg);

	return DataflowResult();
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitStrongEntranceApply(ApplyInst *AI) {
	LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE APPLY: " << *AI);

	// We should have checked earlier that AI has an owned result value. To
	// prevent mistakes, assert that here.
	#ifndef NDEBUG
	bool hasOwnedResult = false;
	for (auto result : AI->getSubstCalleeConv().getDirectSILResults()) {
	if (result.getConvention() == ResultConvention::Owned)
	hasOwnedResult = true;
	}
	assert(hasOwnedResult && "Expected AI to be Owned here");
	#endif

	// Otherwise, return a dataflow result containing a +1.
	LLVM_DEBUG(llvm::dbgs() << " Initializing state.\n");

	auto &State = DataflowState.getTopDownRefCountState(AI);
	State.initWithEntranceInst(SetFactory.get(AI), AI);

	return DataflowResult(AI);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::visitStrongEntrancePartialApply(
	PartialApplyInst *PAI) {
	LLVM_DEBUG(llvm::dbgs() << "VISITING ENTRANCE PARTIAL APPLY: " << *PAI);

	// Rreturn a dataflow result containing a +1.
	LLVM_DEBUG(llvm::dbgs() << " Initializing state.\n");

	auto &State = DataflowState.getTopDownRefCountState(PAI);
	State.initWithEntranceInst(SetFactory.get(PAI), PAI);

	return DataflowResult(PAI);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitStrongEntranceAllocRef(AllocRefInst *ARI) {
	// Alloc refs always introduce new references at +1.
	TopDownRefCountState &State = DataflowState.getTopDownRefCountState(ARI);
	State.initWithEntranceInst(SetFactory.get(ARI), ARI);

	return DataflowResult(ARI);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitStrongEntranceAllocRefDynamic(AllocRefDynamicInst *ARI) {
	// Alloc ref dynamic always introduce references at +1.
	auto &State = DataflowState.getTopDownRefCountState(ARI);
	State.initWithEntranceInst(SetFactory.get(ARI), ARI);

	return DataflowResult(ARI);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitStrongAllocBox(AllocBoxInst *ABI) {
	// Alloc box introduces a ref count of +1 on its container.
	auto &State = DataflowState.getTopDownRefCountState(ABI);
	State.initWithEntranceInst(SetFactory.get(ABI), ABI);
	return DataflowResult(ABI);
	}

	template <class ARCState>
	typename TopDownDataflowRCStateVisitor<ARCState>::DataflowResult
	TopDownDataflowRCStateVisitor<ARCState>::
	visitStrongEntrance(SILNode *N) {
	if (auto *Arg = dyn_cast<SILFunctionArgument>(N))
	return visitStrongEntranceArgument(Arg);

	if (auto *AI = dyn_cast<ApplyInst>(N))
	return visitStrongEntranceApply(AI);

	if (auto *ARI = dyn_cast<AllocRefInst>(N))
	return visitStrongEntranceAllocRef(ARI);

	if (auto *ARI = dyn_cast<AllocRefDynamicInst>(N))
	return visitStrongEntranceAllocRefDynamic(ARI);

	if (auto *ABI = dyn_cast<AllocBoxInst>(N))
	return visitStrongAllocBox(ABI);

	if (auto *PAI = dyn_cast<PartialApplyInst>(N))
	return visitStrongEntrancePartialApply(PAI);

	return DataflowResult();
	}

	//===----------------------------------------------------------------------===//
	// Template Instantiation
	//===----------------------------------------------------------------------===//

	namespace swift {

	template class BottomUpDataflowRCStateVisitor<ARCBBState>;
	template class BottomUpDataflowRCStateVisitor<ARCRegionState>;
	template class TopDownDataflowRCStateVisitor<ARCBBState>;
	template class TopDownDataflowRCStateVisitor<ARCRegionState>;

	} // namespace swift