| //===--- SideEffectAnalysis.h - SIL Side Effect Analysis --------*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2018 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SWIFT_SILOPTIMIZER_ANALYSIS_SIDEEFFECTANALYSIS_H |
| #define SWIFT_SILOPTIMIZER_ANALYSIS_SIDEEFFECTANALYSIS_H |
| |
| #include "swift/SIL/ApplySite.h" |
| #include "swift/SIL/SILInstruction.h" |
| #include "swift/SIL/SILFunction.h" |
| #include "swift/SILOptimizer/Analysis/BottomUpIPAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/ArraySemantic.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallVector.h" |
| |
| namespace swift { |
| |
| class BasicCalleeAnalysis; |
| |
| |
| /// An enum to represent the kind of scan we perform when we calculate |
| /// side effects. |
| enum class RetainObserveKind { |
| ObserveRetains, |
| IgnoreRetains, |
| RetainObserveKindEnd |
| }; |
| |
| /// Generic base class for any bottom up analysis that summarizes per-function |
| /// "effects" by first computing local effects, then propagating those effects |
| /// bottom-up through the call graph. |
| /// |
| /// FunctionEffects constraints: |
| /// - void clear() |
| /// - void setWorstEffects() |
| /// - bool summarizeFunction(SILFunction *) |
| /// - bool summarizeCall(FullApplySite) |
| /// - bool mergeFrom(const FunctionSideEffects &) |
| /// - bool mergeFromApply(const FunctionEffects &, FullApplySite) |
| /// - void analyzeInstruction(SILInstruction *) |
| template <typename FunctionEffects> |
| class GenericFunctionEffectAnalysis : public BottomUpIPAnalysis { |
| |
| /// Stores the analysis data, e.g. side-effects, for a function. |
| struct FunctionInfo : public FunctionInfoBase<FunctionInfo> { |
| |
| /// The function effects. |
| FunctionEffects functionEffects; |
| |
| /// Back-link to the function. |
| SILFunction *F; |
| |
| /// Used during recomputation to indicate if the side-effects of a caller |
| /// must be updated. |
| bool needUpdateCallers = false; |
| |
| FunctionInfo(SILFunction *F) : F(F) {} |
| |
| /// Clears the analysis data on invalidation. |
| void clear() { functionEffects.clear(); } |
| }; |
| |
| typedef BottomUpFunctionOrder<FunctionInfo> FunctionOrder; |
| |
| enum { |
| /// The maximum call-graph recursion depth for recomputing the analysis. |
| /// This is a relatively small number to reduce compile time in case of |
| /// large cycles in the call-graph. |
| /// In case of no cycles, we should not hit this limit at all because the |
| /// pass manager processes functions in bottom-up order. |
| MaxRecursionDepth = 5 |
| }; |
| |
| /// All the function effect information for the whole module. |
| llvm::DenseMap<SILFunction *, FunctionInfo *> functionInfoMap; |
| |
| /// The allocator for the map of values in FunctionInfoMap. |
| llvm::SpecificBumpPtrAllocator<FunctionInfo> allocator; |
| |
| /// Callee analysis, used for determining the callees at call sites. |
| BasicCalleeAnalysis *BCA; |
| |
| public: |
| GenericFunctionEffectAnalysis(SILAnalysisKind kind) |
| : BottomUpIPAnalysis(kind) {} |
| |
| const FunctionEffects &getEffects(SILFunction *F) { |
| FunctionInfo *functionInfo = getFunctionInfo(F); |
| if (!functionInfo->isValid()) |
| recompute(functionInfo); |
| return functionInfo->functionEffects; |
| } |
| |
| /// Get the merged effects of all callees at the given call site from the |
| /// callee's perspective (don't transform parameter effects). |
| void getCalleeEffects(FunctionEffects &calleeEffects, |
| FullApplySite fullApply); |
| |
| /// Get the merge effects of all callees at the given call site from the |
| /// caller's perspective. Parameter effects are translated into information |
| /// for the caller's arguments, and local effects are dropped. |
| void getCallSiteEffects(FunctionEffects &callEffects, |
| FullApplySite fullApply) { |
| FunctionEffects calleeEffects; |
| getCalleeEffects(calleeEffects, fullApply); |
| callEffects.mergeFromApply(calleeEffects, fullApply); |
| } |
| |
| virtual void initialize(SILPassManager *PM) override; |
| |
| /// Invalidate all information in this analysis. |
| virtual void invalidate() override; |
| |
| /// Invalidate all of the information for a specific function. |
| virtual void invalidate(SILFunction *F, InvalidationKind K) override; |
| |
| /// Notify the analysis about a newly created function. |
| virtual void notifyAddedOrModifiedFunction(SILFunction *F) override {} |
| |
| /// Notify the analysis about a function which will be deleted from the |
| /// module. |
| virtual void notifyWillDeleteFunction(SILFunction *F) override { |
| invalidate(F, InvalidationKind::Nothing); |
| } |
| |
| /// Notify the analysis about changed witness or vtables. |
| virtual void invalidateFunctionTables() override {} |
| |
| private: |
| /// Gets or creates FunctionEffects for \p F. |
| FunctionInfo *getFunctionInfo(SILFunction *F) { |
| FunctionInfo *&functionInfo = functionInfoMap[F]; |
| if (!functionInfo) { |
| functionInfo = new (allocator.Allocate()) FunctionInfo(F); |
| } |
| return functionInfo; |
| } |
| |
| /// Analyze the side-effects of a function, including called functions. |
| /// Visited callees are added to \p BottomUpOrder until \p RecursionDepth |
| /// reaches MaxRecursionDepth. |
| void analyzeFunction(FunctionInfo *functionInfo, FunctionOrder &bottomUpOrder, |
| int recursionDepth); |
| |
| void analyzeCall(FunctionInfo *functionInfo, FullApplySite fullApply, |
| FunctionOrder &bottomUpOrder, int recursionDepth); |
| |
| /// Recomputes the side-effect information for the function \p Initial and |
| /// all called functions, up to a recursion depth of MaxRecursionDepth. |
| void recompute(FunctionInfo *initialInfo); |
| }; |
| |
| /// Set \p dest if \p src is set and return true if \p dest was not set |
| /// before. |
| static bool changedFlagByInPlaceOr(bool &dest, bool src) { |
| if (src && !dest) { |
| dest = src; |
| return true; |
| } |
| return false; |
| } |
| |
| /// Side-effect information for the function (global effects) or a specific |
| /// parameter of the function. See FunctionSideEffects. |
| class FunctionSideEffectFlags { |
| friend class FunctionSideEffects; |
| using MemoryBehavior = SILInstruction::MemoryBehavior; |
| |
| bool Reads = false; |
| bool Writes = false; |
| bool Retains = false; |
| bool Releases = false; |
| |
| /// Sets the most conservative effects. |
| void setWorstEffects() { |
| Reads = true; |
| Writes = true; |
| Retains = true; |
| Releases = true; |
| } |
| |
| /// Clears all effects. |
| void clear() { |
| Reads = false; |
| Writes = false; |
| Retains = false; |
| Releases = false; |
| } |
| |
| public: |
| /// Does the function read from memory (excluding reads from locally |
| /// allocated memory)? |
| bool mayRead() const { return Reads; } |
| |
| /// Does the function write to memory (excluding writes to locally |
| /// allocated memory)? |
| bool mayWrite() const { return Writes; } |
| |
| /// Does the function retain objects (excluding retains of locally |
| /// allocated objects)? |
| bool mayRetain() const { return Retains; } |
| |
| /// Does the function release objects (excluding releases of locally |
| /// allocated objects)? |
| bool mayRelease() const { return Releases; } |
| |
| /// Gets the memory behavior considering the global effects and |
| /// all parameter effects. If \p ScanKind equals ignoreRetains then retain |
| /// instructions are considered as side effects. |
| MemoryBehavior getMemBehavior(RetainObserveKind ScanKind) const { |
| if (mayRelease()) |
| return MemoryBehavior::MayHaveSideEffects; |
| |
| if (ScanKind == RetainObserveKind::ObserveRetains && mayRetain()) |
| return MemoryBehavior::MayHaveSideEffects; |
| |
| if (mayWrite()) |
| return mayRead() ? MemoryBehavior::MayReadWrite |
| : MemoryBehavior::MayWrite; |
| |
| if (mayRead()) |
| return MemoryBehavior::MayRead; |
| |
| return MemoryBehavior::None; |
| } |
| |
| /// Merge effects from \p RHS. |
| bool mergeFrom(const FunctionSideEffectFlags &RHS) { |
| bool Changed = false; |
| Changed |= changedFlagByInPlaceOr(Reads, RHS.Reads); |
| Changed |= changedFlagByInPlaceOr(Writes, RHS.Writes); |
| Changed |= changedFlagByInPlaceOr(Retains, RHS.Retains); |
| Changed |= changedFlagByInPlaceOr(Releases, RHS.Releases); |
| return Changed; |
| } |
| |
| friend raw_ostream &operator<<(raw_ostream &os, |
| const FunctionSideEffectFlags &Effects) { |
| if (Effects.mayRead()) |
| os << 'r'; |
| if (Effects.mayWrite()) |
| os << 'w'; |
| if (Effects.mayRetain()) |
| os << '+'; |
| if (Effects.mayRelease()) |
| os << '-'; |
| return os; |
| } |
| }; |
| |
| /// Summarizes the side-effects of a function. The side-effect information |
| /// is divided into global effects and effects for specific function |
| /// parameters. |
| /// If a side-effect can be associated to a specific function parameter, it is |
| /// not added to the global effects of the function. E.g. if a memory write is |
| /// only done through an @inout parameter, the mayWrite side-effect is only |
| /// accounted for this parameter. |
| /// Effects for a parameter make only sense if the parameter is implemented as |
| /// a pointer or contains a pointer: |
| /// *) The parameter is an address parameter, e.g. @out, @inout, etc. |
| /// *) The parameter is a reference |
| /// *) The parameter is a value type (e.g. struct) and contains a reference. |
| /// In this case the effects refer to all references in the value type. |
| /// E.g. if a struct contains 2 references, a mayWrite effect means that |
| /// memory is written to one of the referenced objects (or to both). |
| class FunctionSideEffects { |
| using MemoryBehavior = SILInstruction::MemoryBehavior; |
| |
| /// Side-effects which can be associated to a parameter. |
| llvm::SmallVector<FunctionSideEffectFlags, 6> ParamEffects; |
| |
| /// All other side-effects which cannot be associated to a parameter. |
| FunctionSideEffectFlags GlobalEffects; |
| |
| /// Side-effects on locally allocated storage. Such side-effects are not |
| /// relevant to optimizations. The LocalEffects are only used to return |
| /// "something" for local storage in getEffectsOn(). |
| FunctionSideEffectFlags LocalEffects; |
| |
| /// Does the function allocate objects, boxes, etc., i.e. everything which |
| /// has a reference count. |
| bool AllocsObjects = false; |
| |
| /// Can this function trap or exit the program in any way? |
| bool Traps = false; |
| |
| /// Does this function read a reference count other than with retain or |
| /// release instructions, e.g. isUnique? |
| bool ReadsRC = false; |
| |
| /// Returns the effects for an address or reference. This might be a |
| /// parameter, the LocalEffects or, if the value cannot be associated to one |
| /// of them, the GlobalEffects. |
| FunctionSideEffectFlags *getEffectsOn(SILValue Addr); |
| |
| public: |
| /// Constructs "empty" function effects. This effects object can later be |
| /// populated by summarizeFunction or summarizeCall. |
| FunctionSideEffects() {} |
| |
| /// Sets the most conservative effects, if we don't know anything about the |
| /// function. |
| void setWorstEffects() { |
| GlobalEffects.setWorstEffects(); |
| AllocsObjects = true; |
| Traps = true; |
| ReadsRC = true; |
| } |
| |
| /// Clears all effects. |
| void clear() { |
| ParamEffects.clear(); |
| GlobalEffects.clear(); |
| AllocsObjects = false; |
| Traps = false; |
| ReadsRC = false; |
| } |
| |
| /// Merge the flags from \p RHS. |
| bool mergeFlags(const FunctionSideEffects &RHS) { |
| bool Changed = false; |
| Changed |= changedFlagByInPlaceOr(Traps, RHS.Traps); |
| Changed |= changedFlagByInPlaceOr(AllocsObjects, RHS.AllocsObjects); |
| Changed |= changedFlagByInPlaceOr(ReadsRC, RHS.ReadsRC); |
| return Changed; |
| } |
| |
| // Summarize the given function's effects using this FunctionSideEffects |
| // object. |
| // |
| // Return true if the function's' effects have been fully summarized without |
| // visiting it's body. |
| bool summarizeFunction(SILFunction *F); |
| |
| /// Summarize the callee side effects of a call instruction using this |
| /// FunctionSideEffects object without analyzing the callee function bodies or |
| /// scheduling the callees for bottom-up propagation. |
| /// |
| /// The side effects are represented from the callee's perspective. Parameter |
| /// effects are not translated into information on the caller's argument, and |
| /// local effects are not dropped. |
| /// |
| /// Return true if this call-site's effects are summarized without visiting |
| /// the callee. |
| bool summarizeCall(FullApplySite fullApply); |
| |
| /// Merge effects directly from \p RHS. |
| bool mergeFrom(const FunctionSideEffects &RHS); |
| |
| /// Merge the effects represented in CalleeEffects into this |
| /// FunctionSideEffects object. CalleeEffects must correspond to at least one |
| /// callee at the apply site `FAS`. Merging drops any local effects, and |
| /// translates parameter effects into effects on the caller-side arguments. |
| /// |
| /// The full caller-side effects at a call site can be obtained with |
| /// SideEffectsAnalysis::getCallSiteEffects(). |
| bool mergeFromApply(const FunctionSideEffects &CalleeEffects, |
| FullApplySite FAS); |
| |
| /// Analyze the side-effects of a single SIL instruction \p I. |
| /// Visited callees are added to \p BottomUpOrder until \p RecursionDepth |
| /// reaches MaxRecursionDepth. |
| void analyzeInstruction(SILInstruction *I); |
| |
| /// Print the function effects. |
| void dump() const; |
| |
| /// Does the function allocate objects, boxes, etc., i.e. everything which |
| /// has a reference count. |
| bool mayAllocObjects() const { return AllocsObjects; } |
| |
| /// Can this function trap or exit the program in any way? |
| bool mayTrap() const { return Traps; } |
| |
| /// Does this function read a reference count other than with retain or |
| /// release instructions, e.g. isUnique? |
| bool mayReadRC() const { return ReadsRC; } |
| |
| /// Gets the memory behavior considering the global effects and |
| /// all parameter effects. If \p ScanKind equals ignoreRetains then retain |
| /// instructions are considered as side effects. |
| MemoryBehavior getMemBehavior(RetainObserveKind ScanKind) const; |
| |
| /// Get the global effects for the function. These are effects which cannot |
| /// be associated to a specific parameter, e.g. writes to global variables |
| /// or writes to unknown pointers. |
| const FunctionSideEffectFlags &getGlobalEffects() const { |
| return GlobalEffects; |
| } |
| |
| /// Get the array of parameter effects. If a side-effect can be associated |
| /// to a specific parameter, it is contained here instead of the global |
| /// effects. |
| /// Note that if a parameter effect is mayRelease(), it means that the |
| /// global function effects can be anything, because the destructor of an |
| /// object can have arbitrary side effects. |
| ArrayRef<FunctionSideEffectFlags> getParameterEffects() const { |
| return ParamEffects; |
| } |
| |
| protected: |
| /// Set the side-effects of a function, which has an @_effects attribute. |
| /// Returns true if \a F has an @_effects attribute which could be handled. |
| bool setDefinedEffects(SILFunction *F); |
| |
| /// Set the side-effects of a semantic call. |
| /// Return true if \p ASC could be handled. |
| bool setSemanticEffects(ArraySemanticsCall ASC); |
| |
| friend raw_ostream &operator<<(raw_ostream &os, |
| const FunctionSideEffects &Effects) { |
| os << "func=" << Effects.getGlobalEffects(); |
| int ParamIdx = 0; |
| for (auto &E : Effects.getParameterEffects()) { |
| os << ",param" << ParamIdx++ << "=" << E; |
| } |
| if (Effects.mayAllocObjects()) |
| os << ";alloc"; |
| if (Effects.mayTrap()) |
| os << ";trap"; |
| if (Effects.mayReadRC()) |
| os << ";readrc"; |
| return os; |
| } |
| }; |
| |
| /// The SideEffectAnalysis provides information about side-effects of SIL |
| /// functions. Side-effect information is provided per function and includes: |
| /// Does the function read or write memory? Does the function retain or release |
| /// objects? etc. |
| /// For details see FunctionSideEffects. |
| class SideEffectAnalysis |
| : public GenericFunctionEffectAnalysis<FunctionSideEffects> { |
| public: |
| SideEffectAnalysis() |
| : GenericFunctionEffectAnalysis<FunctionSideEffects>( |
| SILAnalysisKind::SideEffect) {} |
| |
| static bool classof(const SILAnalysis *S) { |
| return S->getKind() == SILAnalysisKind::SideEffect; |
| } |
| }; |
| |
| } // end namespace swift |
| |
| #endif // SWIFT_SILOPTIMIZER_ANALYSIS_SIDEEFFECTANALYSIS_H |