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

 //===--- AccessSummaryAnalysis.h - SIL Access Summary Analysis --*- 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 file implements an interprocedural analysis pass that summarizes
 // the formal accesses that a function makes to its address-type arguments.
 // These summaries are used to statically diagnose violations of exclusive
 // accesses for noescape closures.
 //
 //===----------------------------------------------------------------------===//
 #ifndef SWIFT_SILOPTIMIZER_ANALYSIS_ACCESS_SUMMARY_ANALYSIS_H_
 #define SWIFT_SILOPTIMIZER_ANALYSIS_ACCESS_SUMMARY_ANALYSIS_H_

 #include "swift/SIL/SILFunction.h"
 #include "swift/SIL/SILInstruction.h"
 #include "swift/SILOptimizer/Analysis/BottomUpIPAnalysis.h"
 #include "swift/SILOptimizer/Utils/IndexTrie.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"

 namespace swift {

 class AccessSummaryAnalysis : public BottomUpIPAnalysis {
 public:
   class SubAccessSummary {
   private:
     /// The kind of access begun on the argument.
     SILAccessKind Kind;

     /// The location of the access. Used for diagnostics.
     SILLocation AccessLoc = SILLocation((Expr *)nullptr);

     const IndexTrieNode *SubPath = nullptr;

   public:
     SubAccessSummary(SILAccessKind Kind, SILLocation AccessLoc,
                      const IndexTrieNode *SubPath)
         : Kind(Kind), AccessLoc(AccessLoc), SubPath(SubPath) {}

     SILAccessKind getAccessKind() const { return Kind; }

     SILLocation getAccessLoc() const { return AccessLoc; }

     const IndexTrieNode *getSubPath() const { return SubPath; }

     /// The lattice operation on SubAccessSummaries summaries.
     bool mergeWith(const SubAccessSummary &other);

     /// Merge in an access to the argument of the given kind at the given
     /// location with the given suppath. Returns true if the merge caused the
     /// summary to change.
     bool mergeWith(SILAccessKind otherKind, SILLocation otherLoc,
                    const IndexTrieNode *otherSubPath);

     /// Returns a description of the summary. For debugging and testing
     /// purposes.
     std::string getDescription(SILType BaseType, SILModule &M) const;
   };

   typedef llvm::SmallDenseMap<const IndexTrieNode *, SubAccessSummary, 8>
       SubAccessMap;

   /// Summarizes the accesses that a function begins on an argument, including
   /// the projection subpath that was accessed.
   class ArgumentSummary {
   private:
     SubAccessMap SubAccesses;

   public:
     /// The lattice operation on argument summaries.
     bool mergeWith(const ArgumentSummary &other);

     /// Merge in an access to the argument of the given kind at the given
     /// location. Returns true if the merge caused the summary to change.
     bool mergeWith(SILAccessKind otherKind, SILLocation otherLoc,
                    const IndexTrieNode *otherSubPath);

     /// Returns a description of the summary. For debugging and testing
     /// purposes.
     std::string getDescription(SILType BaseType, SILModule &M) const;

     /// Returns the accesses that the function performs to subpaths of the
     /// argument.
     const SubAccessMap &getSubAccesses() const { return SubAccesses; }

     /// Returns the sorted subaccess summaries into the passed-in storage.
     /// The accesses are sorted lexicographically by increasing subpath
     /// length and projection index.
     void getSortedSubAccesses(SmallVectorImpl<SubAccessSummary> &storage) const;
   };

   /// Summarizes the accesses that a function begins on its arguments or
   /// projections from its arguments.
   class FunctionSummary {
   private:
     llvm::SmallVector<ArgumentSummary, 6> ArgAccesses;

   public:
     FunctionSummary(unsigned argCount) : ArgAccesses(argCount) {}

     /// Returns of summary of the the function accesses that argument at the
     /// given index.
     ArgumentSummary &getAccessForArgument(unsigned argument) {
       return ArgAccesses[argument];
     }

     const ArgumentSummary &getAccessForArgument(unsigned argument) const {
       return ArgAccesses[argument];
     }

     /// Returns the number of argument in the summary.
     unsigned getArgumentCount() const { return ArgAccesses.size(); }

     void print(raw_ostream &os, SILFunction *fn) const;
   };

   class FunctionInfo;
   /// Records a flow of a caller's argument to a called function.
   /// This flow is used to iterate the interprocedural analysis to a fixpoint.
   struct ArgumentFlow {
     /// The index of the argument in the caller.
     const unsigned CallerArgumentIndex;

     /// The index of the argument in the callee.
     const unsigned CalleeArgumentIndex;

     FunctionInfo *const CalleeFunctionInfo;
   };

   /// Records the summary and argument flows for a given function.
   /// Used by the BottomUpIPAnalysis to propagate information
   /// from callees to callers.
   class FunctionInfo : public FunctionInfoBase<FunctionInfo> {
   private:
     FunctionSummary FS;

     SILFunction *F;

     llvm::SmallVector<ArgumentFlow, 8> RecordedArgumentFlows;

   public:
     FunctionInfo(SILFunction *F) : FS(F->getArguments().size()), F(F) {}

     SILFunction *getFunction() const { return F; }

     ArrayRef<ArgumentFlow> getArgumentFlows() const {
       return RecordedArgumentFlows;
     }

     const FunctionSummary &getSummary() const { return FS; }
     FunctionSummary &getSummary() { return FS; }

     /// Record a flow of an argument in this function to a callee.
     void recordFlow(const ArgumentFlow &flow) {
       flow.CalleeFunctionInfo->addCaller(this, nullptr);
       RecordedArgumentFlows.push_back(flow);
     }
   };

 private:
   /// Maps functions to the information the analysis keeps for each function.
   llvm::DenseMap<SILFunction *, FunctionInfo *> FunctionInfos;

   llvm::SpecificBumpPtrAllocator<FunctionInfo> Allocator;

   /// A trie of integer indices that gives pointer identity to a path of
   /// projections. This is shared between all functions in the module.
   std::unique_ptr<IndexTrieNode> SubPathTrie;

 public:
   AccessSummaryAnalysis() : BottomUpIPAnalysis(SILAnalysisKind::AccessSummary) {
     SubPathTrie.reset(new IndexTrieNode());
   }

   /// Returns a summary of the accesses performed by the given function.
   const FunctionSummary &getOrCreateSummary(SILFunction *Fn);

   IndexTrieNode *getSubPathTrieRoot() {
     return SubPathTrie.get();
   }

   /// Returns an IndexTrieNode that represents the single subpath accessed from
   /// BAI or the root if no such node exists.
   const IndexTrieNode *findSubPathAccessed(BeginAccessInst *BAI);

   virtual void initialize(SILPassManager *PM) override {}
   virtual void invalidate() override;
   virtual void invalidate(SILFunction *F, InvalidationKind K) override;
   virtual void notifyAddedOrModifiedFunction(SILFunction *F) override {}
   virtual void notifyWillDeleteFunction(SILFunction *F) override {
     invalidate(F, InvalidationKind::Nothing);
   }
   virtual void invalidateFunctionTables() override {}

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

   /// Returns a description of the subpath suitable for use in diagnostics.
   /// The base type must be the type of the root of the path.
   static std::string getSubPathDescription(SILType BaseType,
                                            const IndexTrieNode *SubPath,
                                            SILModule &M);

   /// Performs a lexicographic comparison of two subpaths, first by path length
   /// and then by index of the last path component. Returns true when lhs
   /// is less than rhs.
   static bool compareSubPaths(const IndexTrieNode *lhs,
                               const IndexTrieNode *rhs);
 private:
   typedef BottomUpFunctionOrder<FunctionInfo> FunctionOrder;

   /// Returns the BottomUpIPAnalysis information for the given function.
   FunctionInfo *getFunctionInfo(SILFunction *F);

   /// Summarizes the given function and iterates the interprocedural analysis
   /// to a fixpoint.
   void recompute(FunctionInfo *initial);

   /// Propagate the access summary from the argument of a called function
   /// to the caller.
   bool propagateFromCalleeToCaller(FunctionInfo *callerInfo,
                                    ArgumentFlow site);

   /// Summarize the given function and schedule it for interprocedural
   /// analysis.
   void processFunction(FunctionInfo *info, FunctionOrder &order);

   /// Summarize how the function uses the given argument.
   void processArgument(FunctionInfo *info, SILFunctionArgument *argment,
                         ArgumentSummary &summary, FunctionOrder &order);

   /// Summarize a partial_apply instruction.
   void processPartialApply(FunctionInfo *callerInfo,
                            unsigned callerArgumentIndex,
                            PartialApplyInst *apply,
                            Operand *applyArgumentOperand, FunctionOrder &order);

   /// Summarize apply or try_apply
   void processFullApply(FunctionInfo *callerInfo, unsigned callerArgumentIndex,
                         FullApplySite apply, Operand *argumentOperand,
                         FunctionOrder &order);

   /// Summarize a call site and schedule it for interprocedural analysis.
   void processCall(FunctionInfo *callerInfo, unsigned callerArgumentIndex,
                    SILFunction *calledFunction, unsigned argumentIndex,
                    FunctionOrder &order);
 };

 } // end namespace swift

 #endif
	//===--- AccessSummaryAnalysis.h - SIL Access Summary Analysis --- 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 file implements an interprocedural analysis pass that summarizes
	// the formal accesses that a function makes to its address-type arguments.
	// These summaries are used to statically diagnose violations of exclusive
	// accesses for noescape closures.
	//
	//===----------------------------------------------------------------------===//
	#ifndef SWIFT_SILOPTIMIZER_ANALYSIS_ACCESS_SUMMARY_ANALYSIS_H_
	#define SWIFT_SILOPTIMIZER_ANALYSIS_ACCESS_SUMMARY_ANALYSIS_H_

	#include "swift/SIL/SILFunction.h"
	#include "swift/SIL/SILInstruction.h"
	#include "swift/SILOptimizer/Analysis/BottomUpIPAnalysis.h"
	#include "swift/SILOptimizer/Utils/IndexTrie.h"
	#include "llvm/ADT/DenseMap.h"
	#include "llvm/ADT/SmallVector.h"

	namespace swift {

	class AccessSummaryAnalysis : public BottomUpIPAnalysis {
	public:
	class SubAccessSummary {
	private:
	/// The kind of access begun on the argument.
	SILAccessKind Kind;

	/// The location of the access. Used for diagnostics.
	SILLocation AccessLoc = SILLocation((Expr *)nullptr);

	const IndexTrieNode *SubPath = nullptr;

	public:
	SubAccessSummary(SILAccessKind Kind, SILLocation AccessLoc,
	const IndexTrieNode *SubPath)
	: Kind(Kind), AccessLoc(AccessLoc), SubPath(SubPath) {}

	SILAccessKind getAccessKind() const { return Kind; }

	SILLocation getAccessLoc() const { return AccessLoc; }

	const IndexTrieNode *getSubPath() const { return SubPath; }

	/// The lattice operation on SubAccessSummaries summaries.
	bool mergeWith(const SubAccessSummary &other);

	/// Merge in an access to the argument of the given kind at the given
	/// location with the given suppath. Returns true if the merge caused the
	/// summary to change.
	bool mergeWith(SILAccessKind otherKind, SILLocation otherLoc,
	const IndexTrieNode *otherSubPath);

	/// Returns a description of the summary. For debugging and testing
	/// purposes.
	std::string getDescription(SILType BaseType, SILModule &M) const;
	};

	typedef llvm::SmallDenseMap<const IndexTrieNode *, SubAccessSummary, 8>
	SubAccessMap;

	/// Summarizes the accesses that a function begins on an argument, including
	/// the projection subpath that was accessed.
	class ArgumentSummary {
	private:
	SubAccessMap SubAccesses;

	public:
	/// The lattice operation on argument summaries.
	bool mergeWith(const ArgumentSummary &other);

	/// Merge in an access to the argument of the given kind at the given
	/// location. Returns true if the merge caused the summary to change.
	bool mergeWith(SILAccessKind otherKind, SILLocation otherLoc,
	const IndexTrieNode *otherSubPath);

	/// Returns a description of the summary. For debugging and testing
	/// purposes.
	std::string getDescription(SILType BaseType, SILModule &M) const;

	/// Returns the accesses that the function performs to subpaths of the
	/// argument.
	const SubAccessMap &getSubAccesses() const { return SubAccesses; }

	/// Returns the sorted subaccess summaries into the passed-in storage.
	/// The accesses are sorted lexicographically by increasing subpath
	/// length and projection index.
	void getSortedSubAccesses(SmallVectorImpl<SubAccessSummary> &storage) const;
	};

	/// Summarizes the accesses that a function begins on its arguments or
	/// projections from its arguments.
	class FunctionSummary {
	private:
	llvm::SmallVector<ArgumentSummary, 6> ArgAccesses;

	public:
	FunctionSummary(unsigned argCount) : ArgAccesses(argCount) {}

	/// Returns of summary of the the function accesses that argument at the
	/// given index.
	ArgumentSummary &getAccessForArgument(unsigned argument) {
	return ArgAccesses[argument];
	}

	const ArgumentSummary &getAccessForArgument(unsigned argument) const {
	return ArgAccesses[argument];
	}

	/// Returns the number of argument in the summary.
	unsigned getArgumentCount() const { return ArgAccesses.size(); }

	void print(raw_ostream &os, SILFunction *fn) const;
	};

	class FunctionInfo;
	/// Records a flow of a caller's argument to a called function.
	/// This flow is used to iterate the interprocedural analysis to a fixpoint.
	struct ArgumentFlow {
	/// The index of the argument in the caller.
	const unsigned CallerArgumentIndex;

	/// The index of the argument in the callee.
	const unsigned CalleeArgumentIndex;

	FunctionInfo *const CalleeFunctionInfo;
	};

	/// Records the summary and argument flows for a given function.
	/// Used by the BottomUpIPAnalysis to propagate information
	/// from callees to callers.
	class FunctionInfo : public FunctionInfoBase<FunctionInfo> {
	private:
	FunctionSummary FS;

	SILFunction *F;

	llvm::SmallVector<ArgumentFlow, 8> RecordedArgumentFlows;

	public:
	FunctionInfo(SILFunction *F) : FS(F->getArguments().size()), F(F) {}

	SILFunction *getFunction() const { return F; }

	ArrayRef<ArgumentFlow> getArgumentFlows() const {
	return RecordedArgumentFlows;
	}

	const FunctionSummary &getSummary() const { return FS; }
	FunctionSummary &getSummary() { return FS; }

	/// Record a flow of an argument in this function to a callee.
	void recordFlow(const ArgumentFlow &flow) {
	flow.CalleeFunctionInfo->addCaller(this, nullptr);
	RecordedArgumentFlows.push_back(flow);
	}
	};

	private:
	/// Maps functions to the information the analysis keeps for each function.
	llvm::DenseMap<SILFunction , FunctionInfo > FunctionInfos;

	llvm::SpecificBumpPtrAllocator<FunctionInfo> Allocator;

	/// A trie of integer indices that gives pointer identity to a path of
	/// projections. This is shared between all functions in the module.
	std::unique_ptr<IndexTrieNode> SubPathTrie;

	public:
	AccessSummaryAnalysis() : BottomUpIPAnalysis(SILAnalysisKind::AccessSummary) {
	SubPathTrie.reset(new IndexTrieNode());
	}

	/// Returns a summary of the accesses performed by the given function.
	const FunctionSummary &getOrCreateSummary(SILFunction *Fn);

	IndexTrieNode *getSubPathTrieRoot() {
	return SubPathTrie.get();
	}

	/// Returns an IndexTrieNode that represents the single subpath accessed from
	/// BAI or the root if no such node exists.
	const IndexTrieNode findSubPathAccessed(BeginAccessInst BAI);

	virtual void initialize(SILPassManager *PM) override {}
	virtual void invalidate() override;
	virtual void invalidate(SILFunction *F, InvalidationKind K) override;
	virtual void notifyAddedOrModifiedFunction(SILFunction *F) override {}
	virtual void notifyWillDeleteFunction(SILFunction *F) override {
	invalidate(F, InvalidationKind::Nothing);
	}
	virtual void invalidateFunctionTables() override {}

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

	/// Returns a description of the subpath suitable for use in diagnostics.
	/// The base type must be the type of the root of the path.
	static std::string getSubPathDescription(SILType BaseType,
	const IndexTrieNode *SubPath,
	SILModule &M);

	/// Performs a lexicographic comparison of two subpaths, first by path length
	/// and then by index of the last path component. Returns true when lhs
	/// is less than rhs.
	static bool compareSubPaths(const IndexTrieNode *lhs,
	const IndexTrieNode *rhs);
	private:
	typedef BottomUpFunctionOrder<FunctionInfo> FunctionOrder;

	/// Returns the BottomUpIPAnalysis information for the given function.
	FunctionInfo getFunctionInfo(SILFunction F);

	/// Summarizes the given function and iterates the interprocedural analysis
	/// to a fixpoint.
	void recompute(FunctionInfo *initial);

	/// Propagate the access summary from the argument of a called function
	/// to the caller.
	bool propagateFromCalleeToCaller(FunctionInfo *callerInfo,
	ArgumentFlow site);

	/// Summarize the given function and schedule it for interprocedural
	/// analysis.
	void processFunction(FunctionInfo *info, FunctionOrder &order);

	/// Summarize how the function uses the given argument.
	void processArgument(FunctionInfo info, SILFunctionArgument argment,
	ArgumentSummary &summary, FunctionOrder &order);

	/// Summarize a partial_apply instruction.
	void processPartialApply(FunctionInfo *callerInfo,
	unsigned callerArgumentIndex,
	PartialApplyInst *apply,
	Operand *applyArgumentOperand, FunctionOrder &order);

	/// Summarize apply or try_apply
	void processFullApply(FunctionInfo *callerInfo, unsigned callerArgumentIndex,
	FullApplySite apply, Operand *argumentOperand,
	FunctionOrder &order);

	/// Summarize a call site and schedule it for interprocedural analysis.
	void processCall(FunctionInfo *callerInfo, unsigned callerArgumentIndex,
	SILFunction *calledFunction, unsigned argumentIndex,
	FunctionOrder &order);
	};

	} // end namespace swift

	#endif