lib/SILOptimizer/Transforms/OptRemarkGenerator.cpp - third_party/swift - Git at Google

 //===--- 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/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();
 }
	//===--- 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/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();
	}