text: //===--- EscapeAnalysis.cpp - SIL Escape Analysis -------------------------===//
  //
  // 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
  //
  //===----------------------------------------------------------------------===//
  
  #define DEBUG_TYPE "sil-escape"
  #include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
  #include "swift/SIL/DebugUtils.h"
  #include "swift/SIL/PrettyStackTrace.h"
  #include "swift/SIL/SILArgument.h"
  #include "swift/SILOptimizer/Analysis/ArraySemantic.h"
  #include "swift/SILOptimizer/Analysis/BasicCalleeAnalysis.h"
  #include "swift/SILOptimizer/PassManager/PassManager.h"
  #include "swift/SILOptimizer/Utils/BasicBlockOptUtils.h"
  #include "swift/SILOptimizer/Utils/InstOptUtils.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/GraphWriter.h"
  #include "llvm/Support/raw_ostream.h"
  
  using namespace swift;
  using CGNode = EscapeAnalysis::CGNode;
  
  static llvm::cl::opt<bool> EnableInternalVerify(
      "escapes-internal-verify",
      llvm::cl::desc("Enable internal verification of escape analysis"),
      llvm::cl::init(false));
  
  // Returns the kind of pointer that \p Ty recursively contains.
  EscapeAnalysis::PointerKind
  EscapeAnalysis::findRecursivePointerKind(SILType Ty,
                                           const SILFunction &F) const {
    // An address may be converted into a reference via something like
    // raw_pointer_to_ref, but in general we don't know what kind of pointer it
    // is.
    if (Ty.isAddress())
      return EscapeAnalysis::AnyPointer;
  
    // Opaque types may contain a reference. Speculatively track them too.
    //
    // 1. It may be possible to optimize opaque values based on known mutation
    // points.
    //
    // 2. A specialized function may call a generic function passing a concrete
    // reference type via incomplete specialization.
    //
    // 3. A generic function may call a specialized function taking a concrete
    // reference type via devirtualization.
    if (Ty.isAddressOnly(F))
      return EscapeAnalysis::AnyPointer;
  
    // A raw pointer definitely does not have a reference, but could point
    // anywhere. We do track these because critical stdlib data structures often
    // use raw pointers under the hood.
    if (Ty.getASTType() == F.getModule().getASTContext().TheRawPointerType)
      return EscapeAnalysis::AnyPointer;
  
    if (Ty.hasReferenceSemantics())
      return EscapeAnalysis::ReferenceOnly;
  
    auto &M = F.getModule();
  
    // Start with the most precise pointer kind
    PointerKind aggregateKind = NoPointer;
    auto meetAggregateKind = [&](PointerKind otherKind) {
      if (otherKind > aggregateKind)
        aggregateKind = otherKind;
    };
    if (auto *Str = Ty.getStructOrBoundGenericStruct()) {
      for (auto *Field : Str->getStoredProperties()) {
        SILType fieldTy = Ty.getFieldType(Field, M, F.getTypeExpansionContext())
                              .getObjectType();
        meetAggregateKind(findCachedPointerKind(fieldTy, F));
      }
      return aggregateKind;
    }
    if (auto TT = Ty.getAs<TupleType>()) {
      for (unsigned i = 0, e = TT->getNumElements(); i != e; ++i) {
        meetAggregateKind(findCachedPointerKind(Ty.getTupleElementType(i), F));
      }
      return aggregateKind;
    }
    if (auto En = Ty.getEnumOrBoundGenericEnum()) {
      for (auto *ElemDecl : En->getAllElements()) {
        if (!ElemDecl->hasAssociatedValues())
          continue;
        SILType eltTy =
            Ty.getEnumElementType(ElemDecl, M, F.getTypeExpansionContext());
        meetAggregateKind(findCachedPointerKind(eltTy, F));
      }
      return aggregateKind;
    }
    // FIXME: without a covered switch, this is not robust in the event that new
    // reference-holding AST types are invented.
    return NoPointer;
  }
  
  // Return the PointerKind that summarizes a class's stored properties.
  //
  // If a class only holds fields of non-pointer types, then it is guaranteed not
  // to point to any other objects.
  EscapeAnalysis::PointerKind
  EscapeAnalysis::findClassPropertiesPointerKind(SILType Ty,
                                                 const SILFunction &F) const {
    if (Ty.isAddress())
      return AnyPointer;
  
    auto *classDecl = Ty.getClassOrBoundGenericClass();
    if (!classDecl)
      return AnyPointer;
  
    auto &M = F.getModule();
    auto expansion = F.getTypeExpansionContext();
  
    // Start with the most precise pointer kind
    PointerKind propertiesKind = NoPointer;
    auto meetAggregateKind = [&](PointerKind otherKind) {
      if (otherKind > propertiesKind)
        propertiesKind = otherKind;
    };
    for (Type classTy = Ty.getASTType(); classTy;
         classTy = classTy->getSuperclass()) {
      classDecl = classTy->getClassOrBoundGenericClass();
      assert(classDecl && "superclass must be a class");
  
      // Return AnyPointer unless we have guaranteed visibility into all class and
      // superclass properties. Use Minimal resilience expansion because the cache
      // is not per-function.
      if (classDecl->isResilient())
        return AnyPointer;
  
      // For each field in the class, get the pointer kind for that field. For
      // reference-type properties, this will be ReferenceOnly. For aggregates, it
      // will be the meet over all aggregate fields.
      SILType objTy =
        SILType::getPrimitiveObjectType(classTy->getCanonicalType());
      for (VarDecl *property : classDecl->getStoredProperties()) {
        SILType fieldTy =
            objTy.getFieldType(property, M, expansion).getObjectType();
        meetAggregateKind(findCachedPointerKind(fieldTy, F));
      }
    }
    return propertiesKind;
  }
  
  // Returns the kind of pointer that \p Ty recursively contains.
  EscapeAnalysis::PointerKind
  EscapeAnalysis::findCachedPointerKind(SILType Ty, const SILFunction &F) const {
    auto iter = pointerKindCache.find(Ty);
    if (iter != pointerKindCache.end())
      return iter->second;
  
    PointerKind pointerKind = findRecursivePointerKind(Ty, F);
    const_cast<EscapeAnalysis *>(this)->pointerKindCache[Ty] = pointerKind;
    return pointerKind;
  }
  
  EscapeAnalysis::PointerKind
  EscapeAnalysis::findCachedClassPropertiesKind(SILType Ty,
                                                const SILFunction &F) const {
    auto iter = classPropertiesKindCache.find(Ty);
    if (iter != classPropertiesKindCache.end())
      return iter->second;
  
    PointerKind pointerKind = findClassPropertiesPointerKind(Ty, F);
    const_cast<EscapeAnalysis *>(this)
      ->classPropertiesKindCache[Ty] = pointerKind;
    return pointerKind;
  }
  
  // If EscapeAnalysis should consider the given value to be a derived address or
  // pointer based on one of its address or pointer operands, then return that
  // operand value. Otherwise, return an invalid value.
  SILValue EscapeAnalysis::getPointerBase(SILValue value) {
    switch (value->getKind()) {
    case ValueKind::IndexAddrInst:
    case ValueKind::IndexRawPointerInst:
    case ValueKind::StructElementAddrInst:
    case ValueKind::StructExtractInst:
    case ValueKind::TupleElementAddrInst:
    case ValueKind::InitExistentialAddrInst:
    case ValueKind::OpenExistentialAddrInst:
    case ValueKind::BeginAccessInst:
    case ValueKind::UncheckedTakeEnumDataAddrInst:
    case ValueKind::UncheckedEnumDataInst:
    case ValueKind::MarkDependenceInst:
    case ValueKind::PointerToAddressInst:
    case ValueKind::AddressToPointerInst:
    case ValueKind::InitEnumDataAddrInst:
    case ValueKind::UncheckedRefCastInst:
    case ValueKind::ConvertFunctionInst:
    case ValueKind::UpcastInst:
    case ValueKind::InitExistentialRefInst:
    case ValueKind::OpenExistentialRefInst:
    case ValueKind::RawPointerToRefInst:
    case ValueKind::RefToRawPointerInst:
    case ValueKind::RefToBridgeObjectInst:
    case ValueKind::BridgeObjectToRefInst:
    case ValueKind::UnconditionalCheckedCastInst:
      // DO NOT use LOADABLE_REF_STORAGE because unchecked references don't have
      // retain/release instructions that trigger the 'default' case.
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)            \
    case ValueKind::RefTo##Name##Inst:                                           \
    case ValueKind::Name##ToRefInst:
  #include "swift/AST/ReferenceStorage.def"
      return cast<SingleValueInstruction>(value)->getOperand(0);
  
    case ValueKind::UncheckedAddrCastInst: {
      auto *uac = cast<UncheckedAddrCastInst>(value);
      SILValue op = uac->getOperand();
      SILType srcTy = op->getType().getObjectType();
      SILType destTy = value->getType().getObjectType();
      SILFunction *f = uac->getFunction();
      // If the source and destination of the cast don't agree on being a pointer,
      // we bail. Otherwise we would miss important edges in the connection graph:
      // e.g. loads of non-pointers are ignored, while it could be an escape of
      // the value (which could be a pointer before the cast).
      if (findCachedPointerKind(srcTy, *f) != findCachedPointerKind(destTy, *f))
        return SILValue();
      return op;
    }
    case ValueKind::TupleExtractInst: {
      auto *TEI = cast<TupleExtractInst>(value);
      // Special handling for extracting the pointer-result from an
      // array construction. See createArrayUninitializedSubgraph.
      if (canOptimizeArrayUninitializedResult(TEI))
        return SILValue();
      return TEI->getOperand();
    }
    case ValueKind::StructInst:
    case ValueKind::TupleInst:
    case ValueKind::EnumInst: {
      // Allow a single-operand aggregate to share its operand's node.
      auto *SVI = cast<SingleValueInstruction>(value);
      SILValue pointerOperand;
      for (SILValue opV : SVI->getOperandValues()) {
        if (!isPointer(opV))
          continue;
  
        if (pointerOperand)
          return SILValue();
  
        pointerOperand = opV;
      }
      return pointerOperand;
    }
    case ValueKind::MultipleValueInstructionResult: {
      if (auto *dt = dyn_cast<DestructureTupleInst>(value)) {
        if (canOptimizeArrayUninitializedResult(dt))
          return SILValue();
        return dt->getOperand();
      }
      return SILValue();
    }
    default:
      return SILValue();
    }
  }
  
  // Recursively find the given value's pointer base. If the value cannot be
  // represented in EscapeAnalysis as one of its operands, then return the same
  // value.
  SILValue EscapeAnalysis::getPointerRoot(SILValue value) {
    while (true) {
      if (SILValue v2 = getPointerBase(value))
        value = v2;
      else
        break;
    }
    return value;
  }
  
  static bool isNonWritableMemoryAddress(SILValue V) {
    switch (V->getKind()) {
    case ValueKind::FunctionRefInst:
    case ValueKind::DynamicFunctionRefInst:
    case ValueKind::PreviousDynamicFunctionRefInst:
    case ValueKind::WitnessMethodInst:
    case ValueKind::ClassMethodInst:
    case ValueKind::SuperMethodInst:
    case ValueKind::ObjCMethodInst:
    case ValueKind::ObjCSuperMethodInst:
    case ValueKind::StringLiteralInst:
    case ValueKind::ThinToThickFunctionInst:
    case ValueKind::ThinFunctionToPointerInst:
    case ValueKind::PointerToThinFunctionInst:
      // These instructions return pointers to memory which can't be a
      // destination of a store.
      return true;
    default:
      return false;
    }
  }
  
  // Implement an intrusive worklist of CGNode. Only one may be in use at a time.
  struct EscapeAnalysis::CGNodeWorklist {
    llvm::SmallVector<CGNode *, 8> nodeVector;
    EscapeAnalysis::ConnectionGraph *conGraph;
  
    CGNodeWorklist(const CGNodeWorklist &) = delete;
  
    CGNodeWorklist(EscapeAnalysis::ConnectionGraph *conGraph)
        : conGraph(conGraph) {
      conGraph->activeWorklist = this;
    }
    ~CGNodeWorklist() { reset(); }
    // Clear the intrusive isInWorkList flags, but leave the nodeVector vector in
    // place for subsequent iteration.
    void reset() {
      ConnectionGraph::clearWorkListFlags(nodeVector);
      conGraph->activeWorklist = nullptr;
    }
    unsigned size() const { return nodeVector.size(); }
  
    bool empty() const { return nodeVector.empty(); }
  
    bool contains(CGNode *node) const {
      assert(conGraph->activeWorklist == this);
      return node->isInWorkList;
    }
    CGNode *operator[](unsigned idx) const {
      assert(idx < size());
      return nodeVector[idx];
    }
    bool tryPush(CGNode *node) {
      assert(conGraph->activeWorklist == this);
      if (node->isInWorkList)
        return false;
  
      node->isInWorkList = true;
      nodeVector.push_back(node);
      return true;
    }
    void push(CGNode *node) {
      assert(conGraph->activeWorklist == this);
      assert(!node->isInWorkList);
      node->isInWorkList = true;
      nodeVector.push_back(node);
    }
  };
  
  /// Mapping from nodes in a callee-graph to nodes in a caller-graph.
  class EscapeAnalysis::CGNodeMap {
    /// The map itself.
    llvm::DenseMap<CGNode *, CGNode *> Map;
  
    /// The list of source nodes (= keys in Map), which is used as a work-list.
    CGNodeWorklist MappedNodes;
  
  public:
    CGNodeMap(ConnectionGraph *conGraph) : MappedNodes(conGraph) {}
    CGNodeMap(const CGNodeMap &) = delete;
  
    /// Adds a mapping and pushes the \p From node into the work-list
    /// MappedNodes.
    void add(CGNode *From, CGNode *To) {
      assert(From && To && !From->isMerged && !To->isMerged);
      Map[From] = To;
      MappedNodes.tryPush(From);
    }
    /// Looks up a node in the mapping.
    CGNode *get(CGNode *From) const {
      auto Iter = Map.find(From);
      if (Iter == Map.end())
        return nullptr;
  
      return Iter->second->getMergeTarget();
    }
    CGNodeWorklist &getMappedNodes() { return MappedNodes; }
  };
  
  //===----------------------------------------------------------------------===//
  //                        ConnectionGraph Implementation
  //===----------------------------------------------------------------------===//
  
  std::pair<const CGNode *, unsigned> EscapeAnalysis::CGNode::getRepNode(
      SmallPtrSetImpl<const CGNode *> &visited) const {
    if (!isContent() || mappedValue)
      return {this, 0};
  
    for (Predecessor pred : Preds) {
      if (!pred.is(EdgeType::PointsTo))
        continue;
      if (!visited.insert(pred.getPredNode()).second)
        continue;
      auto repNodeAndDepth = pred.getPredNode()->getRepNode(visited);
      if (repNodeAndDepth.first)
        return {repNodeAndDepth.first, repNodeAndDepth.second + 1};
      // If a representative node was not found on this pointsTo node, recursion
      // must have hit a cycle. Try the next pointsTo edge.
    }
    return {nullptr, 0};
  }
  
  EscapeAnalysis::CGNode::RepValue EscapeAnalysis::CGNode::getRepValue() const {
    // We don't use CGNodeWorklist because CGNode::dump() should be callable
    // anywhere, even while another worklist is active, and getRepValue() itself
    // is not on any critical path.
    SmallPtrSet<const CGNode *, 4> visited({this});
    const CGNode *repNode;
    unsigned depth;
    std::tie(repNode, depth) = getRepNode(visited);
    return {{repNode ? SILValue(repNode->mappedValue) : SILValue(),
             repNode && repNode->Type == EscapeAnalysis::NodeType::Return},
            depth};
  }
  
  void EscapeAnalysis::CGNode::mergeFlags(bool isInterior,
                                          bool hasReferenceOnly) {
    // isInterior is conservatively preserved from either node unless two content
    // nodes are being merged and one is the interior node's content.
    isInteriorFlag |= isInterior;
  
    // hasReferenceOnly is always conservatively merged.
    hasReferenceOnlyFlag &= hasReferenceOnly;
  }
  
  void EscapeAnalysis::CGNode::mergeProperties(CGNode *fromNode) {
    // isInterior is conservatively preserved from either node unless the other
    // node is the interior node's content.
    bool isInterior = fromNode->isInteriorFlag;
    if (fromNode == pointsTo)
      this->isInteriorFlag = isInterior;
    else if (this == fromNode->pointsTo)
      isInterior = this->isInteriorFlag;
  
    mergeFlags(isInterior, fromNode->hasReferenceOnlyFlag);
  }
  
  template <typename Visitor>
  bool EscapeAnalysis::CGNode::visitSuccessors(Visitor &&visitor) const {
    if (CGNode *pointsToSucc = getPointsToEdge()) {
      // Visit pointsTo, even if pointsTo == this.
      if (!visitor(pointsToSucc))
        return false;
    }
    for (CGNode *def : defersTo) {
      if (!visitor(def))
        return false;
    }
    return true;
  }
  
  template <typename Visitor>
  bool EscapeAnalysis::CGNode::visitDefers(Visitor &&visitor) const {
    // Save predecessors before calling `visitor` which may assign pointsTo edges
    // which invalidates the predecessor iterator.
    SmallVector<Predecessor, 4> predVector(Preds.begin(), Preds.end());
    for (Predecessor pred : predVector) {
      if (!pred.is(EdgeType::Defer))
        continue;
      if (!visitor(pred.getPredNode(), false))
        return false;
    }
    for (auto *deferred : defersTo) {
      if (!visitor(deferred, true))
        return false;
    }
    return true;
  }
  
  void EscapeAnalysis::ConnectionGraph::clear() {
    Values2Nodes.clear();
    Nodes.clear();
    ReturnNode = nullptr;
    UsePoints.clear();
    UsePointTable.clear();
    NodeAllocator.DestroyAll();
    valid = true;
    assert(ToMerge.empty());
  }
  
  // This never returns an interior node. It should never be called directly on an
  // address projection of a reference. To get the interior node for an address
  // projection, always ask for the content of the projection's base instead using
  // getValueContent() or getReferenceContent().
  //
  // Address phis are not allowed, so merging an unknown address with a reference
  // address projection is rare. If that happens, then the projection's node loses
  // it's interior property.
  EscapeAnalysis::CGNode *
  EscapeAnalysis::ConnectionGraph::getNode(SILValue V) {
    if (!isValid())
      return nullptr;
  
    // Early filter obvious non-pointer opcodes.
    if (isa<FunctionRefInst>(V) || isa<DynamicFunctionRefInst>(V) ||
        isa<PreviousDynamicFunctionRefInst>(V))
      return nullptr;
  
    // Create the node flags based on the derived value's kind. If the pointer
    // base type has non-reference pointers but they are never accessed in the
    // current function, then ignore them.
    PointerKind pointerKind = EA->getPointerKind(V);
    if (pointerKind == EscapeAnalysis::NoPointer)
      return nullptr;
  
    // Look past address projections, pointer casts, and the like within the same
    // object. Does not look past a dereference such as ref_element_addr, or
    // project_box.
    SILValue ptrBase = EA->getPointerRoot(V);
    // Do not create a node for undef values so we can verify that node values
    // have the correct pointer kind.
    if (!ptrBase->getFunction())
      return nullptr;
  
    assert(EA->isPointer(ptrBase) &&
           "The base for derived pointer must also be a pointer type");
  
    bool hasReferenceOnly = canOnlyContainReferences(pointerKind);
    // Update the value-to-node map.
    CGNode *&Node = Values2Nodes[ptrBase];
    if (Node) {
      CGNode *targetNode = Node->getMergeTarget();
      targetNode->mergeFlags(false /*isInterior*/, hasReferenceOnly);
      // Update the node in Values2Nodes, so that next time we don't need to find
      // the final merge target.
      Node = targetNode;
      return targetNode;
    }
    if (isa<SILFunctionArgument>(ptrBase)) {
      Node = allocNode(ptrBase, NodeType::Argument, false, hasReferenceOnly);
      if (!isSummaryGraph)
        Node->mergeEscapeState(EscapeState::Arguments);
    } else
      Node = allocNode(ptrBase, NodeType::Value, false, hasReferenceOnly);
    return Node;
  }
  
  /// Adds an argument/instruction in which the node's memory is released.
  int EscapeAnalysis::ConnectionGraph::addUsePoint(CGNode *Node,
                                                   SILInstruction *User) {
    // Use points are never consulted for escaping nodes, but still need to
    // propagate to other nodes in a defer web. Even if this node is escaping,
    // some defer predecessors may not be escaping. Only checking if this node has
    // defer predecessors is insufficient because a defer successor of this node
    // may have defer predecessors.
    if (Node->getEscapeState() >= EscapeState::Global)
      return -1;
  
    int Idx = (int)UsePoints.size();
    assert(UsePoints.count(User) == 0 && "value is already a use-point");
    UsePoints[User] = Idx;
    UsePointTable.push_back(User);
    assert(UsePoints.size() == UsePointTable.size());
    Node->setUsePointBit(Idx);
    return Idx;
  }
  
  CGNode *EscapeAnalysis::ConnectionGraph::defer(CGNode *From, CGNode *To,
                                                 bool &Changed) {
    if (!From->canAddDeferred(To))
      return From;
  
    CGNode *FromPointsTo = From->pointsTo;
    CGNode *ToPointsTo = To->pointsTo;
    // If necessary, merge nodes while the graph is still in a valid state.
    if (FromPointsTo && ToPointsTo && FromPointsTo != ToPointsTo) {
      // We are adding an edge between two pointers which point to different
      // content nodes. This will require merging the content nodes (and maybe
      // other content nodes as well), because of the graph invariance 4).
      //
      // Once the pointee's are merged, the defer edge can be added without
      // creating an inconsistency.
      scheduleToMerge(FromPointsTo, ToPointsTo);
      mergeAllScheduledNodes();
      Changed = true;
    }
    // 'From' and 'To' may have been merged, so addDeferred may no longer succeed.
    if (From->getMergeTarget()->addDeferred(To->getMergeTarget()))
      Changed = true;
  
    // If pointsTo on either side of the defer was uninitialized, initialize that
    // side of the defer web. Do this after adding the new edge to avoid creating
    // useless pointsTo edges.
    if (!FromPointsTo && ToPointsTo)
      initializePointsTo(From, ToPointsTo);
    else if (FromPointsTo && !ToPointsTo)
      initializePointsTo(To, FromPointsTo);
  
    return From->getMergeTarget();
  }
  
  // Precondition: The pointsTo fields of all nodes in initializeNode's defer web
  // are either uninitialized or already initialized to newPointsTo.
  void EscapeAnalysis::ConnectionGraph::initializePointsTo(CGNode *initialNode,
                                                           CGNode *newPointsTo,
                                                           bool createEdge) {
    // Track nodes that require pointsTo edges.
    llvm::SmallVector<CGNode *, 4> pointsToEdgeNodes;
    if (createEdge)
      pointsToEdgeNodes.push_back(initialNode);
  
    // Step 1: Visit each node that reaches or is reachable via defer edges until
    // reaching a node with the newPointsTo or with a proper pointsTo edge.
  
    // A worklist to gather updated nodes in the defer web.
    CGNodeWorklist updatedNodes(this);
    unsigned updateCount = 0;
  
    auto visitDeferTarget = [&](CGNode *node, bool /*isSuccessor*/) {
      if (updatedNodes.contains(node))
        return true;
  
      if (node->pointsTo) {
        assert(node->pointsTo == newPointsTo);
        // Since this node already had a pointsTo, it must reach a pointsTo
        // edge. Stop traversing the defer-web here--this is complete becaused
        // nodes are initialized one at a time, each time a new defer edge is
        // created. If this were not complete, then the backward traversal below
        // in Step 2 could reach uninitialized nodes not seen here in Step 1.
        pointsToEdgeNodes.push_back(node);
        return true;
      }
      ++updateCount;
      if (node->defersTo.empty()) {
        // If this node is the end of a defer-edge path with no pointsTo
        // edge. Create a "fake" pointsTo edge to maintain the graph invariant
        // (this changes the structure of the graph but adding this edge has no
        // effect on the process of merging nodes or creating new defer edges).
        pointsToEdgeNodes.push_back(node);
      }
      updatedNodes.push(node);
      return true;
    };
    // Seed updatedNodes with initialNode.
    visitDeferTarget(initialNode, true);
    // updatedNodes may grow during this loop.
    for (unsigned idx = 0; idx < updatedNodes.size(); ++idx)
      updatedNodes[idx]->visitDefers(visitDeferTarget);
    // Reset this worklist so others can be used, but updateNode.nodeVector still
    // holds all the nodes found by step 1.
    updatedNodes.reset();
  
    // Step 2: Update pointsTo fields by propagating backward from nodes that
    // already have a pointsTo edge.
    do {
      while (!pointsToEdgeNodes.empty()) {
        CGNode *edgeNode = pointsToEdgeNodes.pop_back_val();
        if (!edgeNode->pointsTo) {
          // This node is either (1) a leaf node in the defer web (identified in
          // step 1) or (2) an arbitrary node in a defer-cycle (identified in a
          // previous iteration of the outer loop).
          edgeNode->setPointsToEdge(newPointsTo);
          newPointsTo->mergeUsePoints(edgeNode);
          assert(updateCount--);
        }
        // If edgeNode is already set to newPointsTo, it either was already
        // up-to-date before calling initializePointsTo, or it was visited during
        // a previous iteration of the backward traversal below. Rather than
        // distinguish these cases, always retry backward traversal--it just won't
        // revisit any edges in the later case.
        backwardTraverse(edgeNode, [&](Predecessor pred) {
          if (!pred.is(EdgeType::Defer))
            return Traversal::Backtrack;
  
          CGNode *predNode = pred.getPredNode();
          if (predNode->pointsTo) {
            assert(predNode->pointsTo->getMergeTarget()
                   == newPointsTo->getMergeTarget());
            return Traversal::Backtrack;
          }
          predNode->pointsTo = newPointsTo;
          newPointsTo->mergeUsePoints(predNode);
          assert(updateCount--);
          return Traversal::Follow;
        });
      }
      // For all nodes visited in step 1, pick a single node that was not
      // backward-reachable from a pointsTo edge, create an edge for it and
      // restart traversal. This only happens when step 1 fails to find leaves in
      // the defer web because of defer edge cycles.
      while (!updatedNodes.empty()) {
        CGNode *node = updatedNodes.nodeVector.pop_back_val();
        if (!node->pointsTo) {
          pointsToEdgeNodes.push_back(node);
          break;
        }
      }
      // This outer loop is exceedingly unlikely to execute more than twice.
    } while (!pointsToEdgeNodes.empty());
    assert(updateCount == 0);
  }
  
  void EscapeAnalysis::ConnectionGraph::mergeAllScheduledNodes() {
    // Each merge step is self contained and verifiable, with one exception. When
    // merging a node that points to itself with a node points to another node,
    // multiple merge steps are necessary to make the defer web consistent.
    // Example:
    //   NodeA pointsTo-> From
    //   From  defersTo-> NodeA (an indirect self-cycle)
    //   To    pointsTo-> NodeB
    // Merged:
    //   NodeA pointsTo-> To
    //   To    defersTo-> NodeA (To *should* pointTo itself)
    //   To    pointsTo-> NodeB (but still has a pointsTo edge to NodeB)
    while (!ToMerge.empty()) {
      if (EnableInternalVerify)
        verifyStructure(true /*allowMerge*/);
  
      CGNode *From = ToMerge.pop_back_val();
      CGNode *To = From->getMergeTarget();
      assert(To != From && "Node scheduled to merge but no merge target set");
      assert(!From->isMerged && "Merge source is already merged");
      assert(From->Type == NodeType::Content && "Can only merge content nodes");
      assert(To->Type == NodeType::Content && "Can only merge content nodes");
  
      // Redirect the incoming pointsTo edge and unlink the defer predecessors.
      //
      // Don't redirect the defer-edges because it may trigger mergePointsTo() or
      // initializePointsTo(). By ensuring that 'From' is unreachable first, the
      // graph appears consistent during those operations.
      for (Predecessor Pred : From->Preds) {
        CGNode *PredNode = Pred.getPredNode();
        if (Pred.is(EdgeType::PointsTo)) {
          assert(PredNode->getPointsToEdge() == From
                 && "Incoming pointsTo edge not set in predecessor");
          if (PredNode != From)
            PredNode->setPointsToEdge(To);
        } else {
          assert(PredNode != From);
          auto Iter = PredNode->findDeferred(From);
          assert(Iter != PredNode->defersTo.end()
                 && "Incoming defer-edge not found in predecessor's defer list");
          PredNode->defersTo.erase(Iter);
        }
      }
      // Unlink the outgoing defer edges.
      for (CGNode *Defers : From->defersTo) {
        assert(Defers != From && "defer edge may not form a self-cycle");
        Defers->removeFromPreds(Predecessor(From, EdgeType::Defer));
      }
      // Handle self-cycles on From by creating a self-cycle at To.
      auto redirectPointsTo = [&](CGNode *pointsTo) {
        return (pointsTo == From) ? To : pointsTo;
      };
      // Redirect the outgoing From -> pointsTo edge.
      if (From->pointsToIsEdge) {
        From->pointsTo->removeFromPreds(Predecessor(From, EdgeType::PointsTo));
        if (To->pointsToIsEdge) {
          // If 'To' had a pointsTo edge to 'From', then it was redirected above.
          // Otherwise FromPT and ToPT will be merged below; nothing to do here.
          assert(To->pointsTo != From);
        } else {
          // If 'To' has no pointsTo at all, initialize its defer web.
          if (!To->pointsTo)
            initializePointsToEdge(To, redirectPointsTo(From->pointsTo));
          else {
            // Upgrade 'To's pointsTo to an edge to preserve the fact that 'From'
            // had a pointsTo edge.
            To->pointsToIsEdge = true;
            To->pointsTo = redirectPointsTo(To->pointsTo);
            To->pointsTo->Preds.push_back(Predecessor(To, EdgeType::PointsTo));
          }
        }
      }
      // Merge 'From->pointsTo' and 'To->pointsTo' if needed, regardless of
      // whether either is a proper edge. Merging may be needed because other
      // nodes may have points-to edges to From->PointsTo that won't be visited
      // when updating 'From's defer web.
      //
      // If To doesn't already have a points-to, it will simply be initialized
      // when updating the merged defer web below.
      if (CGNode *toPT = To->pointsTo) {
        // If 'To' already points to 'From', then it will already point to 'From's
        // pointTo after merging. An additional merge would be too conservative.
        if (From->pointsTo && toPT != From)
          scheduleToMerge(redirectPointsTo(From->pointsTo), toPT);
      }
      // Redirect adjacent defer edges, and immediately update all points-to
      // fields in the defer web.
      //
      // Calling initializePointsTo may create new pointsTo edges from nodes in
      // the defer-web. It is unsafe to mutate or query the graph in its currently
      // inconsistent state. However, this particular case is safe because:
      // - The graph is only locally inconsistent w.r.t. nodes still connected to
      // 'From' via defer edges.
      // - 'From' itself is no longer reachable via graph edges (it may only be
      // referenced in points-to fields which haven't all been updated).
      // - Calling initializePointsTo on one from 'From's deferred nodes implies
      // that all nodes in 'From's defer web had a null pointsTo.
      // - 'To's defer web remains consistent each time a new defer edge is
      // added below. Any of 'To's existing deferred nodes either still need to
      // be initialized or have already been initialized to the same pointsTo.
      //
      // Start by updating 'To's own pointsTo field.
      if (To->pointsTo == From)
        mergePointsTo(To, To);
  
      auto mergeDeferPointsTo = [&](CGNode *deferred, bool isSuccessor) {
        assert(From != deferred && "defer edge may not form a self-cycle");
        if (To == deferred)
          return true;
  
        // In case 'deferred' points to 'From', update its pointsTo before
        // exposing it to 'To's defer web.
        if (deferred->pointsTo == From)
          mergePointsTo(deferred, To);
  
        if (isSuccessor)
          To->addDeferred(deferred);
        else
          deferred->addDeferred(To);
  
        if (deferred->pointsTo && To->pointsTo)
          mergePointsTo(deferred, To->pointsTo);
        else if (deferred->pointsTo)
          initializePointsTo(To, deferred->pointsTo);
        else if (To->pointsTo)
          initializePointsTo(deferred, To->pointsTo);
  
        return true;
      };
      // Redirect the adjacent defer edges.
      From->visitDefers(mergeDeferPointsTo);
  
      // Update the web of nodes that originally pointed to 'From' via 'From's old
      // pointsTo predecessors (which are now attached to 'To').
      for (unsigned PredIdx = 0; PredIdx < To->Preds.size(); ++PredIdx) {
        auto predEdge = To->Preds[PredIdx];
        if (!predEdge.is(EdgeType::PointsTo))
          continue;
        predEdge.getPredNode()->visitDefers(
            [&](CGNode *deferred, bool /*isSucc*/) {
              mergePointsTo(deferred, To);
              return true;
            });
      }
      To->mergeEscapeState(From->State);
  
      // Cleanup the merged node.
      From->isMerged = true;
  
      if (From->mappedValue) {
        // values previously mapped to 'From' but not transferred to 'To's
        // mappedValue must remain mapped to 'From'. Lookups on those values will
        // find 'To' via the mergeTarget and will remap those values to 'To'
        // on-the-fly for efficiency. Dropping a value's mapping is illegal
        // because it could cause a node to be recreated without the edges that
        // have already been discovered.
        if (!To->mappedValue) {
          To->mappedValue = From->mappedValue;
          Values2Nodes[To->mappedValue] = To;
        }
        From->mappedValue = nullptr;
      }
      From->Preds.clear();
      From->defersTo.clear();
      From->pointsTo = nullptr;
    }
    if (EnableInternalVerify)
      verifyStructure(true /*allowMerge*/);
  }
  
  // As a result of a merge, update the pointsTo field of initialNode and
  // everything in its defer web to newPointsTo.
  //
  // This may modify the graph by redirecting a pointsTo edges.
  void EscapeAnalysis::ConnectionGraph::mergePointsTo(CGNode *initialNode,
                                                      CGNode *newPointsTo) {
    CGNode *oldPointsTo = initialNode->pointsTo;
    assert(oldPointsTo && "merging content should not initialize any pointsTo");
  
    // newPointsTo may already be scheduled for a merge. Only create new edges to
    // unmerged nodes. This may create a temporary pointsTo mismatch in the defer
    // web, but Graph verification takes merged nodes into consideration.
    newPointsTo = newPointsTo->getMergeTarget();
    if (oldPointsTo == newPointsTo)
      return;
  
    CGNodeWorklist updateNodes(this);
    auto updatePointsTo = [&](CGNode *node) {
      if (node->pointsTo == newPointsTo)
        return;
      // If the original graph was: 'node->From->To->newPointsTo' or
      // 'node->From->From', then node is already be updated to point to
      // 'To' and 'To' must be merged with newPointsTo. We must still update
      // pointsTo so that all nodes in the defer web have the same pointsTo.
      assert(node->pointsTo == oldPointsTo
             || node->pointsTo->getMergeTarget() == newPointsTo);
      if (node->pointsToIsEdge) {
        node->pointsTo->removeFromPreds(Predecessor(node, EdgeType::PointsTo));
        node->setPointsToEdge(newPointsTo);
      } else
        node->pointsTo = newPointsTo;
      updateNodes.push(node);
    };
    updatePointsTo(initialNode);
  
    // Visit each node that reaches or is reachable via defer edges until reaching
    // a node with the newPointsTo.
    auto visitDeferTarget = [&](CGNode *node, bool /*isSuccessor*/) {
      if (!updateNodes.contains(node))
        updatePointsTo(node);
      return true;
    };
    for (unsigned Idx = 0; Idx < updateNodes.size(); ++Idx)
      updateNodes[Idx]->visitDefers(visitDeferTarget);
  }
  
  void EscapeAnalysis::ConnectionGraph::propagateEscapeStates() {
    bool Changed = false;
    do {
      Changed = false;
  
      for (CGNode *Node : Nodes) {
        // Propagate the state to all pointsTo nodes. It would be sufficient to
        // only follow proper pointsTo edges, since this loop also follows defer
        // edges, but this may converge faster.
        if (Node->pointsTo) {
          Changed |= Node->pointsTo->mergeEscapeState(Node->State);
        }
        // Note: Propagating along defer edges may be interesting from an SSA
        // standpoint, but it is entirely irrelevant alias analysis.
        for (CGNode *Def : Node->defersTo) {
          Changed |= Def->mergeEscapeState(Node->State);
        }
      }
    } while (Changed);
  }
  
  void EscapeAnalysis::ConnectionGraph::computeUsePoints() {
  #ifndef NDEBUG
    for (CGNode *Nd : Nodes)
      assert(Nd->UsePoints.empty() && "premature use point computation");
  #endif
    // First scan the whole function and add relevant instructions as use-points.
    for (auto &BB : *F) {
      for (auto &I : BB) {
        switch (I.getKind()) {
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
          case SILInstructionKind::Name##ReleaseInst:
  #include "swift/AST/ReferenceStorage.def"
          case SILInstructionKind::StrongReleaseInst:
          case SILInstructionKind::ReleaseValueInst:
          case SILInstructionKind::DestroyValueInst:
          case SILInstructionKind::ApplyInst:
          case SILInstructionKind::TryApplyInst: {
            /// Actually we only add instructions which may release a reference.
            /// We need the use points only for getting the end of a reference's
            /// liferange. And that must be a releasing instruction.
            int ValueIdx = -1;
            for (const Operand &Op : I.getAllOperands()) {
              CGNode *content = getValueContent(Op.get());
              if (!content)
                continue;
              if (ValueIdx < 0)
                ValueIdx = addUsePoint(content, &I);
              else
                content->setUsePointBit(ValueIdx);
            }
            break;
          }
          default:
            break;
        }
      }
    }
  
    // Second, we propagate the use-point information through the graph.
    bool Changed = false;
    do {
      Changed = false;
      for (CGNode *Node : Nodes) {
        // Propagate the bits to pointsTo. A release of a node may also release
        // any content pointed to be the node.
        if (Node->pointsTo)
          Changed |= Node->pointsTo->mergeUsePoints(Node);
      }
    } while (Changed);
  }
  
  CGNode *EscapeAnalysis::ConnectionGraph::createContentNode(
      CGNode *addrNode, bool isInterior, bool hasReferenceOnly) {
    CGNode *newContent =
        allocNode(nullptr, NodeType::Content, isInterior, hasReferenceOnly);
    initializePointsToEdge(addrNode, newContent);
    return newContent;
  }
  
  CGNode *EscapeAnalysis::ConnectionGraph::getOrCreateContentNode(
      CGNode *addrNode, bool isInterior, bool hasReferenceOnly) {
    if (CGNode *content = addrNode->getContentNodeOrNull()) {
      content->mergeFlags(isInterior, hasReferenceOnly);
      return content;
    }
    CGNode *content = createContentNode(addrNode, isInterior, hasReferenceOnly);
    // getValueContent may be called after the graph is built and escape states
    // are propagated. Keep the escape state and use points consistent here.
    content->mergeEscapeState(addrNode->State);
    content->mergeUsePoints(addrNode);
    return content;
  }
  
  // Create a content node for merging based on an address node in the destination
  // graph and a content node in the source graph.
  CGNode *
  EscapeAnalysis::ConnectionGraph::createMergedContent(CGNode *destAddrNode,
                                                       CGNode *srcContent) {
    // destAddrNode may itself be a content node, so its value may be null. Since
    // we don't have the original pointer value, build a new content node based
    // on the source content.
    CGNode *mergedContent = createContentNode(
        destAddrNode, srcContent->isInterior(), srcContent->hasReferenceOnly());
    return mergedContent;
  }
  
  CGNode *
  EscapeAnalysis::ConnectionGraph::getOrCreateAddressContent(SILValue addrVal,
                                                             CGNode *addrNode) {
    assert(addrVal->getType().isAddress());
  
    bool contentHasReferenceOnly =
        EA->hasReferenceOnly(addrVal->getType().getObjectType(), *F);
    // Address content is never an interior node (only reference content can
    // be an interior node).
    return getOrCreateContentNode(addrNode, false, contentHasReferenceOnly);
  }
  
  // refVal is allowed to be invalid so we can model escaping content for
  // secondary deinitializers of released objects.
  CGNode *
  EscapeAnalysis::ConnectionGraph::getOrCreateReferenceContent(SILValue refVal,
                                                               CGNode *refNode) {
    // The object node created here points to internal fields. It neither has
    // indirect pointsTo nor reference-only pointsTo.
    CGNode *objNode = getOrCreateContentNode(refNode, true, false);
    if (!objNode->isInterior())
      return objNode;
  
    // Determine whether the object that refVal refers to only contains
    // references.
    bool contentHasReferenceOnly = false;
    if (refVal) {
      SILType refType = refVal->getType();
      if (auto *C = refType.getClassOrBoundGenericClass()) {
        PointerKind aggregateKind = NoPointer;
        for (auto *field : C->getStoredProperties()) {
          SILType fieldType = refType
                                  .getFieldType(field, F->getModule(),
                                                F->getTypeExpansionContext())
                                  .getObjectType();
          PointerKind fieldKind = EA->findCachedPointerKind(fieldType, *F);
          if (fieldKind > aggregateKind)
            aggregateKind = fieldKind;
        }
        contentHasReferenceOnly = canOnlyContainReferences(aggregateKind);
      }
    }
    getOrCreateContentNode(objNode, false, contentHasReferenceOnly);
    return objNode;
  }
  
  CGNode *
  EscapeAnalysis::ConnectionGraph::getOrCreateUnknownContent(CGNode *addrNode) {
    // We don't know if addrVal has been cast from a reference or raw
    // pointer. More importantly, we don't know what memory contents it may
    // point to. There's no need to consider it an "interior" node initially. If
    // it's ever merged with another interior node (from ref_element_addr), then
    // it will conservatively take on the interior flag at that time.
    return getOrCreateContentNode(addrNode, false, false);
  }
  
  // If ptrVal is itself mapped to a node, then this must return a non-null
  // contentnode. Otherwise, setEscapesGlobal won't be able to represent escaping
  // memory.
  //
  // This may be called after the graph is built and all escape states and use
  // points are propagate. If a new content node is created, update its state
  // on-the-fly.
  EscapeAnalysis::CGNode *
  EscapeAnalysis::ConnectionGraph::getValueContent(SILValue ptrVal) {
    CGNode *addrNode = getNode(ptrVal);
    if (!addrNode)
      return nullptr;
  
    // Create content based on the derived pointer. If the base pointer contains
    // other types of references, then the content node will be merged when those
    // references are accessed. If the other references types are never accessed
    // in this function, then they are ignored.
    if (ptrVal->getType().isAddress())
      return getOrCreateAddressContent(ptrVal, addrNode);
  
    if (addrNode->hasReferenceOnly())
      return getOrCreateReferenceContent(ptrVal, addrNode);
  
    // The pointer value may contain raw pointers.
    return getOrCreateUnknownContent(addrNode);
  }
  
  CGNode *EscapeAnalysis::ConnectionGraph::getReturnNode() {
    if (!ReturnNode) {
      SILType resultTy = F->mapTypeIntoContext(
          F->getConventions().getSILResultType(F->getTypeExpansionContext()));
      bool hasReferenceOnly = EA->hasReferenceOnly(resultTy, *F);
      ReturnNode = allocNode(nullptr, NodeType::Return, false, hasReferenceOnly);
    }
    return ReturnNode;
  }
  
  bool EscapeAnalysis::ConnectionGraph::mergeFrom(ConnectionGraph *SourceGraph,
                                                  CGNodeMap &Mapping) {
    assert(isValid());
    assert(SourceGraph->isValid());
  
    // The main point of the merging algorithm is to map each content node in the
    // source graph to a content node in this (destination) graph. This may
    // require creating new nodes or merging existing nodes in this graph.
  
    // First step: replicate the points-to edges and the content nodes of the
    // source graph in this graph.
    bool Changed = false;
    for (unsigned Idx = 0; Idx < Mapping.getMappedNodes().size(); ++Idx) {
      CGNode *SourceNd = Mapping.getMappedNodes()[Idx];
      CGNode *DestNd = Mapping.get(SourceNd);
      assert(DestNd);
  
      if (SourceNd->getEscapeState() >= EscapeState::Global) {
        // We don't need to merge the source subgraph of nodes which have the
        // global escaping state set.
        // Just set global escaping in the caller node and that's it.
        Changed |= DestNd->mergeEscapeState(EscapeState::Global);
        // If DestNd is an interior node, its content still needs to be created.
        if (!DestNd->isInterior() || DestNd->pointsTo)
          continue;
      }
  
      CGNode *SourcePT = SourceNd->pointsTo;
      if (!SourcePT)
        continue;
  
      CGNode *MappedDestPT = Mapping.get(SourcePT);
      CGNode *DestPT = DestNd->pointsTo;
      if (!MappedDestPT) {
        if (!DestPT) {
          DestPT = createMergedContent(DestNd, SourcePT);
          Changed = true;
        }
        // This is the first time the dest node is seen; just add the mapping.
        Mapping.add(SourcePT, DestPT);
        continue;
      }
      if (DestPT == MappedDestPT)
        continue;
  
      // We already found the destination node through another path.
      assert(Mapping.getMappedNodes().contains(SourcePT));
      Changed = true;
      if (!DestPT) {
        initializePointsToEdge(DestNd, MappedDestPT);
        continue;
      }
      // There are two content nodes in this graph which map to the same
      // content node in the source graph -> we have to merge them.
      // Defer merging the nodes until all mapped nodes are created so that the
      // graph is structurally valid before merging.
      scheduleToMerge(DestPT, MappedDestPT);
    }
    mergeAllScheduledNodes();
    Mapping.getMappedNodes().reset(); // Make way for a different worklist.
  
    // Second step: add the source graph's defer edges to this graph.
    for (CGNode *SourceNd : Mapping.getMappedNodes().nodeVector) {
      CGNodeWorklist Worklist(SourceGraph);
      Worklist.push(SourceNd);
      CGNode *DestFrom = Mapping.get(SourceNd);
      assert(DestFrom && "node should have been merged to the graph");
  
      // Collect all nodes which are reachable from the SourceNd via a path
      // which only contains defer-edges.
      for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
        CGNode *SourceReachable = Worklist[Idx];
        CGNode *DestReachable = Mapping.get(SourceReachable);
        // Create the edge in this graph. Note: this may trigger merging of
        // content nodes.
        if (DestReachable) {
          DestFrom = defer(DestFrom, DestReachable, Changed);
        } else if (SourceReachable->getEscapeState() >= EscapeState::Global) {
          // If we don't have a mapped node in the destination graph we still have
          // to honor its escaping state. We do that simply by setting the source
          // node of the defer-edge to escaping.
          Changed |= DestFrom->mergeEscapeState(EscapeState::Global);
        }
        for (auto *Deferred : SourceReachable->defersTo)
          Worklist.tryPush(Deferred);
      }
    }
    return Changed;
  }
  
  /// Returns true if \p V is a use of \p Node, i.e. V may (indirectly)
  /// somehow refer to the Node's value.
  /// Use-points are only values which are relevant for lifeness computation,
  /// e.g. release or apply instructions.
  bool EscapeAnalysis::ConnectionGraph::isUsePoint(SILInstruction *UsePoint,
                                                   CGNode *Node) {
    assert(Node->getEscapeState() < EscapeState::Global &&
           "Use points are only valid for non-escaping nodes");
    auto Iter = UsePoints.find(UsePoint);
    if (Iter == UsePoints.end())
      return false;
    int Idx = Iter->second;
    if (Idx >= (int)Node->UsePoints.size())
      return false;
    return Node->UsePoints.test(Idx);
  }
  
  void EscapeAnalysis::ConnectionGraph::getUsePoints(
      CGNode *Node, llvm::SmallVectorImpl<SILInstruction *> &UsePoints) {
    assert(Node->getEscapeState() < EscapeState::Global &&
           "Use points are only valid for non-escaping nodes");
    for (int Idx = Node->UsePoints.find_first(); Idx >= 0;
         Idx = Node->UsePoints.find_next(Idx)) {
      UsePoints.push_back(UsePointTable[Idx]);
    }
  }
  
  // Traverse backward from startNode and return true if \p visitor did not halt
  // traversal..
  //
  // The graph may have cycles.
  template <typename CGPredVisitor>
  bool EscapeAnalysis::ConnectionGraph::backwardTraverse(
      CGNode *startNode, CGPredVisitor &&visitor) {
    CGNodeWorklist worklist(this);
    worklist.push(startNode);
  
    for (unsigned idx = 0; idx < worklist.size(); ++idx) {
      CGNode *reachingNode = worklist[idx];
  
      for (Predecessor pred : reachingNode->Preds) {
        switch (visitor(pred)) {
        case Traversal::Follow: {
          CGNode *predNode = pred.getPredNode();
          worklist.tryPush(predNode);
          break;
        }
        case Traversal::Backtrack:
          break;
        case Traversal::Halt:
          return false;
        }
      }
    }
    return true;
  }
  
  // Traverse forward from startNode, following defer edges and return true if \p
  // visitor did not halt traversal.
  //
  // The graph may have cycles.
  template <typename CGNodeVisitor>
  bool EscapeAnalysis::ConnectionGraph::forwardTraverseDefer(
      CGNode *startNode, CGNodeVisitor &&visitor) {
    CGNodeWorklist worklist(this);
    worklist.push(startNode);
  
    for (unsigned idx = 0; idx < worklist.size(); ++idx) {
      CGNode *reachableNode = worklist[idx];
  
      for (CGNode *deferNode : reachableNode->defersTo) {
        switch (visitor(deferNode)) {
        case Traversal::Follow:
          worklist.tryPush(deferNode);
          break;
        case Traversal::Backtrack:
          break;
        case Traversal::Halt:
          return false;
        }
      }
    }
    return true;
  }
  
  //===----------------------------------------------------------------------===//
  //                      Dumping, Viewing and Verification
  //===----------------------------------------------------------------------===//
  
  #ifndef NDEBUG
  
  /// For the llvm's GraphWriter we copy the connection graph into CGForDotView.
  /// This makes iterating over the edges easier.
  struct CGForDotView {
  
    enum EdgeTypes { PointsTo, Reference, Deferred };
  
    struct Node {
      EscapeAnalysis::CGNode *OrigNode;
      CGForDotView *Graph;
      SmallVector<Node *, 8> Children;
      SmallVector<EdgeTypes, 8> ChildrenTypes;
    };
  
    CGForDotView(const EscapeAnalysis::ConnectionGraph *CG);
    
    std::string getNodeLabel(const Node *Node) const;
    
    std::string getNodeAttributes(const Node *Node) const;
  
    std::vector<Node> Nodes;
  
    SILFunction *F;
  
    const EscapeAnalysis::ConnectionGraph *OrigGraph;
  
    // The same IDs as the SILPrinter uses.
    llvm::DenseMap<const SILNode *, unsigned> InstToIDMap;
  
    typedef std::vector<Node>::iterator iterator;
    typedef SmallVectorImpl<Node *>::iterator child_iterator;
  };
  
  CGForDotView::CGForDotView(const EscapeAnalysis::ConnectionGraph *CG) :
      F(CG->F), OrigGraph(CG) {
    Nodes.resize(CG->Nodes.size());
    llvm::DenseMap<EscapeAnalysis::CGNode *, Node *> Orig2Node;
    int idx = 0;
    for (auto *OrigNode : CG->Nodes) {
      if (OrigNode->isMerged)
        continue;
  
      Orig2Node[OrigNode] = &Nodes[idx++];
    }
    Nodes.resize(idx);
    CG->F->numberValues(InstToIDMap);
  
    idx = 0;
    for (auto *OrigNode : CG->Nodes) {
      if (OrigNode->isMerged)
        continue;
  
      auto &Nd = Nodes[idx++];
      Nd.Graph = this;
      Nd.OrigNode = OrigNode;
      if (auto *PT = OrigNode->getPointsToEdge()) {
        Nd.Children.push_back(Orig2Node[PT]);
        if (OrigNode->hasReferenceOnly())
          Nd.ChildrenTypes.push_back(Reference);
        else
          Nd.ChildrenTypes.push_back(PointsTo);
      }
      for (auto *Def : OrigNode->defersTo) {
        Nd.Children.push_back(Orig2Node[Def]);
        Nd.ChildrenTypes.push_back(Deferred);
      }
    }
  }
  
  void CGNode::RepValue::print(
      llvm::raw_ostream &stream,
      const llvm::DenseMap<const SILNode *, unsigned> &instToIDMap) const {
    if (auto v = getValue())
      stream << '%' << instToIDMap.lookup(v);
    else
      stream << (isReturn() ? "return" : "deleted");
    if (depth > 0)
      stream << '.' << depth;
  }
  
  std::string CGForDotView::getNodeLabel(const Node *Node) const {
    std::string Label;
    llvm::raw_string_ostream O(Label);
    Node->OrigNode->getRepValue().print(O, InstToIDMap);
    O << '\n';
    if (Node->OrigNode->mappedValue) {
      std::string Inst;
      llvm::raw_string_ostream OI(Inst);
      SILValue(Node->OrigNode->mappedValue)->print(OI);
      size_t start = Inst.find(" = ");
      if (start != std::string::npos) {
        start += 3;
      } else {
        start = 2;
      }
      O << Inst.substr(start, 20);
      O << '\n';
    }
    if (!Node->OrigNode->matchPointToOfDefers()) {
      O << "\nPT mismatch: ";
      if (Node->OrigNode->pointsTo)
        Node->OrigNode->pointsTo->getRepValue().print(O, InstToIDMap);
      else
        O << "null";
    }
    O.flush();
    return Label;
  }
  
  std::string CGForDotView::getNodeAttributes(const Node *Node) const {
    auto *Orig = Node->OrigNode;
    std::string attr;
    switch (Orig->Type) {
    case EscapeAnalysis::NodeType::Content:
      attr = "style=\"rounded";
      if (Orig->isInterior()) {
        attr += ",filled";
      }
      attr += "\"";
      break;
    case EscapeAnalysis::NodeType::Argument:
    case EscapeAnalysis::NodeType::Return:
      attr = "style=\"bold\"";
      break;
    default:
      break;
    }
    if (Orig->getEscapeState() != EscapeAnalysis::EscapeState::None
        && !attr.empty())
      attr += ',';
    
    switch (Orig->getEscapeState()) {
    case EscapeAnalysis::EscapeState::None:
      break;
    case EscapeAnalysis::EscapeState::Return:
      attr += "color=\"green\"";
      break;
    case EscapeAnalysis::EscapeState::Arguments:
      attr += "color=\"blue\"";
      break;
    case EscapeAnalysis::EscapeState::Global:
      attr += "color=\"red\"";
      break;
    }
    return attr;
  }
  
  namespace llvm {
  
  
    /// GraphTraits specialization so the CGForDotView can be
    /// iterable by generic graph iterators.
    template <> struct GraphTraits<CGForDotView::Node *> {
      typedef CGForDotView::child_iterator ChildIteratorType;
      typedef CGForDotView::Node *NodeRef;
  
      static NodeRef getEntryNode(NodeRef N) { return N; }
      static inline ChildIteratorType child_begin(NodeRef N) {
        return N->Children.begin();
      }
      static inline ChildIteratorType child_end(NodeRef N) {
        return N->Children.end();
      }
    };
  
    template <> struct GraphTraits<CGForDotView *>
    : public GraphTraits<CGForDotView::Node *> {
      typedef CGForDotView *GraphType;
      typedef CGForDotView::Node *NodeRef;
  
      static NodeRef getEntryNode(GraphType F) { return nullptr; }
  
      typedef pointer_iterator<CGForDotView::iterator> nodes_iterator;
      static nodes_iterator nodes_begin(GraphType OCG) {
        return nodes_iterator(OCG->Nodes.begin());
      }
      static nodes_iterator nodes_end(GraphType OCG) {
        return nodes_iterator(OCG->Nodes.end());
      }
      static unsigned size(GraphType CG) { return CG->Nodes.size(); }
    };
  
    /// This is everything the llvm::GraphWriter needs to write the call graph in
    /// a dot file.
    template <>
    struct DOTGraphTraits<CGForDotView *> : public DefaultDOTGraphTraits {
  
      DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
  
      static std::string getGraphName(const CGForDotView *Graph) {
        return "CG for " + Graph->F->getName().str();
      }
  
      std::string getNodeLabel(const CGForDotView::Node *Node,
                               const CGForDotView *Graph) {
        return Graph->getNodeLabel(Node);
      }
  
      static std::string getNodeAttributes(const CGForDotView::Node *Node,
                                           const CGForDotView *Graph) {
        return Graph->getNodeAttributes(Node);
      }
  
      static std::string getEdgeAttributes(const CGForDotView::Node *Node,
                                           CGForDotView::child_iterator I,
                                           const CGForDotView *Graph) {
        unsigned ChildIdx = I - Node->Children.begin();
        switch (Node->ChildrenTypes[ChildIdx]) {
        case CGForDotView::PointsTo:
          return "";
        case CGForDotView::Reference:
          return "color=\"green\"";
        case CGForDotView::Deferred:
          return "color=\"gray\"";
        }
  
        llvm_unreachable("Unhandled CGForDotView in switch.");
      }
    };
  } // namespace llvm
  
  #endif
  
  void EscapeAnalysis::ConnectionGraph::viewCG() const {
    /// When asserts are disabled, this should be a NoOp.
  #ifndef NDEBUG
    CGForDotView CGDot(this);
    llvm::ViewGraph(&CGDot, "connection-graph");
  #endif
  }
  
  void EscapeAnalysis::ConnectionGraph::dumpCG() const {
    /// When asserts are disabled, this should be a NoOp.
  #ifndef NDEBUG
    CGForDotView CGDot(this);
    llvm::WriteGraph(&CGDot, "connection-graph");
  #endif
  }
  
  void EscapeAnalysis::CGNode::dump() const {
    llvm::errs() << getTypeStr();
    if (isInterior())
      llvm::errs() << " [int]";
    if (hasReferenceOnly())
      llvm::errs() << " [ref]";
  
    auto rep = getRepValue();
    if (rep.depth > 0)
      llvm::errs() << " ." << rep.depth;
    llvm::errs() << ": ";
    if (auto v = rep.getValue())
      llvm::errs() << ": " << v;
    else
      llvm::errs() << (rep.isReturn() ? "return" : "deleted") << '\n';
  
    if (mergeTo) {
      llvm::errs() << "   -> merged to ";
      mergeTo->dump();
    }
  }
  
  const char *EscapeAnalysis::CGNode::getTypeStr() const {
    switch (Type) {
      case NodeType::Value:      return "Val";
      case NodeType::Content:    return "Con";
      case NodeType::Argument:   return "Arg";
      case NodeType::Return:     return "Ret";
    }
  
    llvm_unreachable("Unhandled NodeType in switch.");
  }
  
  void EscapeAnalysis::ConnectionGraph::dump() const {
    print(llvm::errs());
  }
  
  void EscapeAnalysis::ConnectionGraph::print(llvm::raw_ostream &OS) const {
  #ifndef NDEBUG
    OS << "CG of " << F->getName() << '\n';
  
    if (!isValid()) {
      OS << "  invalid\n";
      return;
    }
  
    // Assign the same IDs to SILValues as the SILPrinter does.
    llvm::DenseMap<const SILNode *, unsigned> InstToIDMap;
    InstToIDMap[nullptr] = (unsigned)-1;
    F->numberValues(InstToIDMap);
  
    // Sort by SILValue ID+depth. To make the output somehow consistent with
    // the output of the function's SIL.
    auto sortNodes = [&](llvm::SmallVectorImpl<CGNode *> &Nodes) {
      std::sort(Nodes.begin(), Nodes.end(),
                [&](CGNode *Nd1, CGNode *Nd2) -> bool {
                  auto rep1 = Nd1->getRepValue();
                  auto rep2 = Nd2->getRepValue();
                  unsigned VIdx1 = -1;
                  if (auto v = rep1.getValue())
                    VIdx1 = InstToIDMap[v];
                  unsigned VIdx2 = -1;
                  if (auto v = rep2.getValue())
                    VIdx2 = InstToIDMap[v];
                  if (VIdx1 != VIdx2)
                    return VIdx1 < VIdx2;
                  return rep1.depth < rep2.depth;
                });
    };
  
    llvm::SmallVector<CGNode *, 8> SortedNodes;
    for (CGNode *Nd : Nodes) {
      if (!Nd->isMerged)
        SortedNodes.push_back(Nd);
    }
    sortNodes(SortedNodes);
  
    for (CGNode *Nd : SortedNodes) {
      OS << "  " << Nd->getTypeStr() << ' ';
      if (Nd->isInterior())
        OS << "[int] ";
      if (Nd->hasReferenceOnly())
        OS << "[ref] ";
      Nd->getRepValue().print(OS, InstToIDMap);
      OS << " Esc: ";
      switch (Nd->getEscapeState()) {
        case EscapeState::None: {
          const char *Separator = "";
          for (unsigned VIdx = Nd->UsePoints.find_first(); VIdx != -1u;
               VIdx = Nd->UsePoints.find_next(VIdx)) {
            SILInstruction *inst = UsePointTable[VIdx];
            OS << Separator << '%' << InstToIDMap[inst->asSILNode()];
            Separator = ",";
          }
          break;
        }
        case EscapeState::Return:
          OS << 'R';
          break;
        case EscapeState::Arguments:
          OS << 'A';
          break;
        case EscapeState::Global:
          OS << 'G';
          break;
      }
      OS << ", Succ: ";
      const char *Separator = "";
      if (CGNode *PT = Nd->getPointsToEdge()) {
        OS << '(';
        PT->getRepValue().print(OS, InstToIDMap);
        OS << ')';
        Separator = ", ";
      }
      llvm::SmallVector<CGNode *, 8> SortedDefers = Nd->defersTo;
      sortNodes(SortedDefers);
      for (CGNode *Def : SortedDefers) {
        OS << Separator;
        Def->getRepValue().print(OS, InstToIDMap);
        Separator = ", ";
      }
      OS << '\n';
    }
    OS << "End\n";
  #endif
  }
  
  /// Checks an invariant of the connection graph: The points-to nodes of
  /// the defer-successors must match with the points-to of this node.
  bool CGNode::matchPointToOfDefers(bool allowMerge) const {
    auto redirect = [allowMerge](CGNode *node) {
      return (allowMerge && node) ? node->getMergeTarget() : node;
    };
    for (CGNode *Def : defersTo) {
      if (redirect(pointsTo) != redirect(Def->pointsTo))
        return false;
    }
    /// A defer-path in the graph must not end without the specified points-to
    /// node.
    if (pointsTo && !pointsToIsEdge && defersTo.empty())
      return false;
    return true;
  }
  
  void EscapeAnalysis::ConnectionGraph::verify() const {
  #ifndef NDEBUG
    // Invalidating EscapeAnalysis clears the connection graph.
    if (isEmpty())
      return;
    assert(isValid());
  
    verifyStructure();
  
    // Verify that all pointer nodes are still mapped, otherwise the process of
    // merging nodes may have lost information. Only visit reachable blocks,
    // because the graph builder only mapped values from reachable blocks.
    ReachableBlocks reachable(F);
    reachable.visit([this](SILBasicBlock *bb) {
      for (auto &i : *bb) {
        if (auto *svi = dyn_cast<SingleValueInstruction>(&i)) {
          if (isNonWritableMemoryAddress(svi))
            continue;
        }
  
        if (auto ai = dyn_cast<ApplyInst>(&i)) {
          if (EA->canOptimizeArrayUninitializedCall(ai).isValid())
            continue;
          // Ignore checking CGNode mapping for result of apply to a no return
          // function that will have a null ReturnNode
          if (auto *callee = ai->getReferencedFunctionOrNull()) {
            if (EA->getFunctionInfo(callee)->isValid())
              if (!EA->getConnectionGraph(callee)->getReturnNodeOrNull())
                continue;
          }
        }
        for (auto result : i.getResults()) {
          if (EA->getPointerBase(result))
            continue;
  
          if (!EA->isPointer(result))
            continue;
  
          if (!Values2Nodes.lookup(result)) {
            llvm::dbgs() << "No CG mapping for ";
            result->dumpInContext();
            llvm::dbgs() << " in:\n";
            F->dump();
            llvm_unreachable("Missing escape connection graph mapping");
          }
        }
      }
      return true;
    });
  #endif
  }
  
  void EscapeAnalysis::ConnectionGraph::verifyStructure(bool allowMerge) const {
  #ifndef NDEBUG
    for (CGNode *Nd : Nodes) {
      // Verify the graph structure...
      if (Nd->isMerged) {
        assert(Nd->mergeTo);
        assert(!Nd->pointsTo);
        assert(Nd->defersTo.empty());
        assert(Nd->Preds.empty());
        assert(Nd->Type == NodeType::Content);
        continue;
      }
      // Check if predecessor and successor edges are linked correctly.
      for (Predecessor Pred : Nd->Preds) {
        CGNode *PredNode = Pred.getPredNode();
        if (Pred.is(EdgeType::Defer)) {
          assert(PredNode->findDeferred(Nd) != PredNode->defersTo.end());
        } else {
          assert(Pred.is(EdgeType::PointsTo));
          assert(PredNode->getPointsToEdge() == Nd);
        }
      }
      for (CGNode *Def : Nd->defersTo) {
        assert(Def->findPred(Predecessor(Nd, EdgeType::Defer)) != Def->Preds.end());
        assert(Def != Nd);
      }
      if (CGNode *PT = Nd->getPointsToEdge()) {
        assert(PT->Type == NodeType::Content);
        assert(PT->findPred(Predecessor(Nd, EdgeType::PointsTo)) != PT->Preds.end());
      }
      if (Nd->isInterior())
        assert(Nd->pointsTo && "Interior content node requires a pointsTo node");
  
      // ConnectionGraph invariant #4: For any node N, all paths starting at N
      // which consist of only defer-edges and a single trailing points-to edge
      // must lead to the same
      assert(Nd->matchPointToOfDefers(allowMerge));
  
      // Verify the node to value mapping...
      if (Nd->mappedValue && !(allowMerge && Nd->isMerged)) {
        assert(Nd == Values2Nodes.lookup(Nd->mappedValue));
        assert(EA->isPointer(Nd->mappedValue));
        // Nodes must always be mapped from the pointer root value.
        assert(Nd->mappedValue == EA->getPointerRoot(Nd->mappedValue));
      }
    }
  #endif
  }
  
  //===----------------------------------------------------------------------===//
  //                          EscapeAnalysis
  //===----------------------------------------------------------------------===//
  
  EscapeAnalysis::EscapeAnalysis(SILModule *M)
      : BottomUpIPAnalysis(SILAnalysisKind::Escape), M(M),
        ArrayType(M->getASTContext().getArrayDecl()), BCA(nullptr) {}
  
  void EscapeAnalysis::initialize(SILPassManager *PM) {
    BCA = PM->getAnalysis<BasicCalleeAnalysis>();
  }
  
  /// Returns true if we need to add defer edges for the arguments of a block.
  static bool linkBBArgs(SILBasicBlock *BB) {
    // Don't need to handle function arguments.
    if (BB == &BB->getParent()->front())
      return false;
    // We don't need to link to the try_apply's normal result argument, because
    // we handle it separately in setAllEscaping() and mergeCalleeGraph().
    if (SILBasicBlock *SinglePred = BB->getSinglePredecessorBlock()) {
      auto *TAI = dyn_cast<TryApplyInst>(SinglePred->getTerminator());
      if (TAI && BB == TAI->getNormalBB())
        return false;
    }
    return true;
  }
  
  void EscapeAnalysis::buildConnectionGraph(FunctionInfo *FInfo,
                                            FunctionOrder &BottomUpOrder,
                                            int RecursionDepth) {
    if (BottomUpOrder.prepareForVisiting(FInfo))
      return;
  
    LLVM_DEBUG(llvm::dbgs() << "  >> build graph for "
                            << FInfo->Graph.F->getName() << '\n');
  
    FInfo->NeedUpdateSummaryGraph = true;
  
    ConnectionGraph *ConGraph = &FInfo->Graph;
    assert(ConGraph->isEmpty());
  
    // Visit the blocks in dominance order.
    ReachableBlocks reachable(ConGraph->F);
    reachable.visit([&](SILBasicBlock *bb) {
      // Create edges for the instructions.
      for (auto &i : *bb) {
        analyzeInstruction(&i, FInfo, BottomUpOrder, RecursionDepth);
        
        // Bail if the graph gets too big. The node merging algorithm has
        // quadratic complexity and we want to avoid this.
        // TODO: fix the quadratic complexity (if possible) and remove this limit.
        if (ConGraph->Nodes.size() > 10000) {
          ConGraph->invalidate();
          return false;
        }
      }
      return true;
    });
  
    if (!ConGraph->isValid())
      return;
  
    // Second step: create defer-edges for block arguments.
    for (SILBasicBlock &BB : *ConGraph->F) {
      if (!reachable.isVisited(&BB))
        continue;
  
      if (!linkBBArgs(&BB))
        continue;
  
      // Create defer-edges from the block arguments to it's values in the
      // predecessor's terminator instructions.
      for (SILArgument *BBArg : BB.getArguments()) {
        llvm::SmallVector<SILValue,4> Incoming;
        if (!BBArg->getSingleTerminatorOperands(Incoming)) {
          // We don't know where the block argument comes from -> treat it
          // conservatively.
          ConGraph->setEscapesGlobal(BBArg);
          continue;
        }
        CGNode *ArgNode = ConGraph->getNode(BBArg);
        if (!ArgNode)
          continue;
  
        for (SILValue Src : Incoming) {
          CGNode *SrcArg = ConGraph->getNode(Src);
          if (SrcArg) {
            ArgNode = ConGraph->defer(ArgNode, SrcArg);
          } else {
            ConGraph->setEscapesGlobal(BBArg);
            break;
          }
        }
      }
    }
    LLVM_DEBUG(llvm::dbgs() << "  << finished graph for "
                            << FInfo->Graph.F->getName() << '\n');
  }
  
  bool EscapeAnalysis::buildConnectionGraphForCallees(
      SILInstruction *Caller, CalleeList Callees, FunctionInfo *FInfo,
      FunctionOrder &BottomUpOrder, int RecursionDepth) {
    if (Callees.allCalleesVisible()) {
      // Derive the connection graph of the apply from the known callees.
      for (SILFunction *Callee : Callees) {
        FunctionInfo *CalleeInfo = getFunctionInfo(Callee);
        CalleeInfo->addCaller(FInfo, Caller);
        if (!CalleeInfo->isVisited()) {
          // Recursively visit the called function.
          buildConnectionGraph(CalleeInfo, BottomUpOrder, RecursionDepth + 1);
          BottomUpOrder.tryToSchedule(CalleeInfo);
        }
      }
      return true;
    }
    return false;
  }
  
  /// Build the connection graph for destructors that may be called
  /// by a given instruction \I for the object \V.
  /// Returns true if V is a local object and destructors called by a given
  /// instruction could be determined. In all other cases returns false.
  bool EscapeAnalysis::buildConnectionGraphForDestructor(
      SILValue V, SILInstruction *I, FunctionInfo *FInfo,
      FunctionOrder &BottomUpOrder, int RecursionDepth) {
    // It should be a locally allocated object.
    if (!pointsToLocalObject(V))
      return false;
  
    // Determine the exact type of the value.
    auto Ty = getExactDynamicTypeOfUnderlyingObject(V, nullptr);
    if (!Ty) {
      // The object is local, but we cannot determine its type.
      return false;
    }
    // If Ty is an optional, its deallocation is equivalent to the deallocation
    // of its payload.
    // TODO: Generalize it. Destructor of an aggregate type is equivalent to calling
    // destructors for its components.
    while (auto payloadTy = Ty.getOptionalObjectType())
      Ty = payloadTy;
    auto Class = Ty.getClassOrBoundGenericClass();
    if (!Class || Class->hasClangNode())
      return false;
    auto Destructor = Class->getDestructor();
    SILDeclRef DeallocRef(Destructor, SILDeclRef::Kind::Deallocator);
    // Find a SILFunction for destructor.
    SILFunction *Dealloc = M->lookUpFunction(DeallocRef);
    if (!Dealloc)
      return false;
    CalleeList Callees(Dealloc);
    return buildConnectionGraphForCallees(I, Callees, FInfo, BottomUpOrder,
                                          RecursionDepth);
  }
  
  EscapeAnalysis::ArrayUninitCall
  EscapeAnalysis::canOptimizeArrayUninitializedCall(ApplyInst *ai) {
    ArrayUninitCall call;
    // This must be an exact match so we don't accidentally optimize
    // "array.uninitialized_intrinsic".
    if (!ArraySemanticsCall(ai, "array.uninitialized", false))
      return call;
  
    // Check if the result is used in the usual way: extracting the
    // array and the element pointer with tuple_extract.
    //
    // Do not ignore any uses, even redundant tuple_extract, because all apply
    // uses must be mapped to ConnectionGraph nodes by the client of this API.
    for (Operand *use : getNonDebugUses(ai)) {
      if (auto *tei = dyn_cast<TupleExtractInst>(use->getUser())) {
        if (tei->getFieldIndex() == 0 && !call.arrayStruct) {
          call.arrayStruct = tei;
          continue;
        }
        if (tei->getFieldIndex() == 1 && !call.arrayElementPtr) {
          call.arrayElementPtr = tei;
          continue;
        }
      }
      if (auto *dt = dyn_cast<DestructureTupleInst>(use->getUser())) {
        call.arrayStruct = dt->getResult(0);
        call.arrayElementPtr = dt->getResult(1);
        continue;
      }
      // If there are any other uses, such as a release_value, erase the previous
      // call info and bail out.
      call.arrayStruct = nullptr;
      call.arrayElementPtr = nullptr;
      break;
    }
    // An "array.uninitialized" call may have a first argument which is the
    // allocated array buffer. Make sure the call's argument is recognized by
    // EscapeAnalysis as a pointer, otherwise createArrayUninitializedSubgraph
    // won't be able to map the result nodes onto it. There is a variant of
    // @_semantics("array.uninitialized") that does not take the storage as input,
    // so it will effectively bail out here.
    if (isPointer(ai->getArgument(0)))
      call.arrayStorageRef = ai->getArgument(0);
    return call;
  }
  
  bool EscapeAnalysis::canOptimizeArrayUninitializedResult(
      SILInstruction *extract) {
    assert(isa<TupleExtractInst>(extract) || isa<DestructureTupleInst>(extract));
    ApplyInst *ai = dyn_cast<ApplyInst>(extract->getOperand(0));
    if (!ai)
      return false;
  
    return canOptimizeArrayUninitializedCall(ai).isValid();
  }
  
  // Handle @_semantics("array.uninitialized")
  //
  // This call is analagous to a 'struct(storageRef)' instruction--we want a defer
  // edge from the returned Array struct to the storage Reference that it
  // contains.
  //
  // The returned unsafe pointer is handled simply by mapping the pointer value
  // onto the object node that the storage argument points to.
  void EscapeAnalysis::createArrayUninitializedSubgraph(
      ArrayUninitCall call, ConnectionGraph *conGraph) {
    CGNode *arrayStructNode = conGraph->getNode(call.arrayStruct);
    assert(arrayStructNode && "Array struct must have a node");
  
    CGNode *arrayRefNode = conGraph->getNode(call.arrayStorageRef);
    assert(arrayRefNode && "canOptimizeArrayUninitializedCall checks isPointer");
    // If the arrayRefNode != null then arrayObjNode must be valid.
    CGNode *arrayObjNode = conGraph->getValueContent(call.arrayStorageRef);
  
    // The reference argument is effectively stored inside the returned
    // array struct. This is like struct(arrayRefNode).
    conGraph->defer(arrayStructNode, arrayRefNode);
  
    // Map the returned element pointer to the array object's field pointer.
    conGraph->setNode(call.arrayElementPtr, arrayObjNode);
  }
  
  void EscapeAnalysis::analyzeInstruction(SILInstruction *I,
                                          FunctionInfo *FInfo,
                                          FunctionOrder &BottomUpOrder,
                                          int RecursionDepth) {
    ConnectionGraph *ConGraph = &FInfo->Graph;
    FullApplySite FAS = FullApplySite::isa(I);
    if (FAS &&
        // We currently don't support co-routines. In most cases co-routines will be inlined anyway.
        !isa<BeginApplyInst>(I)) {
      ArraySemanticsCall ASC(FAS.getInstruction());
      switch (ASC.getKind()) {
        // TODO: Model ReserveCapacityForAppend, AppendContentsOf, AppendElement.
        case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
        case ArrayCallKind::kCheckSubscript:
        case ArrayCallKind::kCheckIndex:
        case ArrayCallKind::kGetCount:
        case ArrayCallKind::kGetCapacity:
        case ArrayCallKind::kMakeMutable:
          // These array semantics calls do not capture anything.
          return;
        case ArrayCallKind::kArrayUninitialized: {
          ArrayUninitCall call = canOptimizeArrayUninitializedCall(
              cast<ApplyInst>(FAS.getInstruction()));
          if (call.isValid()) {
            createArrayUninitializedSubgraph(call, ConGraph);
            return;
          }
          break;
        }
        case ArrayCallKind::kGetElement:
          if (CGNode *ArrayObjNode = ConGraph->getValueContent(ASC.getSelf())) {
            CGNode *LoadedElement = nullptr;
            // This is like a load from a ref_element_addr.
            if (ASC.hasGetElementDirectResult()) {
              LoadedElement = ConGraph->getNode(ASC.getCallResult());
            } else {
              // The content of the destination address.
              LoadedElement = ConGraph->getValueContent(FAS.getArgument(0));
              assert(LoadedElement && "indirect result must have node");
            }
            if (LoadedElement) {
              if (CGNode *arrayElementStorage =
                      ConGraph->getFieldContent(ArrayObjNode)) {
                ConGraph->defer(arrayElementStorage, LoadedElement);
                return;
              }
            }
          }
          break;
        case ArrayCallKind::kGetElementAddress:
          // This is like a ref_element_addr. Both the object node and the
          // returned address point to the same element storage.
          if (CGNode *ArrayObjNode = ConGraph->getValueContent(ASC.getSelf())) {
            CGNode *arrayElementAddress = ConGraph->getNode(ASC.getCallResult());
            ConGraph->defer(ArrayObjNode, arrayElementAddress);
            return;
          }
          break;
        case ArrayCallKind::kWithUnsafeMutableBufferPointer:
          // Model this like an escape of the elements of the array and a capture
          // of anything captured by the closure.
          // Self is passed inout.
          if (CGNode *ArrayStructNode =
                  ConGraph->getValueContent(ASC.getSelf())) {
            // The first non indirect result is the closure.
            auto Args = FAS.getArgumentsWithoutIndirectResults();
            ConGraph->setEscapesGlobal(Args[0]);
  
            // One content node for going from the array buffer pointer to
            // the element address (like ref_element_addr).
            CGNode *ArrayObjNode =
                ConGraph->getOrCreateContentNode(ArrayStructNode,
                                                 /*isInterior*/ true,
                                                 /*hasRefOnly*/ false);
            // If ArrayObjNode was already potentially merged with its pointsTo,
            // then conservatively mark the whole thing as escaping.
            if (!ArrayObjNode->isInterior()) {
              ArrayObjNode->markEscaping();
              return;
            }
            // Otherwise, create the content node for the element storage.
            CGNode *ArrayElementStorage = ConGraph->getOrCreateContentNode(
                ArrayObjNode, /*isInterior*/ false,
                /*hasRefOnly*/ true);
            ArrayElementStorage->markEscaping();
            return;
          }
          break;
        default:
          break;
        }
  
      if (RecursionDepth < MaxRecursionDepth) {
        CalleeList Callees = BCA->getCalleeList(FAS);
        if (buildConnectionGraphForCallees(FAS.getInstruction(), Callees, FInfo,
                                           BottomUpOrder, RecursionDepth))
          return;
      }
  
      if (auto *Fn = FAS.getReferencedFunctionOrNull()) {
        if (Fn->getName() == "swift_bufferAllocate")
          // The call is a buffer allocation, e.g. for Array.
          return;
      }
    }
  
    if (isa<StrongReleaseInst>(I) || isa<ReleaseValueInst>(I) ||
        isa<DestroyValueInst>(I)) {
      // Treat the release instruction as if it is the invocation
      // of a deinit function.
      if (RecursionDepth < MaxRecursionDepth) {
        // Check if the destructor is known.
        auto OpV = I->getOperand(0);
        if (buildConnectionGraphForDestructor(OpV, I, FInfo, BottomUpOrder,
                                              RecursionDepth))
          return;
      }
    }
  
    // If this instruction produces a single value whose pointer is represented by
    // a different base pointer, then skip it.
    if (auto *SVI = dyn_cast<SingleValueInstruction>(I)) {
      if (getPointerBase(SVI))
        return;
  
      // Instructions which return the address of non-writable memory cannot have
      // an effect on escaping.
      if (isNonWritableMemoryAddress(SVI))
        return;
    }
  
    // Incidental uses produce no values and have no effect on their operands.
    if (isIncidentalUse(I))
      return;
  
    switch (I->getKind()) {
      case SILInstructionKind::AllocStackInst:
      case SILInstructionKind::AllocRefInst:
      case SILInstructionKind::AllocBoxInst:
        ConGraph->getNode(cast<SingleValueInstruction>(I));
        return;
  
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)            \
    case SILInstructionKind::Name##RetainInst:                                   \
    case SILInstructionKind::StrongRetain##Name##Inst:
  #include "swift/AST/ReferenceStorage.def"
      case SILInstructionKind::DeallocStackInst:
      case SILInstructionKind::StrongRetainInst:
      case SILInstructionKind::RetainValueInst:
      case SILInstructionKind::BranchInst:
      case SILInstructionKind::CondBranchInst:
      case SILInstructionKind::SwitchEnumInst:
      case SILInstructionKind::DebugValueInst:
      case SILInstructionKind::ValueMetatypeInst:
      case SILInstructionKind::InitExistentialMetatypeInst:
      case SILInstructionKind::OpenExistentialMetatypeInst:
      case SILInstructionKind::ExistentialMetatypeInst:
      case SILInstructionKind::DeallocRefInst:
      case SILInstructionKind::SetDeallocatingInst:
      case SILInstructionKind::FixLifetimeInst:
      case SILInstructionKind::ClassifyBridgeObjectInst:
        // Early bailout: These instructions never produce a pointer value and
        // have no escaping effect on their operands.
        assert(!llvm::any_of(I->getResults(), [this](SILValue result) {
          return isPointer(result);
        }));
        return;
      case SILInstructionKind::BeginBorrowInst:
      case SILInstructionKind::CopyValueInst: {
        auto svi = cast<SingleValueInstruction>(I);
        CGNode *resultNode = ConGraph->getNode(svi);
        if (CGNode *opNode = ConGraph->getNode(svi->getOperand(0))) {
          ConGraph->defer(resultNode, opNode);
          return;
        }
        ConGraph->setEscapesGlobal(svi);
        return;
      }
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
      case SILInstructionKind::Name##ReleaseInst:
  #include "swift/AST/ReferenceStorage.def"
      case SILInstructionKind::DestroyValueInst:
      case SILInstructionKind::StrongReleaseInst:
      case SILInstructionKind::ReleaseValueInst: {
        // A release instruction may deallocate the pointer operand. This may
        // capture anything pointed to by the released object, but not the object
        // itself (because it will be a dangling pointer after deallocation).
        SILValue OpV = I->getOperand(0);
        CGNode *objNode = ConGraph->getValueContent(OpV);
        if (!objNode)
          return;
  
        CGNode *fieldNode = ConGraph->getFieldContent(objNode);
        if (!fieldNode) {
          // In the unexpected case that the object has no field content, create
          // escaping unknown content.
          //
          // TODO: Why does this need to be "escaping"? The fields can't escape
          // during deinitialization.
          ConGraph->getOrCreateUnknownContent(objNode)->markEscaping();
          return;
        }
        if (!deinitIsKnownToNotCapture(OpV)) {
          // Find out if the object's fields may have any references or pointers.
          PointerKind propertiesKind =
              findCachedClassPropertiesKind(OpV->getType(), *OpV->getFunction());
          if (propertiesKind != EscapeAnalysis::NoPointer)
            ConGraph->getOrCreateUnknownContent(fieldNode)->markEscaping();
          return;
        }
        // This deinit is known to not directly capture it's own field content;
        // however, other secondary deinitializers could still capture anything
        // pointed to by references within those fields. Since secondary
        // deinitializers only apply to reference-type fields, not pointer-type
        // fields, the "field" content can initially be considered an indirect
        // reference. Unfortunately, we can't know all possible reference types
        // that may eventually be associated with 'fieldContent', so we must
        // assume here that 'fieldContent2' could hold raw pointers. This is
        // implied by passing in invalid SILValue.
        CGNode *escapingNode =
            ConGraph->getOrCreateReferenceContent(SILValue(), fieldNode);
        if (CGNode *indirectFieldNode = escapingNode->getContentNodeOrNull())
          escapingNode = indirectFieldNode;
  
        ConGraph->getOrCreateUnknownContent(escapingNode)->markEscaping();
        return;
      }
      case SILInstructionKind::DestroyAddrInst: {
        SILValue addressVal = I->getOperand(0);
        CGNode *valueNode = ConGraph->getValueContent(addressVal);
        if (!valueNode)
          return;
  
        // The value's destructor may escape anything the value points to.
        // This could be an object referenced by the value or the contents of an
        // existential box.
        if (CGNode *fieldNode = ConGraph->getFieldContent(valueNode)) {
          ConGraph->getOrCreateUnknownContent(fieldNode)->markEscaping();
          return;
        }
        ConGraph->getOrCreateUnknownContent(valueNode)->markEscaping();
        return;
      }
  
  #define NEVER_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
      case SILInstructionKind::Load##Name##Inst:
  #include "swift/AST/ReferenceStorage.def"
      case SILInstructionKind::LoadInst: {
        assert(!cast<SingleValueInstruction>(I)->getType().isAddress());
        // For loads, get the address-type operand and return the content node
        // that the address directly points to. The load's address may itself come
        // from a ref_element_addr, project_box or open_existential, in which
        // case, the loaded content will be the field content, not the RC
        // content.
        auto SVI = cast<SingleValueInstruction>(I);
        if (!isPointer(SVI))
          return;
  
        if (CGNode *PointsTo = ConGraph->getValueContent(SVI->getOperand(0))) {
          ConGraph->setNode(SVI, PointsTo);
          return;
        }
        // A load from an address we don't handle -> be conservative.
        ConGraph->setEscapesGlobal(SVI);
        break;
      }
      case SILInstructionKind::RefElementAddrInst:
      case SILInstructionKind::RefTailAddrInst:
      case SILInstructionKind::ProjectBoxInst: {
        // For projections into objects, get the non-address reference operand and
        // return an interior content node that the reference points to.
        auto SVI = cast<SingleValueInstruction>(I);
        if (CGNode *PointsTo = ConGraph->getValueContent(SVI->getOperand(0))) {
          ConGraph->setNode(SVI, PointsTo);
          return;
        }
        // A load or projection from an address we don't handle -> be
        // conservative.
        ConGraph->setEscapesGlobal(SVI);
        return;
      }
      case SILInstructionKind::CopyAddrInst: {
        // Be conservative if the dest may be the final release.
        if (!cast<CopyAddrInst>(I)->isInitializationOfDest()) {
          setAllEscaping(I, ConGraph);
          return;
        }
  
        // A copy_addr is like a 'store (load src) to dest'.
        SILValue srcAddr = I->getOperand(CopyAddrInst::Src);
        CGNode *loadedContent = ConGraph->getValueContent(srcAddr);
        if (!loadedContent) {
          setAllEscaping(I, ConGraph);
          break;
        }
        SILValue destAddr = I->getOperand(CopyAddrInst::Dest);
        // Create a defer-edge from the store location to the loaded content.
        if (CGNode *destContent = ConGraph->getValueContent(destAddr)) {
          ConGraph->defer(destContent, loadedContent);
          return;
        }
        // A store to an address we don't handle -> be conservative.
        ConGraph->setEscapesGlobal(srcAddr);
        return;
      }
  
  #define NEVER_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...) \
      case SILInstructionKind::Store##Name##Inst:
  #include "swift/AST/ReferenceStorage.def"
      case SILInstructionKind::StoreInst: {
        SILValue srcVal = I->getOperand(StoreInst::Src);
        CGNode *valueNode = ConGraph->getNode(srcVal);
        // If the stored value isn't tracked, ignore the store.
        if (!valueNode)
          return;
  
        // The store destination content is always one pointsTo level away from
        // its address.  Either the address points to a variable or argument, and
        // the pointee is removed by a level of pointer indirection, or the
        // address corresponds is a projection within a reference counted object
        // (via ref_element_addr, project_box, or open_existential_addr) where the
        // stored field content is chained one level below the RC content.
        SILValue destAddr = I->getOperand(StoreInst::Dest);
        if (CGNode *pointsTo = ConGraph->getValueContent(destAddr)) {
          // Create a defer-edge from the content to the stored value.
          ConGraph->defer(pointsTo, valueNode);
          return;
        }
        // A store to an address we don't handle -> be conservative.
        ConGraph->setEscapesGlobal(srcVal);
        return;
      }
      case SILInstructionKind::PartialApplyInst: {
        // The result of a partial_apply is a thick function which stores the
        // boxed partial applied arguments. We create defer-edges from the
        // partial_apply values to the arguments.
        auto PAI = cast<PartialApplyInst>(I);
        if (CGNode *ResultNode = ConGraph->getNode(PAI)) {
          for (const Operand &Op : PAI->getAllOperands()) {
            if (CGNode *ArgNode = ConGraph->getNode(Op.get())) {
              ResultNode = ConGraph->defer(ResultNode, ArgNode);
            }
          }
        }
        return;
      }
      case SILInstructionKind::SelectEnumInst:
      case SILInstructionKind::SelectEnumAddrInst:
        analyzeSelectInst(cast<SelectEnumInstBase>(I), ConGraph);
        return;
      case SILInstructionKind::SelectValueInst:
        analyzeSelectInst(cast<SelectValueInst>(I), ConGraph);
        return;
      case SILInstructionKind::EndCOWMutationInst:
      case SILInstructionKind::StructInst:
      case SILInstructionKind::TupleInst:
      case SILInstructionKind::EnumInst: {
        // Aggregate composition is like assigning the aggregate fields to the
        // resulting aggregate value.
        auto svi = cast<SingleValueInstruction>(I);
        CGNode *resultNode = ConGraph->getNode(svi);
        for (const Operand &operand : svi->getAllOperands()) {
          if (CGNode *subNode = ConGraph->getNode(operand.get()))
            ConGraph->defer(resultNode, subNode);
        }
        return;
      }
      case SILInstructionKind::TupleExtractInst: {
        // This is a tuple_extract which extracts the second result of an
        // array.uninitialized call (otherwise getPointerBase should have already
        // looked through it).
        assert(canOptimizeArrayUninitializedResult(I)
               && "tuple_extract should be handled as projection");
        return;
      }
      case SILInstructionKind::DestructureTupleInst: {
        if (canOptimizeArrayUninitializedResult(I)) {
          return;
        }
        setAllEscaping(I, ConGraph);
        return;
      }
      case SILInstructionKind::UncheckedRefCastAddrInst: {
        auto *URCAI = cast<UncheckedRefCastAddrInst>(I);
        CGNode *SrcNode = ConGraph->getNode(URCAI->getSrc());
        CGNode *DestNode = ConGraph->getNode(URCAI->getDest());
        assert(SrcNode && DestNode && "must have nodes for address operands");
        ConGraph->defer(DestNode, SrcNode);
        return;
      }
      case SILInstructionKind::ReturnInst: {
        SILValue returnVal = cast<ReturnInst>(I)->getOperand();
        if (CGNode *ValueNd = ConGraph->getNode(returnVal)) {
          ConGraph->defer(ConGraph->getReturnNode(), ValueNd);
          ConGraph->getValueContent(returnVal)->mergeEscapeState(
              EscapeState::Return);
        }
        return;
      }
      default:
        // We handle all other instructions conservatively.
        setAllEscaping(I, ConGraph);
        return;
    }
  }
  
  template<class SelectInst> void EscapeAnalysis::
  analyzeSelectInst(SelectInst *SI, ConnectionGraph *ConGraph) {
    if (auto *ResultNode = ConGraph->getNode(SI)) {
      // Connect all case values to the result value.
      // Note that this does not include the first operand (the condition).
      for (unsigned Idx = 0, End = SI->getNumCases(); Idx < End; ++Idx) {
        SILValue CaseVal = SI->getCase(Idx).second;
        auto *ArgNode = ConGraph->getNode(CaseVal);
        assert(ArgNode &&
               "there should be an argument node if there is a result node");
        ResultNode = ConGraph->defer(ResultNode, ArgNode);
      }
      // ... also including the default value.
      auto *DefaultNode = ConGraph->getNode(SI->getDefaultResult());
      assert(DefaultNode &&
             "there should be an argument node if there is a result node");
      ConGraph->defer(ResultNode, DefaultNode);
    }
  }
  
  bool EscapeAnalysis::deinitIsKnownToNotCapture(SILValue V) {
    for (;;) {
      // The deinit of an array buffer does not capture the array elements.
      if (V->getType().getNominalOrBoundGenericNominal() == ArrayType)
        return true;
  
      // The deinit of a box does not capture its content.
      if (V->getType().is<SILBoxType>())
        return true;
  
      if (isa<FunctionRefInst>(V) || isa<DynamicFunctionRefInst>(V) ||
          isa<PreviousDynamicFunctionRefInst>(V))
        return true;
  
      // Check all operands of a partial_apply
      if (auto *PAI = dyn_cast<PartialApplyInst>(V)) {
        for (Operand &Op : PAI->getAllOperands()) {
          if (isPointer(Op.get()) && !deinitIsKnownToNotCapture(Op.get()))
            return false;
        }
        return true;
      }
      if (auto base = getPointerBase(V)) {
        V = base;
        continue;
      }
      return false;
    }
  }
  
  void EscapeAnalysis::setAllEscaping(SILInstruction *I,
                                      ConnectionGraph *ConGraph) {
    if (auto *TAI = dyn_cast<TryApplyInst>(I)) {
      ConGraph->setEscapesGlobal(TAI->getNormalBB()->getArgument(0));
      ConGraph->setEscapesGlobal(TAI->getErrorBB()->getArgument(0));
    }
    // Even if the instruction does not write memory we conservatively set all
    // operands to escaping, because they may "escape" to the result value in
    // an unspecified way. For example consider bit-casting a pointer to an int.
    // In this case we don't even create a node for the resulting int value.
    for (const Operand &Op : I->getAllOperands()) {
      SILValue OpVal = Op.get();
      if (!isNonWritableMemoryAddress(OpVal))
        ConGraph->setEscapesGlobal(OpVal);
    }
    // Even if the instruction does not write memory it could e.g. return the
    // address of global memory. Therefore we have to define it as escaping.
    for (auto result : I->getResults())
      ConGraph->setEscapesGlobal(result);
  }
  
  void EscapeAnalysis::recompute(FunctionInfo *Initial) {
    allocNewUpdateID();
  
    LLVM_DEBUG(llvm::dbgs() << "recompute escape analysis with UpdateID "
                            << getCurrentUpdateID() << '\n');
  
    // Collect and analyze all functions to recompute, starting at Initial.
    FunctionOrder BottomUpOrder(getCurrentUpdateID());
    buildConnectionGraph(Initial, BottomUpOrder, 0);
  
    // Build the bottom-up order.
    BottomUpOrder.tryToSchedule(Initial);
    BottomUpOrder.finishScheduling();
  
    // Second step: propagate the connection graphs up the call-graph until it
    // stabilizes.
    int Iteration = 0;
    bool NeedAnotherIteration;
    do {
      LLVM_DEBUG(llvm::dbgs() << "iteration " << Iteration << '\n');
      NeedAnotherIteration = false;
  
      for (FunctionInfo *FInfo : BottomUpOrder) {
        bool SummaryGraphChanged = false;
        if (FInfo->NeedUpdateSummaryGraph) {
          LLVM_DEBUG(llvm::dbgs() << "  create summary graph for "
                                  << FInfo->Graph.F->getName() << '\n');
  
          PrettyStackTraceSILFunction
            callerTraceRAII("merging escape summary", FInfo->Graph.F);
          FInfo->Graph.propagateEscapeStates();
  
          // Derive the summary graph of the current function. Even if the
          // complete graph of the function did change, it does not mean that the
          // summary graph will change.
          SummaryGraphChanged = mergeSummaryGraph(&FInfo->SummaryGraph,
                                                  &FInfo->Graph);
          FInfo->NeedUpdateSummaryGraph = false;
        }
  
        if (Iteration < MaxGraphMerges) {
          // In the first iteration we have to merge the summary graphs, even if
          // they didn't change (in not recomputed leaf functions).
          if (Iteration == 0 || SummaryGraphChanged) {
            // Merge the summary graph into all callers.
            for (const auto &E : FInfo->getCallers()) {
              assert(E.isValid());
  
              // Only include callers which we are actually recomputing.
              if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(E.Caller)) {
                PrettyStackTraceSILFunction
                  calleeTraceRAII("merging escape graph", FInfo->Graph.F);
                PrettyStackTraceSILFunction
                  callerTraceRAII("...into", E.Caller->Graph.F);
                LLVM_DEBUG(llvm::dbgs() << "  merge "
                                        << FInfo->Graph.F->getName()
                                        << " into "
                                        << E.Caller->Graph.F->getName() << '\n');
                if (mergeCalleeGraph(E.FAS, &E.Caller->Graph,
                                     &FInfo->SummaryGraph)) {
                  E.Caller->NeedUpdateSummaryGraph = true;
                  if (!E.Caller->isScheduledAfter(FInfo)) {
                    // This happens if we have a cycle in the call-graph.
                    NeedAnotherIteration = true;
                  }
                }
              }
            }
          }
        } else if (Iteration == MaxGraphMerges) {
          // Limit the total number of iterations. First to limit compile time,
          // second to make sure that the loop terminates. Theoretically this
          // should always be the case, but who knows?
          LLVM_DEBUG(llvm::dbgs() << "  finalize conservatively "
                                  << FInfo->Graph.F->getName() << '\n');
          for (const auto &E : FInfo->getCallers()) {
            assert(E.isValid());
            if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(E.Caller)) {
              setAllEscaping(E.FAS, &E.Caller->Graph);
              E.Caller->NeedUpdateSummaryGraph = true;
              NeedAnotherIteration = true;
            }
          }
        }
      }
      ++Iteration;
    } while (NeedAnotherIteration);
  
    for (FunctionInfo *FInfo : BottomUpOrder) {
      if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(FInfo)) {
        FInfo->Graph.computeUsePoints();
        FInfo->Graph.verify();
        FInfo->SummaryGraph.verifyStructure();
      }
    }
  }
  
  bool EscapeAnalysis::mergeCalleeGraph(SILInstruction *AS,
                                        ConnectionGraph *CallerGraph,
                                        ConnectionGraph *CalleeGraph) {
    if (!CallerGraph->isValid())
      return false;
      
    if (!CalleeGraph->isValid()) {
      setAllEscaping(AS, CallerGraph);
      // Conservatively assume that setting that setAllEscaping(AS) did change the
      // graph.
      return true;
    }
                                        
    // This CGNodeMap uses an intrusive worklist to keep track of Mapped nodes
    // from the CalleeGraph. Meanwhile, mergeFrom uses separate intrusive
    // worklists to update nodes in the CallerGraph.
    CGNodeMap Callee2CallerMapping(CalleeGraph);
  
    // First map the callee parameters to the caller arguments.
    SILFunction *Callee = CalleeGraph->F;
    auto FAS = FullApplySite::isa(AS);
    unsigned numCallerArgs = FAS ? FAS.getNumArguments() : 1;
    unsigned numCalleeArgs = Callee->getArguments().size();
    assert(numCalleeArgs >= numCallerArgs);
    for (unsigned Idx = 0; Idx < numCalleeArgs; ++Idx) {
      // If there are more callee parameters than arguments it means that the
      // callee is the result of a partial_apply - a thick function. A thick
      // function also references the boxed partially applied arguments.
      // Therefore we map all the extra callee parameters to the callee operand
      // of the apply site.
      SILValue CallerArg;
      if (FAS)
        CallerArg =
            (Idx < numCallerArgs ? FAS.getArgument(Idx) : FAS.getCallee());
      else
        CallerArg = (Idx < numCallerArgs ? AS->getOperand(Idx) : SILValue());
  
      CGNode *CalleeNd = CalleeGraph->getNode(Callee->getArgument(Idx));
      if (!CalleeNd)
        continue;
  
      CGNode *CallerNd = CallerGraph->getNode(CallerArg);
      // There can be the case that we see a callee argument as pointer but not
      // the caller argument. E.g. if the callee argument has a @convention(c)
      // function type and the caller passes a function_ref.
      if (!CallerNd)
        continue;
  
      Callee2CallerMapping.add(CalleeNd, CallerNd);
    }
  
    // Map the return value.
    if (CGNode *RetNd = CalleeGraph->getReturnNodeOrNull()) {
      // The non-ApplySite instructions that cause calls are to things like
      // destructors that don't have return values.
      assert(FAS);
      ValueBase *CallerReturnVal = nullptr;
      if (auto *TAI = dyn_cast<TryApplyInst>(AS)) {
        CallerReturnVal = TAI->getNormalBB()->getArgument(0);
      } else {
        CallerReturnVal = cast<ApplyInst>(AS);
      }
      CGNode *CallerRetNd = CallerGraph->getNode(CallerReturnVal);
      if (CallerRetNd)
        Callee2CallerMapping.add(RetNd, CallerRetNd);
    }
    return CallerGraph->mergeFrom(CalleeGraph, Callee2CallerMapping);
  }
  
  bool EscapeAnalysis::mergeSummaryGraph(ConnectionGraph *SummaryGraph,
                                          ConnectionGraph *Graph) {
    if (!Graph->isValid()) {
      bool changed = SummaryGraph->isValid();
      SummaryGraph->invalidate();
      return changed;
    }
  
    // Make a 1-to-1 mapping of all arguments and the return value. This CGNodeMap
    // node map uses an intrusive worklist to keep track of Mapped nodes from the
    // Graph. Meanwhile, mergeFrom uses separate intrusive worklists to
    // update nodes in the SummaryGraph.
    CGNodeMap Mapping(Graph);
    for (SILArgument *Arg : Graph->F->getArguments()) {
      if (CGNode *ArgNd = Graph->getNode(Arg)) {
        Mapping.add(ArgNd, SummaryGraph->getNode(Arg));
      }
    }
    if (CGNode *RetNd = Graph->getReturnNodeOrNull()) {
      Mapping.add(RetNd, SummaryGraph->getReturnNode());
    }
    // Merging actually creates the summary graph.
    return SummaryGraph->mergeFrom(Graph, Mapping);
  }
  
  // Return true if any content within the logical object pointed to by \p value
  // escapes.
  //
  // Get the value's content node and check the escaping flag on all nodes within
  // that object. An interior CG node points to content within the same object.
  bool EscapeAnalysis::canEscapeToUsePoint(SILValue value,
                                           SILInstruction *usePoint,
                                           ConnectionGraph *conGraph) {
  
    assert((FullApplySite::isa(usePoint) || isa<RefCountingInst>(usePoint) ||
            isa<DestroyValueInst>(usePoint)) &&
           "use points are only created for calls and refcount instructions");
  
    CGNode *node = conGraph->getValueContent(value);
    if (!node)
      return true;
  
    // Follow points-to edges and return true if the current 'node' may escape at
    // 'usePoint'.
    CGNodeWorklist worklist(conGraph);
    while (node) {
      // Merging arbitrary nodes is supported, which may lead to cycles of
      // interior nodes. End the search.
      if (!worklist.tryPush(node))
        break;
  
      // First check if 'node' may escape in a way not represented by the
      // connection graph, assuming that it may represent part of the object
      // pointed to by 'value'. If 'node' happens to represent another object
      // indirectly reachabe from 'value', then it cannot actually escape to this
      // usePoint, so passing the original value is still conservatively correct.
      if (node->valueEscapesInsideFunction(value))
        return true;
  
      // No hidden escapes; check if 'usePoint' may access memory at 'node'.
      if (conGraph->isUsePoint(usePoint, node))
        return true;
  
      if (!node->isInterior())
        break;
  
      // Continue to check for escaping content whenever 'content' may point to
      // the same object as 'node'.
      node = node->getContentNodeOrNull();
    }
    return false;
  }
  
  bool EscapeAnalysis::canEscapeTo(SILValue V, FullApplySite FAS) {
    // If it's not a local object we don't know anything about the value.
    if (!isUniquelyIdentified(V))
      return true;
    auto *ConGraph = getConnectionGraph(FAS.getFunction());
    return canEscapeToUsePoint(V, FAS.getInstruction(), ConGraph);
  }
  
  // FIXME: remove this to avoid confusion with SILType.hasReferenceSemantics.
  static bool hasReferenceSemantics(SILType T) {
    // Exclude address types.
    return T.isObject() && T.hasReferenceSemantics();
  }
  
  bool EscapeAnalysis::canEscapeTo(SILValue V, RefCountingInst *RI) {
    // If it's not uniquely identified we don't know anything about the value.
    if (!isUniquelyIdentified(V))
      return true;
    auto *ConGraph = getConnectionGraph(RI->getFunction());
    return canEscapeToUsePoint(V, RI, ConGraph);
  }
  
  bool EscapeAnalysis::canEscapeTo(SILValue V, DestroyValueInst *DVI) {
    // If it's not uniquely identified we don't know anything about the value.
    if (!isUniquelyIdentified(V))
      return true;
    auto *ConGraph = getConnectionGraph(DVI->getFunction());
    return canEscapeToUsePoint(V, DVI, ConGraph);
  }
  
  /// Utility to get the function which contains both values \p V1 and \p V2.
  static SILFunction *getCommonFunction(SILValue V1, SILValue V2) {
    SILBasicBlock *BB1 = V1->getParentBlock();
    SILBasicBlock *BB2 = V2->getParentBlock();
    if (!BB1 || !BB2)
      return nullptr;
  
    SILFunction *F = BB1->getParent();
    assert(BB2->getParent() == F && "values not in same function");
    return F;
  }
  
  bool EscapeAnalysis::canPointToSameMemory(SILValue V1, SILValue V2) {
    // At least one of the values must be a non-escaping local object.
    bool isUniq1 = isUniquelyIdentified(V1);
    bool isUniq2 = isUniquelyIdentified(V2);
    if (!isUniq1 && !isUniq2)
      return true;
  
    SILFunction *F = getCommonFunction(V1, V2);
    if (!F)
      return true;
    auto *ConGraph = getConnectionGraph(F);
  
    CGNode *Content1 = ConGraph->getValueContent(V1);
    if (!Content1)
      return true;
  
    CGNode *Content2 = ConGraph->getValueContent(V2);
    if (!Content2)
      return true;
  
    // Finish the check for one value being a non-escaping local object.
    if (isUniq1 && Content1->valueEscapesInsideFunction(V1))
      isUniq1 = false;
  
    if (isUniq2 && Content2->valueEscapesInsideFunction(V2))
      isUniq2 = false;
  
    if (!isUniq1 && !isUniq2)
      return true;
  
    // Check if both nodes may point to the same content.
    // FIXME!!!: This will be rewritten to use node flags in the next commit.
    SILType T1 = V1->getType();
    SILType T2 = V2->getType();
    if (T1.isAddress() && T2.isAddress()) {
      return Content1 == Content2;
    }
    if (hasReferenceSemantics(T1) && hasReferenceSemantics(T2)) {
      return Content1 == Content2;
    }
    // As we model the ref_element_addr instruction as a content-relationship, we
    // have to go down one content level if just one of the values is a
    // ref-counted object.
    if (T1.isAddress() && hasReferenceSemantics(T2)) {
      Content2 = ConGraph->getFieldContent(Content2);
      return Content1 == Content2;
    }
    if (T2.isAddress() && hasReferenceSemantics(T1)) {
      Content1 = ConGraph->getFieldContent(Content1);
      return Content1 == Content2;
    }
    return true;
  }
  
  // Returns true if deinitialization of \p releasedPtr may release memory
  // directly pointed to by \p livePtr.
  //
  // The implementation is common between mayReleaseReferenceContent and
  // mayReleaseAddressContent, but the semantics are different. For references,
  // this models the release of the reference itself. For addresses, this models
  // the release of any reference pointed to by the address. The caller should
  // explicitly ask for the right one so they aren't surprised. Here we simply
  // switch behavior based on whether \p releasedPtr is an address type.
  //
  // Note that \p livePtr could be a reference itself, an address of a
  // local/argument that contains a reference, or even a pointer to the middle of
  // an object. (Even an exclusive argument may point to the middle of an object).
  //
  // This is similar to asking "is the content of livePtr reachable via
  // releasedPtr". There are two interesting cases in which a connection graph
  // query can determine that the accessed memory cannot be released:
  //
  // Case #1: \p livePtr points to a uniquely identified object that does not
  // escape within this function.
  //
  // In this case, it is sufficient to ensure that no connection graph path exists
  // from the content of \p livePtr to the content of \p releasedPtr.
  //
  // Note: A "uniquely identified object" is either locally allocated, which is
  // obviously not reachable outside this function, or an exclusive address, which
  // *is* reachable outside this function, but must have its own reference count
  // so cannot be released in this function or its callees.
  //
  // Case #2: The released reference points to a local object and no connection
  // graph path exists from the referenced object to a global-escaping or
  // argument-escaping node.
  //
  // TODO: This API is inneffective for release hoisting, because the release
  // itself is often the only place that an object's contents may escape. We can't
  // currently determine that since the contents cannot escape prior to \p
  // releasePtr, then livePtr cannot possible point to the same memory!
  //
  // TODO: In the future, we may have an AliasAnalysis query that distinguishes
  // between retain-sinking vs. release-hoisting. With SemanticARC, we may not
  // need to do this, but it is possible to be much more aggressive with
  // release-hoisting. This is becase, for a retain/release pair, it's always ok
  // to release earlier as long as there are no subsequent aliasing uses. If the
  // caller is only concerned with release hoisting and knows there are no
  // subsequent aliasing uses protected by a local release, then the connection
  // graph reachability check here only needs to search within the current object
  // (it can stop at a non-interior edge). This would assume that any indirectly
  // released reference needs to be kept alive by some distinct local
  // references--ARC can't remove those without inserting a
  // mark_dependence/end_dependence scope. It would also ignore the fact that
  // objects may contain raw pointers into themselves or into other objects. Any
  // access to the raw pointer is not considered a use of the object because that
  // access must be "guarded" by a fix_lifetime or mark_dependence/end_dependence
  // that acts as a placeholder.
  bool EscapeAnalysis::mayReleaseContent(SILValue releasedPtr, SILValue livePtr) {
    SILFunction *f = getCommonFunction(releasedPtr, livePtr);
    if (!f)
      return true;
  
    auto *conGraph = getConnectionGraph(f);
  
    CGNode *liveContentNode = conGraph->getValueContent(livePtr);
    if (!liveContentNode)
      return true;
  
    // Case #1: Unique livePtr whose content does not escape.
    //
    // If \p livePtr is an exclusive function argument, it may be indirectly
    // reachable via releasedPtr, but the exclusive argument must have it's own
    // reference count retained by the called. We consider \p livePtr unique since
    // it so cannot be freed via a release of \p releasedPtr within this function
    // or its callees.
    bool isLiveAddressUnique =
        isUniquelyIdentified(livePtr)
        && !liveContentNode->valueEscapesInsideFunction(livePtr);
  
    // Case #2: releasedPtr points to a local object.
    if (!isLiveAddressUnique && !pointsToLocalObject(releasedPtr))
      return true;
  
    // If \p releasedPtr is an address, then its released content is at least two
    // levels away: the address points to a reference, which points to an object.
    // CGNode *releasedObjNode = nullptr;
    CGNode *releasedObjNode = nullptr;
    if (releasedPtr->getType().isAddress()) {
      CGNode *addrContentObjNode = conGraph->getValueContent(releasedPtr);
      if (!addrContentObjNode)
        return true;
      releasedObjNode = conGraph->getOrCreateUnknownContent(addrContentObjNode);
    } else {
      releasedObjNode = conGraph->getValueContent(releasedPtr);
    }
    // Make sure we have at least one value CGNode for releasedReference.
    if (!releasedObjNode)
      return true;
  
    // Check for reachability from releasedObjNode to liveContentNode.
    // A pointsTo cycle is equivalent to a null pointsTo.
    CGNodeWorklist worklist(conGraph);
    for (CGNode *releasedNode = releasedObjNode;
         releasedNode && worklist.tryPush(releasedNode);
         releasedNode = releasedNode->getContentNodeOrNull()) {
      // A path exists from released content to accessed content.
      if (releasedNode == liveContentNode)
        return true;
  
      // A path exists to an escaping node.
      if (!isLiveAddressUnique && releasedNode->escapesInsideFunction())
        return true;
    }
    return false; // no path to escaping memory that may be freed.
  }
  
  void EscapeAnalysis::invalidate() {
    Function2Info.clear();
    Allocator.DestroyAll();
    LLVM_DEBUG(llvm::dbgs() << "invalidate all\n");
  }
  
  void EscapeAnalysis::invalidate(SILFunction *F, InvalidationKind K) {
    if (FunctionInfo *FInfo = Function2Info.lookup(F)) {
      LLVM_DEBUG(llvm::dbgs() << "  invalidate "
                              << FInfo->Graph.F->getName() << '\n');
      invalidateIncludingAllCallers(FInfo);
    }
  }
  
  void EscapeAnalysis::verify() const {
  #ifndef NDEBUG
    for (auto Iter : Function2Info) {
      FunctionInfo *FInfo = Iter.second;
      FInfo->Graph.verify();
      FInfo->SummaryGraph.verifyStructure();
    }
  #endif
  }
  
  void EscapeAnalysis::verify(SILFunction *F) const {
  #ifndef NDEBUG
    if (FunctionInfo *FInfo = Function2Info.lookup(F)) {
      FInfo->Graph.verify();
      FInfo->SummaryGraph.verifyStructure();
    }
  #endif
  }
  
  SILAnalysis *swift::createEscapeAnalysis(SILModule *M) {
    return new EscapeAnalysis(M);
  }
  