text: //===--- ARCMatchingSet.cpp - ARC Matching Set Builder --------------------===//
  //
  // 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 "arc-sequence-opts"
  
  #include "ARCMatchingSet.h"
  #include "RefCountState.h"
  #include "swift/Basic/BlotMapVector.h"
  #include "swift/SIL/SILBuilder.h"
  #include "swift/SIL/SILVisitor.h"
  #include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
  #include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
  #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
  #include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
  #include "swift/SILOptimizer/PassManager/Transforms.h"
  #include "swift/SILOptimizer/Utils/InstOptUtils.h"
  #include "llvm/ADT/MapVector.h"
  #include "llvm/ADT/PointerUnion.h"
  #include "llvm/ADT/SmallPtrSet.h"
  #include "llvm/ADT/Statistic.h"
  #include "llvm/ADT/StringSwitch.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/Debug.h"
  
  using namespace swift;
  
  //===----------------------------------------------------------------------===//
  //                          ARC Matching Set Builder
  //===----------------------------------------------------------------------===//
  
  /// Match retains to releases and return whether or not all of the releases
  /// were known safe.
  Optional<MatchingSetFlags>
  ARCMatchingSetBuilder::matchIncrementsToDecrements() {
    MatchingSetFlags Flags = {true, true};
  
    // For each increment in our list of new increments.
    //
    // FIXME: Refactor this into its own function.
    for (SILInstruction *Increment : NewIncrements) {
      LLVM_DEBUG(llvm::dbgs() << "    Looking up state for increment: "
                              << *Increment);
  
      auto BURefCountState = BUMap.find(Increment);
      assert(BURefCountState != BUMap.end() && "Catch this on debug builds.");
      if (BURefCountState == BUMap.end()) {
        LLVM_DEBUG(llvm::dbgs() << "        FAILURE! Could not find state for "
                                   "increment!\n");
        return None;
      }
  
      LLVM_DEBUG(llvm::dbgs() << "        SUCCESS! Found state for increment.\n");
  
      // If we are not tracking a ref count inst for this increment, there is
      // nothing we can pair it with implying we should skip it.
      if (!(*BURefCountState)->second.isTrackingRefCountInst()) {
        LLVM_DEBUG(llvm::dbgs() << "    SKIPPING INCREMENT! State not tracking "
                                   "any instruction.\n");
        continue;
      }
  
      bool BUIsKnownSafe = (*BURefCountState)->second.isKnownSafe();
      LLVM_DEBUG(llvm::dbgs() << "        BOTTOM UP KNOWNSAFE: "
                              << (BUIsKnownSafe ? "true" : "false") << "\n");
      Flags.KnownSafe &= BUIsKnownSafe;
  
      bool BUCodeMotionSafe = (*BURefCountState)->second.isCodeMotionSafe();
      LLVM_DEBUG(llvm::dbgs() << "        BOTTOM UP CODEMOTIONSAFE: "
                              << (BUCodeMotionSafe ? "true" : "false") << "\n");
      Flags.CodeMotionSafe &= BUCodeMotionSafe;
  
      // Now that we know we have an inst, grab the decrement.
      for (auto DecIter : (*BURefCountState)->second.getInstructions()) {
        SILInstruction *Decrement = DecIter;
        LLVM_DEBUG(llvm::dbgs() << "        Decrement: " << *Decrement);
  
        // Now grab the increment matched up with the decrement from the bottom up
        // map.
        // If we can't find it, bail we can't match this increment up with
        // anything.
        auto TDRefCountState = TDMap.find(Decrement);
        if (TDRefCountState == TDMap.end()) {
          LLVM_DEBUG(llvm::dbgs() << "            FAILURE! Could not find state "
                                     "for decrement.\n");
          return None;
        }
        LLVM_DEBUG(llvm::dbgs() << "            SUCCESS! Found state for "
                                   "decrement.\n");
  
        // Make sure the increment we are looking at is also matched to our
        // decrement. Otherwise bail.
        if (!(*TDRefCountState)->second.isTrackingRefCountInst() ||
            !(*TDRefCountState)->second.containsInstruction(Increment)) {
          LLVM_DEBUG(
              llvm::dbgs() << "            FAILURE! Not tracking instruction or "
                              "found increment that did not match.\n");
          return None;
        }
  
        // Add the decrement to the decrement to move set. If we don't insert
        // anything, just continue.
        if (!MatchSet.Decrements.insert(Decrement)) {
          LLVM_DEBUG(llvm::dbgs()
                     << "        SKIPPING! Already processed this decrement\n");
          continue;
        }
  
        NewDecrements.push_back(Decrement);
      }
    }
  
    return Flags;
  }
  
  Optional<MatchingSetFlags>
  ARCMatchingSetBuilder::matchDecrementsToIncrements() {
    MatchingSetFlags Flags = {true, true};
  
    // For each increment in our list of new increments.
    //
    // FIXME: Refactor this into its own function.
    for (SILInstruction *Decrement : NewDecrements) {
      LLVM_DEBUG(llvm::dbgs() << "    Looking up state for decrement: "
                              << *Decrement);
  
      auto TDRefCountState = TDMap.find(Decrement);
      assert(TDRefCountState != TDMap.end() && "Catch this on debug builds.");
      if (TDRefCountState == TDMap.end()) {
        LLVM_DEBUG(llvm::dbgs() << "        FAILURE! Could not find state for "
                                   "increment!\n");
        return None;
      }
  
      LLVM_DEBUG(llvm::dbgs() << "        SUCCESS! Found state for decrement.\n");
  
      // If we are not tracking a ref count inst for this increment, there is
      // nothing we can pair it with implying we should skip it.
      if (!(*TDRefCountState)->second.isTrackingRefCountInst()) {
        LLVM_DEBUG(llvm::dbgs() << "    SKIPPING DECREMENT! State not tracking "
                                   "any instruction.\n");
        continue;
      }
  
      bool TDIsKnownSafe = (*TDRefCountState)->second.isKnownSafe();
      LLVM_DEBUG(llvm::dbgs() << "        TOP DOWN KNOWNSAFE: "
                              << (TDIsKnownSafe ? "true" : "false") << "\n");
      Flags.KnownSafe &= TDIsKnownSafe;
  
      bool TDCodeMotionSafe = (*TDRefCountState)->second.isCodeMotionSafe();
      LLVM_DEBUG(llvm::dbgs() << "        TOP DOWN CODEMOTIONSAFE: "
                              << (TDCodeMotionSafe ? "true" : "false") << "\n");
      Flags.CodeMotionSafe &= TDCodeMotionSafe;
  
      // Now that we know we have an inst, grab the decrement.
      for (auto IncIter : (*TDRefCountState)->second.getInstructions()) {
        SILInstruction *Increment = IncIter;
        LLVM_DEBUG(llvm::dbgs() << "        Increment: " << *Increment);
  
        // Now grab the increment matched up with the decrement from the bottom up
        // map.
        // If we can't find it, bail we can't match this increment up with
        // anything.
        auto BURefCountState = BUMap.find(Increment);
        if (BURefCountState == BUMap.end()) {
          LLVM_DEBUG(llvm::dbgs() << "            FAILURE! Could not find state "
                                     "for increment.\n");
          return None;
        }
  
        LLVM_DEBUG(
            llvm::dbgs() << "            SUCCESS! Found state for increment.\n");
  
        // Make sure the increment we are looking at is also matched to our
        // decrement.
        // Otherwise bail.
        if (!(*BURefCountState)->second.isTrackingRefCountInst() ||
            !(*BURefCountState)->second.containsInstruction(Decrement)) {
          LLVM_DEBUG(
              llvm::dbgs() << "            FAILURE! Not tracking instruction or "
                              "found increment that did not match.\n");
          return None;
        }
  
        // Add the decrement to the decrement to move set. If we don't insert
        // anything, just continue.
        if (!MatchSet.Increments.insert(Increment)) {
          LLVM_DEBUG(llvm::dbgs()
                     << "    SKIPPING! Already processed this increment.\n");
          continue;
        }
  
        NewIncrements.push_back(Increment);
      }
    }
  
    return Flags;
  }
  
  /// Visit each retain/release that is matched up to our operand over and over
  /// again until we converge by not adding any more to the set which we can move.
  /// If we find a situation that we cannot handle, we bail and return false. If
  /// we succeed and it is safe to move increment/releases, we return true.
  bool ARCMatchingSetBuilder::matchUpIncDecSetsForPtr() {
    bool KnownSafeTD = true;
    bool KnownSafeBU = true;
    bool CodeMotionSafeTD = true;
    bool CodeMotionSafeBU = true;
  
    while (true) {
      LLVM_DEBUG(llvm::dbgs() << "Attempting to match up increments -> "
                 "decrements:\n");
      // For each increment in our list of new increments, attempt to match them
      // up with decrements.
      auto Result = matchIncrementsToDecrements();
      if (!Result) {
        LLVM_DEBUG(llvm::dbgs() << "    FAILED TO MATCH INCREMENTS -> "
                   "DECREMENTS!\n");
        return false;
      }
      if (!Result->KnownSafe) {
        LLVM_DEBUG(llvm::dbgs() << "    NOT KNOWN SAFE!\n");
        KnownSafeTD = false;
      }
      if (!Result->CodeMotionSafe) {
        LLVM_DEBUG(llvm::dbgs() << "    NOT CODE MOTION SAFE!\n");
        CodeMotionSafeTD = false;
      }
        
      NewIncrements.clear();
  
      // If we do not have any decrements to attempt to match up with, bail.
      if (NewDecrements.empty())
        break;
  
      LLVM_DEBUG(llvm::dbgs() << "Attempting to match up decrements -> "
                 "increments:\n");
      Result = matchDecrementsToIncrements();
      if (!Result) {
        LLVM_DEBUG(llvm::dbgs() << "    FAILED TO MATCH DECREMENTS -> "
                   "INCREMENTS!\n");
        return false;
      }
      if (!Result->KnownSafe) {
        LLVM_DEBUG(llvm::dbgs() << "    NOT KNOWN SAFE!\n");
        KnownSafeBU = false;
      }
      if (!Result->CodeMotionSafe) {
        LLVM_DEBUG(llvm::dbgs() << "    NOT CODE MOTION SAFE!\n");
        CodeMotionSafeBU = false;
      }
      NewDecrements.clear();
  
      // If we do not have any increment to attempt to match up with again, bail.
      if (NewIncrements.empty())
        break;
    }
  
    // There is no way we can get a top-down code motion but not a bottom-up, or vice
    // versa.
    assert(CodeMotionSafeTD == CodeMotionSafeBU && "Asymmetric code motion safety");
  
    bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU);
    bool CodeMotionSafe = (CodeMotionSafeTD && CodeMotionSafeBU);
    if (UnconditionallySafe || CodeMotionSafe) {
      LLVM_DEBUG(llvm::dbgs() << "UNCONDITIONALLY OR CODE MOTION SAFE! "
                 "DELETING INSTS.\n");
    } else {
      LLVM_DEBUG(llvm::dbgs() << "NOT UNCONDITIONALLY SAFE AND CODE MOTION "
                 "BLOCKED!\n");
      return false;
    }
  
    // Make sure we always have increments and decrements in the match set.
    assert(MatchSet.Increments.empty() == MatchSet.Decrements.empty() &&
           "Match set without increments or decrements");
  
    if (!MatchSet.Increments.empty())
      MatchedPair = true;
  
    // Success!
    LLVM_DEBUG(llvm::dbgs() << "SUCCESS! We can remove things.\n");
    return true;
  }
  