text: //===--- DIMemoryUseCollector.h -------------------------------------------===//
  //
  // 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
  //
  //===----------------------------------------------------------------------===//
  //
  // This file declares logic used by definitive analysis related passes that look
  // at all the instructions that access a memory object.  This is quite specific
  // to definitive analysis in that it is tuple element sensitive instead of
  // relying on SROA.
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef SWIFT_SILOPTIMIZER_PASSMANAGER_DIMEMORYUSECOLLECTOR_H
  #define SWIFT_SILOPTIMIZER_PASSMANAGER_DIMEMORYUSECOLLECTOR_H
  
  #include "swift/Basic/LLVM.h"
  #include "swift/SIL/SILInstruction.h"
  #include "swift/SIL/SILType.h"
  #include "llvm/ADT/APInt.h"
  #include "llvm/ADT/TinyPtrVector.h"
  
  namespace swift {
  
  class SILBuilder;
  
  namespace ownership {
  
  struct DIElementUseInfo;
  
  /// This struct holds information about the memory object being analyzed that is
  /// required to correctly break it down into elements.
  ///
  /// This includes a collection of utilities for reasoning about (potentially
  /// recursively) exploded aggregate elements, and computing access paths and
  /// indexes into the flattened namespace.
  ///
  /// The flattened namespace is assigned lexicographically.  For example, in:
  ///   (Int, ((Float, (), Double)))
  /// the Int member is numbered 0, the Float is numbered 1, and the Double is
  /// numbered 2.  Empty tuples don't get numbered since they contain no state.
  ///
  /// Structs and classes have their elements exploded when we are analyzing the
  /// 'self' member in an initializer for the aggregate.
  ///
  /// Derived classes have an additional field at the end that models whether or
  /// not super.init() has been called or not.
  class DIMemoryObjectInfo {
    /// The uninitialized memory that we are analyzing.
    MarkUninitializedInst *MemoryInst;
  
    /// This is the base type of the memory allocation.
    SILType MemorySILType;
  
    /// This is the count of elements being analyzed.  For memory objects that are
    /// tuples, this is the flattened element count.  For 'self' members in init
    /// methods, this is the local field count (+1 for super/self classes were
    /// initialized).
    unsigned NumElements;
  
    /// True if the memory object being analyzed represents a 'let', which is
    /// initialize-only (reassignments are not allowed).
    bool IsLet = false;
  
    /// True if NumElements has a dummy value in it to force a struct to be
    /// non-empty.
    bool HasDummyElement = false;
  
  public:
    DIMemoryObjectInfo(MarkUninitializedInst *MemoryInst);
  
    SILLocation getLoc() const { return MemoryInst->getLoc(); }
    SILFunction &getFunction() const { return *MemoryInst->getFunction(); }
    SILModule &getModule() const { return MemoryInst->getModule(); }
    SILBasicBlock *getParentBlock() const { return MemoryInst->getParent(); }
  
    /// Return the first instruction of the function containing the memory object.
    SILInstruction *getFunctionEntryPoint() const;
  
    CanType getASTType() const { return MemorySILType.getASTType(); }
    SILType getType() const { return MemorySILType; }
  
    /// Returns true if this memory object is of trivial type.
    bool hasTrivialType() const { return MemorySILType.isTrivial(getFunction()); }
  
    /// Returns true if NumElements has a dummy value in it to force a struct to
    /// be non-empty.
    bool hasDummyElement() const { return HasDummyElement; }
  
    /// Return the actual 'uninitialized' memory. In the case of alloc_ref,
    /// alloc_stack, this always just returns the actual mark_uninitialized
    /// instruction. For alloc_box though it returns the project_box associated
    /// with the memory info.
    SingleValueInstruction *getUninitializedValue() const {
      if (auto *mui = dyn_cast<MarkUninitializedInst>(MemoryInst)) {
        if (auto *pbi = mui->getSingleUserOfType<ProjectBoxInst>()) {
          return pbi;
        }
      }
      return MemoryInst;
    }
  
    /// Return the number of elements, without the extra "super.init" tracker in
    /// initializers of derived classes.
    unsigned getNumMemoryElements() const {
      return NumElements - (unsigned)isDerivedClassSelf();
    }
  
    /// Return the number of elements, including the extra "super.init" tracker in
    /// initializers of derived classes.
    ///
    /// \see getNumMemoryElements() for the number of elements, excluding the
    /// extra "super.init" tracker in the initializers of derived classes.
    unsigned getNumElements() const { return NumElements; }
  
    /// Return true if this is 'self' in any kind of initializer.
    bool isAnyInitSelf() const { return !MemoryInst->isVar(); }
  
    /// True if the memory object is the 'self' argument of a struct initializer.
    bool isStructInitSelf() const {
      if (MemoryInst->isRootSelf() || MemoryInst->isCrossModuleRootSelf()) {
        if (auto decl = getASTType()->getAnyNominal()) {
          if (isa<StructDecl>(decl)) {
            return true;
          }
        }
      }
      return false;
    }
  
    /// True if the memory object is the 'self' argument of a non-delegating
    /// cross-module struct initializer.
    bool isCrossModuleStructInitSelf() const {
      if (MemoryInst->isCrossModuleRootSelf()) {
        assert(isStructInitSelf());
        return true;
      }
      return false;
    }
  
    /// True if the memory object is the 'self' argument of a class designated
    /// initializer.
    bool isClassInitSelf() const {
      if (MemoryInst->isDelegatingSelf())
        return false;
  
      if (!MemoryInst->isVar()) {
        if (auto decl = getASTType()->getAnyNominal()) {
          if (isa<ClassDecl>(decl)) {
            return true;
          }
        }
      }
      return false;
    }
  
    /// True if this memory object is the 'self' of a derived class initializer.
    bool isDerivedClassSelf() const { return MemoryInst->isDerivedClassSelf(); }
  
    /// True if this memory object is the 'self' of a derived class initializer for
    /// which we can assume that all ivars have been initialized.
    bool isDerivedClassSelfOnly() const {
      return MemoryInst->isDerivedClassSelfOnly();
    }
  
    /// True if this memory object is the 'self' of a derived class init method,
    /// regardless of whether we're tracking ivar initializations or not.
    bool isAnyDerivedClassSelf() const {
      return MemoryInst->isDerivedClassSelf() ||
             MemoryInst->isDerivedClassSelfOnly();
    }
  
    /// True if this memory object is the 'self' of a non-root class init method.
    bool isNonRootClassSelf() const {
      return isClassInitSelf() && !MemoryInst->isRootSelf();
    }
  
    /// True if this is a delegating initializer, one that calls 'self.init'.
    bool isDelegatingInit() const {
      return MemoryInst->isDelegatingSelf() ||
             MemoryInst->isDelegatingSelfAllocated();
    }
  
    /// True if this is an initializer that initializes stored properties.
    bool isNonDelegatingInit() const {
      switch (MemoryInst->getKind()) {
      case MarkUninitializedInst::Var:
        return false;
      case MarkUninitializedInst::RootSelf:
      case MarkUninitializedInst::CrossModuleRootSelf:
      case MarkUninitializedInst::DerivedSelf:
      case MarkUninitializedInst::DerivedSelfOnly:
        return true;
      case MarkUninitializedInst::DelegatingSelf:
      case MarkUninitializedInst::DelegatingSelfAllocated:
        return false;
      }
      return false;
    }
  
    bool isRootSelf() const {
      return MemoryInst->getKind() == MarkUninitializedInst::RootSelf;
    }
  
    bool isDelegatingSelfAllocated() const {
      return MemoryInst->isDelegatingSelfAllocated();
    }
  
    enum class EndScopeKind { Borrow, Access };
  
    /// Given an element number (in the flattened sense) return a pointer to a
    /// leaf element of the specified number.
    SILValue emitElementAddressForDestroy(
        unsigned TupleEltNo, SILLocation Loc, SILBuilder &B,
        SmallVectorImpl<std::pair<SILValue, EndScopeKind>> &EndScopeList) const;
  
    /// Return the swift type of the specified element.
    SILType getElementType(unsigned EltNo) const;
  
    /// Push the symbolic path name to the specified element number onto the
    /// specified std::string.  If the actual decl (or a subelement thereof) can
    /// be determined, return it.  Otherwise, return null.
    ValueDecl *getPathStringToElement(unsigned Element,
                                      std::string &Result) const;
  
    /// If the specified value is a 'let' property in an initializer, return true.
    bool isElementLetProperty(unsigned Element) const;
  };
  
  enum DIUseKind {
    /// The instruction is a Load.
    Load,
  
    /// The instruction is either an initialization or an assignment, we don't
    /// know which.  This classification only happens with values of trivial type
    /// where the different isn't significant.
    InitOrAssign,
  
    /// The instruction is an initialization of the tuple element.
    Initialization,
  
    /// The instruction is an assignment, overwriting an already initialized
    /// value.
    Assign,
  
    /// The instruction is a store to a member of a larger struct value.
    PartialStore,
  
    /// An 'inout' argument of a function application.
    InOutArgument,
  
    /// An 'inout' self argument of a function application.
    InOutSelfArgument,
  
    /// An indirect 'in' parameter of an Apply instruction.
    IndirectIn,
  
    /// This instruction is a general escape of the value, e.g. a call to a
    /// closure that captures it.
    Escape,
  
    /// This instruction is a call to 'self.init' in a delegating initializer,
    /// or a call to 'super.init' in a designated initializer of a derived class..
    SelfInit,
    
    /// This instruction is a load that's only used to answer a `type(of: self)`
    /// question.
    LoadForTypeOfSelf,
  };
  
  /// This struct represents a single classified access to the memory object
  /// being analyzed, along with classification information about the access.
  struct DIMemoryUse {
    /// This is the instruction accessing the memory.
    SILInstruction *Inst;
  
    /// This is what kind of access it is, load, store, escape, etc.
    DIUseKind Kind;
  
    /// For memory objects of (potentially recursive) tuple type, this keeps
    /// track of which tuple elements are affected.
    unsigned short FirstElement, NumElements;
  
    DIMemoryUse(SILInstruction *Inst, DIUseKind Kind, unsigned FE, unsigned NE)
        : Inst(Inst), Kind(Kind), FirstElement(FE), NumElements(NE) {
      assert(FE == FirstElement && NumElements == NE &&
             "more than 64K elements not supported yet");
    }
  
    DIMemoryUse() : Inst(nullptr) {}
  
    bool isInvalid() const { return Inst == nullptr; }
    bool isValid() const { return Inst != nullptr; }
  
    bool usesElement(unsigned i) const {
      return i >= FirstElement &&
             i < static_cast<unsigned>(FirstElement + NumElements);
    }
  
    /// onlyTouchesTrivialElements - Return true if all of the accessed elements
    /// have trivial type and the access itself is a trivial instruction.
    bool onlyTouchesTrivialElements(const DIMemoryObjectInfo &MemoryInfo) const;
  
    /// getElementBitmask - Return a bitmask with the touched tuple elements
    /// set.
    APInt getElementBitmask(unsigned NumMemoryTupleElements) const {
      return APInt::getBitsSet(NumMemoryTupleElements, FirstElement,
                               FirstElement + NumElements);
    }
  };
  
  struct DIElementUseInfo {
    SmallVector<DIMemoryUse, 16> Uses;
    SmallVector<SILInstruction *, 4> Releases;
    TinyPtrVector<SILInstruction *> StoresToSelf;
  
    void trackUse(DIMemoryUse Use) { Uses.push_back(Use); }
  
    void trackDestroy(SILInstruction *Destroy) { Releases.push_back(Destroy); }
  
    void trackStoreToSelf(SILInstruction *I);
  };
  
  /// collectDIElementUsesFrom - Analyze all uses of the specified allocation
  /// instruction (alloc_box, alloc_stack or mark_uninitialized), classifying them
  /// and storing the information found into the Uses and Releases lists.
  void collectDIElementUsesFrom(const DIMemoryObjectInfo &MemoryInfo,
                                DIElementUseInfo &UseInfo);
  
  } // end namespace ownership
  } // end namespace swift
  
  #endif
  