text: //===------ SideEffectAnalysis.h - SIL Side Effect Analysis -*- C++ -*-----===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2015 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
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef SWIFT_SILANALYSIS_SIDEEFFECTANALYSIS_H_
  #define SWIFT_SILANALYSIS_SIDEEFFECTANALYSIS_H_
  
  #include "swift/SIL/SILInstruction.h"
  #include "swift/SIL/SILFunction.h"
  #include "swift/SILAnalysis/BottomUpIPAnalysis.h"
  #include "swift/SILAnalysis/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
  };
  
  /// 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 SideEffectAnalysis::FunctionEffects and
  /// SideEffectAnalysis::Effects.
  class SideEffectAnalysis : public BottomUpIPAnalysis {
  public:
  
    using MemoryBehavior = SILInstruction::MemoryBehavior;
    /// Set \p dest if \p src is set and return true if \p dest was not set
    /// before.
    static bool updateFlag(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 FunctionEffects.
    class Effects {
      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;
      }
  
      friend class SideEffectAnalysis;
      
    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 Effects &RHS) {
        bool Changed = false;
        Changed |= updateFlag(Reads, RHS.Reads);
        Changed |= updateFlag(Writes, RHS.Writes);
        Changed |= updateFlag(Retains, RHS.Retains);
        Changed |= updateFlag(Releases, RHS.Releases);
        return Changed;
      }
    };
  
    friend raw_ostream &operator<<(raw_ostream &os,
                                   const SideEffectAnalysis::Effects &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 FunctionEffects {
      
      /// Side-effects which can be associated to a parameter.
      llvm::SmallVector<Effects, 6> ParamEffects;
      
      /// All other side-effects which cannot be associated to a parameter.
      Effects 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().
      Effects 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 refernce count other than with retain or
      /// release instructions, e.g. isUnique?
      bool ReadsRC = false;
      
      /// Returns the effecs for an address or reference. This might be a
      /// parameter, the LocalEffects or, if the value can not be associated to one
      /// of them, the GlobalEffects.
      Effects *getEffectsOn(SILValue Addr);
      
      FunctionEffects(unsigned numParams) : ParamEffects(numParams) { }
  
      /// 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() {
        GlobalEffects.clear();
        for (Effects &PE : ParamEffects)
          PE.clear();
        AllocsObjects = false;
        Traps = false;
        ReadsRC = false;
      }
    
      /// Merge the flags from \p RHS.
      bool mergeFlags(const FunctionEffects &RHS) {
        bool Changed = false;
        Changed |= updateFlag(Traps, RHS.Traps);
        Changed |= updateFlag(AllocsObjects, RHS.AllocsObjects);
        Changed |= updateFlag(ReadsRC, RHS.ReadsRC);
        return Changed;
      }
      
      friend class SideEffectAnalysis;
      
    public:
      
      /// Constructs "empty" function effects.
      FunctionEffects() { }
  
      /// 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 refernce 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 Effects &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.
      ArrayRef<Effects> getParameterEffects() const { return ParamEffects; }
      
      /// Merge effects from \p RHS.
      bool mergeFrom(const FunctionEffects &RHS);
  
      /// Merge effects from an apply site within the function.
      bool mergeFromApply(const FunctionEffects &CalleeEffects,
                          FullApplySite FAS);
      
      /// Print the function effects.
      void dump() const;
    };
  
    friend raw_ostream &operator<<(raw_ostream &os,
                            const SideEffectAnalysis::FunctionEffects &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;
    }
  
  private:
  
    /// Stores the analysis data, i.e. the side-effects, for a function.
    struct FunctionInfo : public FunctionInfoBase<FunctionInfo> {
  
      /// The side-effects of the function.
      FunctionEffects FE;
  
      /// 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) :
        FE(F->empty() ? 0 : F->getArguments().size()), F(F) { }
  
      /// Clears the analysis data on invalidation.
      void clear() { FE.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 side-effect information for the whole module.
    llvm::DenseMap<SILFunction *, FunctionInfo *> Function2Info;
    
    /// The allocator for the map values in Function2Info.
    llvm::SpecificBumpPtrAllocator<FunctionInfo> Allocator;
    
    /// Callee analysis, used for determining the callees at call sites.
    BasicCalleeAnalysis *BCA;
  
    /// Get the side-effects of a function, which has an @effects attribute.
    /// Returns true if \a F has an @effects attribute which could be handled.
    static bool getDefinedEffects(FunctionEffects &Effects, SILFunction *F);
    
    /// Get the side-effects of a semantic call.
    /// Return true if \p ASC could be handled.
    bool getSemanticEffects(FunctionEffects &Effects, ArraySemanticsCall ASC);
    
    /// 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 *FInfo,
                         FunctionOrder &BottomUpOrder,
                         int RecursionDepth);
  
    /// 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(FunctionInfo *FInfo,
                            SILInstruction *I,
                            FunctionOrder &BottomUpOrder,
                            int RecursionDepth);
  
    /// Gets or creates FunctionEffects for \p F.
    FunctionInfo *getFunctionInfo(SILFunction *F) {
      FunctionInfo *&FInfo = Function2Info[F];
      if (!FInfo) {
        FInfo = new (Allocator.Allocate()) FunctionInfo(F);
      }
      return FInfo;
    }
  
    /// Recomputes the side-effect information for the function \p Initial and
    /// all called functions, up to a recursion depth of MaxRecursionDepth.
    void recompute(FunctionInfo *Initial);
  
  public:
    SideEffectAnalysis()
        : BottomUpIPAnalysis(AnalysisKind::SideEffect) {}
  
    static bool classof(const SILAnalysis *S) {
      return S->getKind() == AnalysisKind::SideEffect;
    }
    
    virtual void initialize(SILPassManager *PM) override;
    
    /// Get the side-effects of a function.
    const FunctionEffects &getEffects(SILFunction *F) {
      FunctionInfo *FInfo = getFunctionInfo(F);
      if (!FInfo->isValid())
        recompute(FInfo);
      return FInfo->FE;
    }
  
    /// Get the side-effects of a call site.
    void getEffects(FunctionEffects &ApplyEffects, FullApplySite FAS);
    
    /// No invalidation is needed. See comment for SideEffectAnalysis.
    virtual void invalidate(InvalidationKind K) override;
    
    /// No invalidation is needed. See comment for SideEffectAnalysis.
    virtual void invalidate(SILFunction *F, InvalidationKind K)  override;
  };
  
  } // end namespace swift
  
  #endif
  
  