text: //===--- OptRemarkGenerator.cpp -------------------------------------------===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2020 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
  //
  //===----------------------------------------------------------------------===//
  ///
  /// \file
  ///
  /// In this pass, we define the opt-remark-generator, a simple SILVisitor that
  /// attempts to infer opt-remarks for the user using heuristics.
  ///
  //===----------------------------------------------------------------------===//
  
  #define DEBUG_TYPE "sil-opt-remark-gen"
  
  #include "swift/Basic/Defer.h"
  #include "swift/AST/SemanticAttrs.h"
  #include "swift/SIL/MemAccessUtils.h"
  #include "swift/SIL/OptimizationRemark.h"
  #include "swift/SIL/Projection.h"
  #include "swift/SIL/SILFunction.h"
  #include "swift/SIL/SILInstruction.h"
  #include "swift/SIL/SILModule.h"
  #include "swift/SIL/SILVisitor.h"
  #include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
  #include "swift/SILOptimizer/PassManager/Passes.h"
  #include "swift/SILOptimizer/PassManager/Transforms.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/raw_ostream.h"
  
  using namespace swift;
  
  static llvm::cl::opt<bool> ForceVisitImplicitAutogeneratedFunctions(
      "optremarkgen-visit-implicit-autogen-funcs", llvm::cl::Hidden,
      llvm::cl::desc(
          "Emit opt remarks even on implicit and autogenerated functions"),
      llvm::cl::init(false));
  
  static llvm::cl::opt<bool> DecllessDebugValueUseSILDebugInfo(
      "optremarkgen-declless-debugvalue-use-sildebugvar-info", llvm::cl::Hidden,
      llvm::cl::desc(
          "If a debug_value does not have a decl, infer a value with a name from "
          "that info that has a loc set to the loc of the debug_value "
          "instruction itself. This is for testing purposes so it is easier to "
          "write SIL test cases for this pass"),
      llvm::cl::init(false));
  
  //===----------------------------------------------------------------------===//
  //                           Value To Decl Inferrer
  //===----------------------------------------------------------------------===//
  
  namespace {
  
  struct ValueToDeclInferrer {
    using Argument = OptRemark::Argument;
    using ArgumentKeyKind = OptRemark::ArgumentKeyKind;
  
    RCIdentityFunctionInfo &rcfi;
    SmallVector<std::pair<SILType, Projection>, 32> accessPath;
    SmallVector<Operand *, 32> rcIdenticalSecondaryUseSearch;
  
    ValueToDeclInferrer(RCIdentityFunctionInfo &rcfi) : rcfi(rcfi) {}
  
    /// Given a value, attempt to infer a conservative list of decls that the
    /// passed in value could be referring to. This is done just using heuristics
    bool infer(ArgumentKeyKind keyKind, SILValue value,
               SmallVectorImpl<Argument> &resultingInferredDecls);
  
    /// Print out a note to \p stream that beings at decl and then if
    /// useProjectionPath is set to true iterates the accessPath we computed for
    /// decl producing a segmented access path, e.x.: "of 'x.lhs.ivar'".
    ///
    /// The reason why one may not want to emit a projection path note here is if
    /// one found an debug_value on a value that is rc-identical to the actual
    /// value associated with the current projection path. Consider the following
    /// SIL:
    ///
    ///    struct KlassPair {
    ///      var lhs: Klass
    ///      var rhs: Klass
    ///    }
    ///
    ///    struct StateWithOwningPointer {
    ///      var state: TrivialState
    ///      var owningPtr: Klass
    ///    }
    ///
    ///    sil @theFunction : $@convention(thin) () -> () {
    ///    bb0:
    ///      %0 = apply %getKlassPair() : $@convention(thin) () -> @owned KlassPair
    ///      // This debug_value's name can be combined...
    ///      debug_value %0 : $KlassPair, name "myPair"
    ///      // ... with the access path from the struct_extract here...
    ///      %1 = struct_extract %0 : $KlassPair, #KlassPair.lhs
    ///      // ... to emit a nice diagnostic that 'myPair.lhs' is being retained.
    ///      strong_retain %1 : $Klass
    ///
    ///      // In contrast in this case, we rely on looking through rc-identity
    ///      // uses to find the debug_value. In this case, the source info
    ///      // associated with the debug_value (%2) is no longer associated with
    ///      // the underlying access path we have been tracking upwards (%1 is in
    ///      // our access path list). Instead, we know that the debug_value is
    ///      // rc-identical to whatever value we were originally tracking up (%1)
    ///      // and thus the correct identifier to use is the direct name of the
    ///      // identifier alone since that source identifier must be some value
    ///      // in the source that by itself is rc-identical to whatever is being
    ///      // manipulated.
    ///      //
    ///      // The reason why we must do this is due to the behavior of the late
    ///      // optimizer and how it forms these patterns in the code.
    ///      %0a = apply %getStateWithOwningPointer() : $@convention(thin) () -> @owned StateWithOwningPointer
    ///      %1 = struct_extract %0a : $StateWithOwningPointer, #StateWithOwningPointer.owningPtr
    ///      strong_retain %1 : $Klass
    ///      %2 = struct $Array(%0 : $Builtin.NativeObject, ...)
    ///      debug_value %2 : $Array, ...
    ///    }
    void printNote(llvm::raw_string_ostream &stream, StringRef name,
                   bool shouldPrintAccessPath = true);
  
    /// Convenience overload that calls:
    ///
    ///   printNote(stream, decl->getBaseName().userFacingName(), shouldPrintAccessPath).
    void printNote(llvm::raw_string_ostream &stream, const ValueDecl *decl,
                   bool shouldPrintAccessPath = true) {
      printNote(stream, decl->getBaseName().userFacingName(),
                shouldPrintAccessPath);
    }
  
    /// Print out non-destructively the current access path we have found to
    /// stream.
    void printAccessPath(llvm::raw_string_ostream &stream);
  };
  
  } // anonymous namespace
  
  void ValueToDeclInferrer::printAccessPath(llvm::raw_string_ostream &stream) {
    for (auto &pair : accessPath) {
      auto baseType = pair.first;
      auto &proj = pair.second;
      stream << ".";
  
      // WARNING: This must be kept insync with isSupportedProjection!
      switch (proj.getKind()) {
      case ProjectionKind::Upcast:
        stream << "upcast<" << proj.getCastType(baseType) << ">";
        continue;
      case ProjectionKind::RefCast:
        stream << "refcast<" << proj.getCastType(baseType) << ">";
        continue;
      case ProjectionKind::BitwiseCast:
        stream << "bitwise_cast<" << proj.getCastType(baseType) << ">";
        continue;
      case ProjectionKind::Struct:
        stream << proj.getVarDecl(baseType)->getBaseName();
        continue;
      case ProjectionKind::Tuple:
        stream << proj.getIndex();
        continue;
      case ProjectionKind::Enum:
        stream << proj.getEnumElementDecl(baseType)->getBaseName();
        continue;
      // Object -> Address projections can never be looked through.
      case ProjectionKind::Class:
      case ProjectionKind::Box:
      case ProjectionKind::Index:
      case ProjectionKind::TailElems:
        llvm_unreachable(
            "Object -> Address projection should never be looked through!");
      }
  
      llvm_unreachable("Covered switch is not covered?!");
    }
  }
  
  void ValueToDeclInferrer::printNote(llvm::raw_string_ostream &stream,
                                      StringRef name,
                                      bool shouldPrintAccessPath) {
    stream << "of '" << name;
    if (shouldPrintAccessPath)
      printAccessPath(stream);
    stream << "'";
  }
  
  // WARNING: This must be kept insync with ValueToDeclInferrer::printNote(...).
  static SingleValueInstruction *isSupportedProjection(Projection p, SILValue v) {
    switch (p.getKind()) {
    case ProjectionKind::Upcast:
    case ProjectionKind::RefCast:
    case ProjectionKind::BitwiseCast:
    case ProjectionKind::Struct:
    case ProjectionKind::Tuple:
    case ProjectionKind::Enum:
      return cast<SingleValueInstruction>(v);
      // Object -> Address projections can never be looked through.
    case ProjectionKind::Class:
    case ProjectionKind::Box:
    case ProjectionKind::Index:
    case ProjectionKind::TailElems:
      return nullptr;
    }
    llvm_unreachable("Covered switch is not covered?!");
  }
  
  static bool hasNonInlinedDebugScope(SILInstruction *i) {
    if (auto *scope = i->getDebugScope())
      return !scope->InlinedCallSite;
    return false;
  }
  
  bool ValueToDeclInferrer::infer(
      ArgumentKeyKind keyKind, SILValue value,
      SmallVectorImpl<Argument> &resultingInferredDecls) {
    // Clear the stored access path at end of scope.
    SWIFT_DEFER {
      accessPath.clear();
    };
    SmallPtrSet<SILInstruction *, 8> visitedDebugValueInsts;
  
    // This is a linear IR traversal using a 'falling while loop'. That means
    // every time through the loop we are trying to handle a case before we hit
    // the bottom of the while loop where we always return true (since we did not
    // hit a could not compute case). Reassign value and continue to go to the
    // next step.
    while (true) {
      // First check for "identified values" like arguments and global_addr.
      if (auto *arg = dyn_cast<SILArgument>(value))
        if (auto *decl = arg->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            printNote(stream, decl);
          }
          resultingInferredDecls.push_back(
              Argument({keyKind, "InferredValue"}, std::move(msg), decl));
          return true;
        }
  
      if (auto *ga = dyn_cast<GlobalAddrInst>(value))
        if (auto *decl = ga->getReferencedGlobal()->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            printNote(stream, decl);
          }
          resultingInferredDecls.push_back(
              Argument({keyKind, "InferredValue"}, std::move(msg), decl));
          return true;
        }
  
      if (auto *ari = dyn_cast<AllocRefInst>(value)) {
        if (auto *decl = ari->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            printNote(stream, decl);
          }
          resultingInferredDecls.push_back(
              Argument({keyKind, "InferredValue"}, std::move(msg), decl));
          return true;
        }
      }
  
      if (auto *abi = dyn_cast<AllocBoxInst>(value)) {
        if (auto *decl = abi->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            printNote(stream, decl);
          }
  
          resultingInferredDecls.push_back(
              Argument({keyKind, "InferredValue"}, std::move(msg), decl));
          return true;
        }
      }
  
      if (auto *asi = dyn_cast<AllocStackInst>(value)) {
        if (auto *decl = asi->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            printNote(stream, decl);
          }
          resultingInferredDecls.push_back(
              Argument({keyKind, "InferredValue"}, std::move(msg), decl));
          return true;
        }
      }
  
      // Then visit our users (ignoring rc identical transformations) and see if
      // we can find a debug_value that provides us with a decl we can use to
      // construct an argument.
      //
      // The reason why we do this is that sometimes we reform a struct from its
      // constituant parts and then construct the debug_value from that. For
      // instance, if we FSOed.
      bool foundDeclFromUse = false;
      rcfi.visitRCUses(value, [&](Operand *use) {
        // Skip type dependent uses.
        if (use->isTypeDependent())
          return;
  
        // Then see if we have a debug_value that is associated with a non-inlined
        // debug scope. Such an instruction is an instruction that is from the
        // current function.
        auto *dvi = dyn_cast<DebugValueInst>(use->getUser());
        if (!dvi || !hasNonInlinedDebugScope(dvi))
          return;
  
        // See if we have already inferred this debug_value as a potential source
        // for this instruction. In such a case, just return.
        if (!visitedDebugValueInsts.insert(dvi).second)
          return;
  
        if (auto *decl = dvi->getDecl()) {
          std::string msg;
          {
            llvm::raw_string_ostream stream(msg);
            // If we are not a top level use, we must be a rc-identical transitive
            // use. In such a case, we just print out the rc identical value
            // without a projection path. This is because we now have a better
            // name and the name is rc-identical to whatever was at the end of the
            // projection path but is not at the end of that projection path.
            printNote(stream, decl,
                      use->get() == value /*print projection path*/);
          }
          resultingInferredDecls.emplace_back(
              OptRemark::ArgumentKey{keyKind, "InferredValue"}, std::move(msg),
              decl);
          foundDeclFromUse = true;
          return;
        }
  
        // If we did not have a decl, see if we were asked for testing
        // purposes to use SILDebugInfo to create a placeholder inferred
        // value.
        if (!DecllessDebugValueUseSILDebugInfo)
          return;
  
        auto varInfo = dvi->getVarInfo();
        if (!varInfo)
          return;
  
        auto name = varInfo->Name;
        if (name.empty())
          return;
  
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, name, use->get() == value /*print projection path*/);
        }
        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), dvi->getLoc()));
        foundDeclFromUse = true;
      });
  
      // At this point, we could not infer any argument. See if we can look up the
      // def-use graph and come up with a good location after looking through
      // loads and projections.
      if (auto *li = dyn_cast<LoadInst>(value)) {
        value = stripAccessMarkers(li->getOperand());
        continue;
      }
  
      if (auto proj = Projection(value)) {
        if (auto *projInst = isSupportedProjection(proj, value)) {
          value = projInst->getOperand(0);
          accessPath.emplace_back(value->getType(), proj);
          continue;
        }
      }
  
      // TODO: We could emit at this point a msg for temporary allocations.
  
      // If we reached this point, we finished falling through the loop and return
      // if we found any decls from uses. We always process everything so we /can/
      // potentially emit multiple diagnostics.
      return foundDeclFromUse;
    }
  }
  
  //===----------------------------------------------------------------------===//
  //                        Opt Remark Generator Visitor
  //===----------------------------------------------------------------------===//
  
  namespace {
  
  struct OptRemarkGeneratorInstructionVisitor
      : public SILInstructionVisitor<OptRemarkGeneratorInstructionVisitor> {
    SILModule &mod;
    OptRemark::Emitter ORE;
  
    /// A class that we use to infer the decl that is associated with a
    /// miscellaneous SIL value. This is just a heuristic that is to taste.
    ValueToDeclInferrer valueToDeclInferrer;
  
    OptRemarkGeneratorInstructionVisitor(SILFunction &fn,
                                         RCIdentityFunctionInfo &rcfi)
        : mod(fn.getModule()), ORE(DEBUG_TYPE, fn), valueToDeclInferrer(rcfi) {}
  
    void visitStrongRetainInst(StrongRetainInst *sri);
    void visitStrongReleaseInst(StrongReleaseInst *sri);
    void visitRetainValueInst(RetainValueInst *rvi);
    void visitReleaseValueInst(ReleaseValueInst *rvi);
    void visitAllocRefInst(AllocRefInst *ari);
    void visitAllocBoxInst(AllocBoxInst *abi);
    void visitSILInstruction(SILInstruction *) {}
  };
  
  } // anonymous namespace
  
  void OptRemarkGeneratorInstructionVisitor::visitStrongRetainInst(
      StrongRetainInst *sri) {
    ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                                 sri->getOperand(), inferredArgs);
      (void)foundArgs;
  
      // Retains begin a lifetime scope so we infer scan forward.
      auto remark =
          RemarkMissed("memory", *sri,
                       SourceLocInferenceBehavior::ForwardScanAlwaysInfer)
          << "retain of type '" << NV("ValueType", sri->getOperand()->getType())
          << "'";
      for (auto arg : inferredArgs) {
        remark << arg;
      }
      return remark;
    });
  }
  
  void OptRemarkGeneratorInstructionVisitor::visitStrongReleaseInst(
      StrongReleaseInst *sri) {
    ORE.emit([&]() {
      using namespace OptRemark;
      // Releases end a lifetime scope so we infer scan backward.
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                                 sri->getOperand(), inferredArgs);
      (void)foundArgs;
  
      auto remark =
          RemarkMissed("memory", *sri,
                       SourceLocInferenceBehavior::BackwardScanAlwaysInfer)
          << "release of type '" << NV("ValueType", sri->getOperand()->getType())
          << "'";
      for (auto arg : inferredArgs) {
        remark << arg;
      }
      return remark;
    });
  }
  
  void OptRemarkGeneratorInstructionVisitor::visitRetainValueInst(
      RetainValueInst *rvi) {
    ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                                 rvi->getOperand(), inferredArgs);
      (void)foundArgs;
      // Retains begin a lifetime scope, so we infer scan forwards.
      auto remark =
          RemarkMissed("memory", *rvi,
                       SourceLocInferenceBehavior::ForwardScanAlwaysInfer)
          << "retain of type '" << NV("ValueType", rvi->getOperand()->getType())
          << "'";
      for (auto arg : inferredArgs) {
        remark << arg;
      }
      return remark;
    });
  }
  
  void OptRemarkGeneratorInstructionVisitor::visitReleaseValueInst(
      ReleaseValueInst *rvi) {
    ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                                 rvi->getOperand(), inferredArgs);
      (void)foundArgs;
  
      // Releases end a lifetime scope so we infer scan backward.
      auto remark =
          RemarkMissed("memory", *rvi,
                       SourceLocInferenceBehavior::BackwardScanAlwaysInfer)
          << "release of type '" << NV("ValueType", rvi->getOperand()->getType())
          << "'";
      for (auto arg : inferredArgs) {
        remark << arg;
      }
      return remark;
    });
  }
  
  void OptRemarkGeneratorInstructionVisitor::visitAllocRefInst(
      AllocRefInst *ari) {
    if (ari->canAllocOnStack()) {
      return ORE.emit([&]() {
        using namespace OptRemark;
        SmallVector<Argument, 8> inferredArgs;
        bool foundArgs =
            valueToDeclInferrer.infer(ArgumentKeyKind::Note, ari, inferredArgs);
        (void)foundArgs;
        auto resultRemark =
            RemarkPassed("memory", *ari, SourceLocInferenceBehavior::ForwardScan)
            << "stack allocated ref of type '" << NV("ValueType", ari->getType())
            << "'";
        for (auto &arg : inferredArgs)
          resultRemark << arg;
        return resultRemark;
      });
    }
  
    return ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs =
          valueToDeclInferrer.infer(ArgumentKeyKind::Note, ari, inferredArgs);
      (void)foundArgs;
  
      auto resultRemark =
          RemarkMissed("memory", *ari, SourceLocInferenceBehavior::ForwardScan)
          << "heap allocated ref of type '" << NV("ValueType", ari->getType())
          << "'";
      for (auto &arg : inferredArgs)
        resultRemark << arg;
      return resultRemark;
    });
  }
  
  void OptRemarkGeneratorInstructionVisitor::visitAllocBoxInst(
      AllocBoxInst *abi) {
    return ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs =
          valueToDeclInferrer.infer(ArgumentKeyKind::Note, abi, inferredArgs);
      (void)foundArgs;
  
      auto resultRemark =
          RemarkMissed("memory", *abi, SourceLocInferenceBehavior::ForwardScan)
          << "heap allocated box of type '" << NV("ValueType", abi->getType())
          << "'";
      for (auto &arg : inferredArgs)
        resultRemark << arg;
      return resultRemark;
    });
  }
  
  //===----------------------------------------------------------------------===//
  //                            Top Level Entrypoint
  //===----------------------------------------------------------------------===//
  
  namespace {
  
  class OptRemarkGenerator : public SILFunctionTransform {
    ~OptRemarkGenerator() override {}
  
    bool isOptRemarksEnabled() {
      auto *fn = getFunction();
      // TODO: Put this on LangOpts as a helper.
      auto &langOpts = fn->getASTContext().LangOpts;
  
      return bool(langOpts.OptimizationRemarkMissedPattern) ||
             bool(langOpts.OptimizationRemarkPassedPattern) ||
             fn->getModule().getSILRemarkStreamer() ||
             fn->hasSemanticsAttrThatStartsWith(
                 semantics::FORCE_EMIT_OPT_REMARK_PREFIX);
    }
  
    /// The entry point to the transformation.
    void run() override {
      if (!isOptRemarksEnabled())
        return;
  
      auto *fn = getFunction();
  
      // Skip top level implicit functions and top level autogenerated functions,
      // unless we were asked by the user to emit them.
      if (!ForceVisitImplicitAutogeneratedFunctions) {
        // Skip implicit functions generated by Sema.
        if (auto *ctx = fn->getDeclContext())
          if (auto *decl = ctx->getAsDecl())
            if (decl->isImplicit())
              return;
        // Skip autogenerated functions generated by SILGen.
        if (auto loc = fn->getDebugScope()->getLoc())
          if (loc.isAutoGenerated())
            return;
      }
  
      LLVM_DEBUG(llvm::dbgs() << "Visiting: " << fn->getName() << "\n");
      auto &rcfi = *getAnalysis<RCIdentityAnalysis>()->get(fn);
      OptRemarkGeneratorInstructionVisitor visitor(*fn, rcfi);
      for (auto &block : *fn) {
        for (auto &inst : block) {
          visitor.visit(&inst);
        }
      }
    }
  };
  
  } // end anonymous namespace
  
  SILTransform *swift::createOptRemarkGenerator() {
    return new OptRemarkGenerator();
  }
  