include/swift/SILOptimizer/Analysis/EpilogueARCAnalysis.h - third_party/swift - Git at Google

 //===--- EpilogueARCAnalysis.h ----------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This is an analysis that determines the ref count identity (i.e. gc root) of
 //  a pointer. Any values with the same ref count identity are able to be
 //  retained and released interchangeably.
 //
 //===----------------------------------------------------------------------===//

 #ifndef SWIFT_SILOPTIMIZER_ANALYSIS_EPILOGUEARCANALYSIS_H
 #define SWIFT_SILOPTIMIZER_ANALYSIS_EPILOGUEARCANALYSIS_H

 #include "swift/SIL/SILValue.h"
 #include "swift/SIL/SILArgument.h"
 #include "swift/SILOptimizer/Analysis/Analysis.h"
 #include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
 #include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
 #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
 #include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
 #include "swift/SILOptimizer/PassManager/PassManager.h"

 namespace swift {

 /// EpilogueARCBlockState - Keep track of whether an epilogue ARC instruction
 /// has been found.
 struct EpilogueARCBlockState {
   /// Keep track of whether an epilogue release has been found before and after
   /// this basic block.
   bool BBSetIn;
   /// The basic block local SILValue we are interested to find epilogue ARC in.
   SILValue LocalArg;
   /// Constructor, we only compute epilogue ARC instruction for 1 argument at
   /// a time.
   /// Optimistic data flow.
   EpilogueARCBlockState() { BBSetIn = true; LocalArg = SILValue(); }
 };

 /// EpilogueARCContext - This class implements a data flow with which epilogue
 /// retains or releases for a SILValue are found.
 ///
 /// NOTE:
 /// In case of release finder, this function assumes the SILArgument has
 /// @owned semantic.
 /// In case of retain finder, this class assumes Arg is one of the return value
 /// of the function.
 class EpilogueARCContext {
 public:
   enum EpilogueARCKind { Retain = 0, Release = 1 };

 private:
   /// Current post-order we are using.
   LazyFunctionInfo<PostOrderAnalysis, PostOrderFunctionInfo> PO;

   /// Current alias analysis we are using.
   AliasAnalysis *AA;

   /// Current rc-identity we are using.
   LazyFunctionInfo<RCIdentityAnalysis, RCIdentityFunctionInfo> RCFI;

   // All state below this line must always be cleared by the reset routine.
   //
   // Are we finding retains or releases.
   EpilogueARCKind Kind;

   // The argument we are looking for epilogue ARC instruction for.
   SILValue Arg;

   /// A map from a block's post order index to block state.
   std::vector<EpilogueARCBlockState> IndexToStateMap;

   /// The epilogue retains or releases.
   llvm::SmallSetVector<SILInstruction *, 1> EpilogueARCInsts;

   /// The exit blocks of the function.
   llvm::SmallPtrSet<SILBasicBlock *, 2> ExitBlocks;

   EpilogueARCBlockState &getState(SILBasicBlock *BB) {
     return IndexToStateMap[*PO->getPONumber(BB)];
   }

   /// Return true if this is a function exiting block this epilogue ARC
   /// matcher is interested in.
   bool isInterestedFunctionExitingBlock(SILBasicBlock *BB) {
     if (EpilogueARCKind::Release == Kind)
       return BB->getTerminator()->isFunctionExiting();

     return BB->getTerminator()->isFunctionExiting() &&
            BB->getTerminator()->getTermKind() != TermKind::ThrowInst;
   }

   /// Return true if this is a function exit block.
   bool isExitBlock(SILBasicBlock *BB) {
     return ExitBlocks.count(BB);
   }

   /// Return true if this is a retain instruction.
   bool isRetainInstruction(SILInstruction *II) {
     return isa<RetainValueInst>(II) || isa<StrongRetainInst>(II);
   }

   /// Return true if this is a release instruction.
   bool isReleaseInstruction(SILInstruction *II) {
     return isa<ReleaseValueInst>(II) || isa<StrongReleaseInst>(II);
   }

   SILValue getArg(SILBasicBlock *BB) {
     SILValue A = getState(BB).LocalArg;
     if (A)
       return A;
     return Arg;
   }

 public:
   /// Constructor.
   EpilogueARCContext(SILFunction *F, PostOrderAnalysis *PO, AliasAnalysis *AA,
                      RCIdentityAnalysis *RCIA)
       : PO(F, PO), AA(AA), RCFI(F, RCIA) {}

   /// Run the data flow to find the epilogue retains or releases.
   bool run(EpilogueARCKind NewKind, SILValue NewArg) {
     Kind = NewKind;
     Arg = NewArg;

     // Initialize the epilogue arc data flow context.
     initializeDataflow();
     // Converge the data flow.
     if (!convergeDataflow())
       return false;
     // Lastly, find the epilogue ARC instructions.
     return computeEpilogueARC();
   }

   /// Reset the epilogue arc instructions.
   llvm::SmallSetVector<SILInstruction *, 1> getEpilogueARCInsts() {
     return EpilogueARCInsts;
   }

   void reset() {
     IndexToStateMap.clear();
     EpilogueARCInsts.clear();
     ExitBlocks.clear();
     EpilogueARCInsts.clear();
   }

   /// Initialize the data flow.
   void initializeDataflow();

   /// Keep iterating until the data flow is converged.
   bool convergeDataflow();

   /// Find the epilogue ARC instructions.
   bool computeEpilogueARC();

   /// This instruction prevents looking further for epilogue retains on the
   /// current path.
   bool mayBlockEpilogueRetain(SILInstruction *II, SILValue Ptr) {
     // reference decrementing instruction prevents any retain to be identified as
     // epilogue retains.
     if (mayDecrementRefCount(II, Ptr, AA))
       return true;
     // Handle self-recursion. A self-recursion can be considered a +1 on the
     // current argument.
     if (auto *AI = dyn_cast<ApplyInst>(II))
      if (AI->getCalleeFunction() == II->getParent()->getParent())
        return true;
     return false;
   }

   /// This instruction prevents looking further for epilogue releases on the
   /// current path.
   bool mayBlockEpilogueRelease(SILInstruction *II, SILValue Ptr) {
     // Check whether this instruction read reference count, i.e. uniqueness
     // check. Moving release past that may result in additional COW.
     return II->mayReleaseOrReadRefCount();
   }

   /// Does this instruction block the interested ARC instruction ?
   bool mayBlockEpilogueARC(SILInstruction *II, SILValue Ptr) {
     if (Kind == EpilogueARCKind::Retain)
       return mayBlockEpilogueRetain(II, Ptr);
     return mayBlockEpilogueRelease(II, Ptr);
   }

   /// This is the type of instructions the data flow is interested in.
   bool isInterestedInstruction(SILInstruction *II) {
     // We are checking for release.
     if (Kind == EpilogueARCKind::Release)
       return isReleaseInstruction(II) &&
              RCFI->getRCIdentityRoot(II->getOperand(0)) ==
              RCFI->getRCIdentityRoot(getArg(II->getParent()));
     // We are checking for retain. If this is a self-recursion. call
     // to the function (which returns an owned value) can be treated as
     // the retain instruction.
     if (auto *AI = dyn_cast<ApplyInst>(II))
      if (AI->getCalleeFunction() == II->getParent()->getParent())
        return true;
     // Check whether this is a retain instruction and the argument it
     // retains.
     return isRetainInstruction(II) &&
            RCFI->getRCIdentityRoot(II->getOperand(0)) ==
            RCFI->getRCIdentityRoot(getArg(II->getParent()));
   }
 };

 /// This class is a simple wrapper around an identity cache.
 class EpilogueARCFunctionInfo {
   using ARCInstructions = llvm::SmallSetVector<SILInstruction *, 1>;

   EpilogueARCContext Context;

   /// The epilogue retain cache.
   llvm::DenseMap<SILValue, ARCInstructions> EpilogueRetainInstCache;

   /// The epilogue release cache.
   llvm::DenseMap<SILValue, ARCInstructions> EpilogueReleaseInstCache;

 public:
   void handleDeleteNotification(ValueBase *V) {
     // Being conservative and clear everything for now.
     EpilogueRetainInstCache.clear();
     EpilogueReleaseInstCache.clear();
   }

   /// Constructor.
   EpilogueARCFunctionInfo(SILFunction *F, PostOrderAnalysis *PO,
                           AliasAnalysis *AA, RCIdentityAnalysis *RC)
       : Context(F, PO, AA, RC) {}

   /// Find the epilogue ARC instruction based on the given \p Kind and given
   /// \p Arg.
   llvm::SmallSetVector<SILInstruction *, 1>
   computeEpilogueARCInstructions(EpilogueARCContext::EpilogueARCKind Kind,
                                  SILValue Arg) {
     auto &ARCCache = Kind == EpilogueARCContext::EpilogueARCKind::Retain ?
                  EpilogueRetainInstCache :
                  EpilogueReleaseInstCache;
     auto Iter = ARCCache.find(Arg);
     if (Iter != ARCCache.end())
       return Iter->second;

     // Initialize and run the data flow. Clear the epilogue arc instructions if the
     // data flow is aborted in middle.
     if (!Context.run(Kind, Arg)) {
       Context.reset();
       return llvm::SmallSetVector<SILInstruction *, 1>();
     }

     auto Result = Context.getEpilogueARCInsts();
     Context.reset();
     ARCCache[Arg] = Result;
     return Result;
   }
 };

 class EpilogueARCAnalysis : public FunctionAnalysisBase<EpilogueARCFunctionInfo> {
   /// Current post order analysis we are using.
   PostOrderAnalysis *PO;
   /// Current alias analysis we are using.
   AliasAnalysis *AA;
   /// Current RC Identity analysis we are using.
   RCIdentityAnalysis *RC;

 public:
   EpilogueARCAnalysis(SILModule *)
     : FunctionAnalysisBase<EpilogueARCFunctionInfo>(AnalysisKind::EpilogueARC),
       PO(nullptr), AA(nullptr), RC(nullptr) {}

   EpilogueARCAnalysis(const EpilogueARCAnalysis &) = delete;
   EpilogueARCAnalysis &operator=(const EpilogueARCAnalysis &) = delete;

   virtual void handleDeleteNotification(ValueBase *V) override {
     // If the parent function of this instruction was just turned into an
     // external declaration, bail. This happens during SILFunction destruction.
     SILFunction *F = V->getFunction();
     if (F->isExternalDeclaration()) {
       return;
     }

     // If we do have an analysis, tell it to handle its delete notifications.
     if (auto A = maybeGet(F)) {
       A.get()->handleDeleteNotification(V);
     }
   }

   virtual bool needsNotifications() override { return true; }

   static bool classof(const SILAnalysis *S) {
     return S->getKind() == AnalysisKind::EpilogueARC;
   }

   virtual void initialize(SILPassManager *PM) override;

   virtual EpilogueARCFunctionInfo *newFunctionAnalysis(SILFunction *F) override {
     return new EpilogueARCFunctionInfo(F, PO, AA, RC);
   }

   virtual bool shouldInvalidate(SILAnalysis::InvalidationKind K) override {
     return true;
   }

  };

 } // end swift namespace

 #endif
	//===--- EpilogueARCAnalysis.h ----------------------------------- C++ --===//
	//
	// 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
	//
	//===----------------------------------------------------------------------===//
	//
	// This is an analysis that determines the ref count identity (i.e. gc root) of
	// a pointer. Any values with the same ref count identity are able to be
	// retained and released interchangeably.
	//
	//===----------------------------------------------------------------------===//

	#ifndef SWIFT_SILOPTIMIZER_ANALYSIS_EPILOGUEARCANALYSIS_H
	#define SWIFT_SILOPTIMIZER_ANALYSIS_EPILOGUEARCANALYSIS_H

	#include "swift/SIL/SILValue.h"
	#include "swift/SIL/SILArgument.h"
	#include "swift/SILOptimizer/Analysis/Analysis.h"
	#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
	#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
	#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
	#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
	#include "swift/SILOptimizer/PassManager/PassManager.h"

	namespace swift {

	/// EpilogueARCBlockState - Keep track of whether an epilogue ARC instruction
	/// has been found.
	struct EpilogueARCBlockState {
	/// Keep track of whether an epilogue release has been found before and after
	/// this basic block.
	bool BBSetIn;
	/// The basic block local SILValue we are interested to find epilogue ARC in.
	SILValue LocalArg;
	/// Constructor, we only compute epilogue ARC instruction for 1 argument at
	/// a time.
	/// Optimistic data flow.
	EpilogueARCBlockState() { BBSetIn = true; LocalArg = SILValue(); }
	};

	/// EpilogueARCContext - This class implements a data flow with which epilogue
	/// retains or releases for a SILValue are found.
	///
	/// NOTE:
	/// In case of release finder, this function assumes the SILArgument has
	/// @owned semantic.
	/// In case of retain finder, this class assumes Arg is one of the return value
	/// of the function.
	class EpilogueARCContext {
	public:
	enum EpilogueARCKind { Retain = 0, Release = 1 };

	private:
	/// Current post-order we are using.
	LazyFunctionInfo<PostOrderAnalysis, PostOrderFunctionInfo> PO;

	/// Current alias analysis we are using.
	AliasAnalysis *AA;

	/// Current rc-identity we are using.
	LazyFunctionInfo<RCIdentityAnalysis, RCIdentityFunctionInfo> RCFI;

	// All state below this line must always be cleared by the reset routine.
	//
	// Are we finding retains or releases.
	EpilogueARCKind Kind;

	// The argument we are looking for epilogue ARC instruction for.
	SILValue Arg;

	/// A map from a block's post order index to block state.
	std::vector<EpilogueARCBlockState> IndexToStateMap;

	/// The epilogue retains or releases.
	llvm::SmallSetVector<SILInstruction *, 1> EpilogueARCInsts;

	/// The exit blocks of the function.
	llvm::SmallPtrSet<SILBasicBlock *, 2> ExitBlocks;

	EpilogueARCBlockState &getState(SILBasicBlock *BB) {
	return IndexToStateMap[*PO->getPONumber(BB)];
	}

	/// Return true if this is a function exiting block this epilogue ARC
	/// matcher is interested in.
	bool isInterestedFunctionExitingBlock(SILBasicBlock *BB) {
	if (EpilogueARCKind::Release == Kind)
	return BB->getTerminator()->isFunctionExiting();

	return BB->getTerminator()->isFunctionExiting() &&
	BB->getTerminator()->getTermKind() != TermKind::ThrowInst;
	}

	/// Return true if this is a function exit block.
	bool isExitBlock(SILBasicBlock *BB) {
	return ExitBlocks.count(BB);
	}

	/// Return true if this is a retain instruction.
	bool isRetainInstruction(SILInstruction *II) {
	return isa<RetainValueInst>(II) \|\| isa<StrongRetainInst>(II);
	}

	/// Return true if this is a release instruction.
	bool isReleaseInstruction(SILInstruction *II) {
	return isa<ReleaseValueInst>(II) \|\| isa<StrongReleaseInst>(II);
	}

	SILValue getArg(SILBasicBlock *BB) {
	SILValue A = getState(BB).LocalArg;
	if (A)
	return A;
	return Arg;
	}

	public:
	/// Constructor.
	EpilogueARCContext(SILFunction F, PostOrderAnalysis PO, AliasAnalysis *AA,
	RCIdentityAnalysis *RCIA)
	: PO(F, PO), AA(AA), RCFI(F, RCIA) {}

	/// Run the data flow to find the epilogue retains or releases.
	bool run(EpilogueARCKind NewKind, SILValue NewArg) {
	Kind = NewKind;
	Arg = NewArg;

	// Initialize the epilogue arc data flow context.
	initializeDataflow();
	// Converge the data flow.
	if (!convergeDataflow())
	return false;
	// Lastly, find the epilogue ARC instructions.
	return computeEpilogueARC();
	}

	/// Reset the epilogue arc instructions.
	llvm::SmallSetVector<SILInstruction *, 1> getEpilogueARCInsts() {
	return EpilogueARCInsts;
	}

	void reset() {
	IndexToStateMap.clear();
	EpilogueARCInsts.clear();
	ExitBlocks.clear();
	EpilogueARCInsts.clear();
	}

	/// Initialize the data flow.
	void initializeDataflow();

	/// Keep iterating until the data flow is converged.
	bool convergeDataflow();

	/// Find the epilogue ARC instructions.
	bool computeEpilogueARC();

	/// This instruction prevents looking further for epilogue retains on the
	/// current path.
	bool mayBlockEpilogueRetain(SILInstruction *II, SILValue Ptr) {
	// reference decrementing instruction prevents any retain to be identified as
	// epilogue retains.
	if (mayDecrementRefCount(II, Ptr, AA))
	return true;
	// Handle self-recursion. A self-recursion can be considered a +1 on the
	// current argument.
	if (auto *AI = dyn_cast<ApplyInst>(II))
	if (AI->getCalleeFunction() == II->getParent()->getParent())
	return true;
	return false;
	}

	/// This instruction prevents looking further for epilogue releases on the
	/// current path.
	bool mayBlockEpilogueRelease(SILInstruction *II, SILValue Ptr) {
	// Check whether this instruction read reference count, i.e. uniqueness
	// check. Moving release past that may result in additional COW.
	return II->mayReleaseOrReadRefCount();
	}

	/// Does this instruction block the interested ARC instruction ?
	bool mayBlockEpilogueARC(SILInstruction *II, SILValue Ptr) {
	if (Kind == EpilogueARCKind::Retain)
	return mayBlockEpilogueRetain(II, Ptr);
	return mayBlockEpilogueRelease(II, Ptr);
	}

	/// This is the type of instructions the data flow is interested in.
	bool isInterestedInstruction(SILInstruction *II) {
	// We are checking for release.
	if (Kind == EpilogueARCKind::Release)
	return isReleaseInstruction(II) &&
	RCFI->getRCIdentityRoot(II->getOperand(0)) ==
	RCFI->getRCIdentityRoot(getArg(II->getParent()));
	// We are checking for retain. If this is a self-recursion. call
	// to the function (which returns an owned value) can be treated as
	// the retain instruction.
	if (auto *AI = dyn_cast<ApplyInst>(II))
	if (AI->getCalleeFunction() == II->getParent()->getParent())
	return true;
	// Check whether this is a retain instruction and the argument it
	// retains.
	return isRetainInstruction(II) &&
	RCFI->getRCIdentityRoot(II->getOperand(0)) ==
	RCFI->getRCIdentityRoot(getArg(II->getParent()));
	}
	};

	/// This class is a simple wrapper around an identity cache.
	class EpilogueARCFunctionInfo {
	using ARCInstructions = llvm::SmallSetVector<SILInstruction *, 1>;

	EpilogueARCContext Context;

	/// The epilogue retain cache.
	llvm::DenseMap<SILValue, ARCInstructions> EpilogueRetainInstCache;

	/// The epilogue release cache.
	llvm::DenseMap<SILValue, ARCInstructions> EpilogueReleaseInstCache;

	public:
	void handleDeleteNotification(ValueBase *V) {
	// Being conservative and clear everything for now.
	EpilogueRetainInstCache.clear();
	EpilogueReleaseInstCache.clear();
	}

	/// Constructor.
	EpilogueARCFunctionInfo(SILFunction F, PostOrderAnalysis PO,
	AliasAnalysis AA, RCIdentityAnalysis RC)
	: Context(F, PO, AA, RC) {}

	/// Find the epilogue ARC instruction based on the given \p Kind and given
	/// \p Arg.
	llvm::SmallSetVector<SILInstruction *, 1>
	computeEpilogueARCInstructions(EpilogueARCContext::EpilogueARCKind Kind,
	SILValue Arg) {
	auto &ARCCache = Kind == EpilogueARCContext::EpilogueARCKind::Retain ?
	EpilogueRetainInstCache :
	EpilogueReleaseInstCache;
	auto Iter = ARCCache.find(Arg);
	if (Iter != ARCCache.end())
	return Iter->second;

	// Initialize and run the data flow. Clear the epilogue arc instructions if the
	// data flow is aborted in middle.
	if (!Context.run(Kind, Arg)) {
	Context.reset();
	return llvm::SmallSetVector<SILInstruction *, 1>();
	}

	auto Result = Context.getEpilogueARCInsts();
	Context.reset();
	ARCCache[Arg] = Result;
	return Result;
	}
	};

	class EpilogueARCAnalysis : public FunctionAnalysisBase<EpilogueARCFunctionInfo> {
	/// Current post order analysis we are using.
	PostOrderAnalysis *PO;
	/// Current alias analysis we are using.
	AliasAnalysis *AA;
	/// Current RC Identity analysis we are using.
	RCIdentityAnalysis *RC;

	public:
	EpilogueARCAnalysis(SILModule *)
	: FunctionAnalysisBase<EpilogueARCFunctionInfo>(AnalysisKind::EpilogueARC),
	PO(nullptr), AA(nullptr), RC(nullptr) {}

	EpilogueARCAnalysis(const EpilogueARCAnalysis &) = delete;
	EpilogueARCAnalysis &operator=(const EpilogueARCAnalysis &) = delete;

	virtual void handleDeleteNotification(ValueBase *V) override {
	// If the parent function of this instruction was just turned into an
	// external declaration, bail. This happens during SILFunction destruction.
	SILFunction *F = V->getFunction();
	if (F->isExternalDeclaration()) {
	return;
	}

	// If we do have an analysis, tell it to handle its delete notifications.
	if (auto A = maybeGet(F)) {
	A.get()->handleDeleteNotification(V);
	}
	}

	virtual bool needsNotifications() override { return true; }

	static bool classof(const SILAnalysis *S) {
	return S->getKind() == AnalysisKind::EpilogueARC;
	}

	virtual void initialize(SILPassManager *PM) override;

	virtual EpilogueARCFunctionInfo newFunctionAnalysis(SILFunction F) override {
	return new EpilogueARCFunctionInfo(F, PO, AA, RC);
	}

	virtual bool shouldInvalidate(SILAnalysis::InvalidationKind K) override {
	return true;
	}

	};

	} // end swift namespace

	#endif