//===--- SILFunction.cpp - Defines the SILFunction data structure ---------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBasicBlock.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SIL/SILProfiler.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/PrettyStackTrace.h"
#include "swift/AST/GenericEnvironment.h"
#include "swift/Basic/OptimizationMode.h"
#include "swift/Basic/Statistic.h"
#include "llvm/ADT/Optional.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/GraphWriter.h"

using namespace swift;
using namespace Lowering;

ArrayRef<Requirement> SILSpecializeAttr::getRequirements() const {
  return {const_cast<SILSpecializeAttr *>(this)->getRequirementsData(),
          numRequirements};
}

SILSpecializeAttr::SILSpecializeAttr(ArrayRef<Requirement> requirements,
                                     bool exported, SpecializationKind kind)
    : numRequirements(requirements.size()), kind(kind), exported(exported) {
  std::copy(requirements.begin(), requirements.end(), getRequirementsData());
}

SILSpecializeAttr *SILSpecializeAttr::create(SILModule &M,
                                             ArrayRef<Requirement> requirements,
                                             bool exported,
                                             SpecializationKind kind) {
  unsigned size =
      sizeof(SILSpecializeAttr) + sizeof(Requirement) * requirements.size();
  void *buf = M.allocate(size, alignof(SILSpecializeAttr));
  return ::new (buf) SILSpecializeAttr(requirements, exported, kind);
}

void SILFunction::addSpecializeAttr(SILSpecializeAttr *Attr) {
  if (getLoweredFunctionType()->getGenericSignature()) {
    Attr->F = this;
    SpecializeAttrSet.push_back(Attr);
  }
}

SILFunction *SILFunction::create(
    SILModule &M, SILLinkage linkage, StringRef name,
    CanSILFunctionType loweredType, GenericEnvironment *genericEnv,
    Optional<SILLocation> loc, IsBare_t isBareSILFunction,
    IsTransparent_t isTrans, IsSerialized_t isSerialized,
    ProfileCounter entryCount, IsThunk_t isThunk,
    SubclassScope classSubclassScope, Inline_t inlineStrategy, EffectsKind E,
    SILFunction *insertBefore, const SILDebugScope *debugScope) {
  // Get a StringMapEntry for the function.  As a sop to error cases,
  // allow the name to have an empty string.
  llvm::StringMapEntry<SILFunction*> *entry = nullptr;
  if (!name.empty()) {
    entry = &*M.FunctionTable.insert(std::make_pair(name, nullptr)).first;
    PrettyStackTraceSILFunction trace("creating", entry->getValue());
    assert(!entry->getValue() && "function already exists");
    name = entry->getKey();
  }

  auto fn = new (M) SILFunction(M, linkage, name, loweredType, genericEnv, loc,
                                isBareSILFunction, isTrans, isSerialized,
                                entryCount, isThunk, classSubclassScope,
                                inlineStrategy, E, insertBefore, debugScope);

  if (entry) entry->setValue(fn);
  return fn;
}

SILFunction::SILFunction(SILModule &Module, SILLinkage Linkage, StringRef Name,
                         CanSILFunctionType LoweredType,
                         GenericEnvironment *genericEnv,
                         Optional<SILLocation> Loc, IsBare_t isBareSILFunction,
                         IsTransparent_t isTrans, IsSerialized_t isSerialized,
                         ProfileCounter entryCount, IsThunk_t isThunk,
                         SubclassScope classSubclassScope,
                         Inline_t inlineStrategy, EffectsKind E,
                         SILFunction *InsertBefore,
                         const SILDebugScope *DebugScope)
    : Module(Module), Name(Name), LoweredType(LoweredType),
      GenericEnv(genericEnv), SpecializationInfo(nullptr),
      DebugScope(DebugScope), Bare(isBareSILFunction), Transparent(isTrans),
      Serialized(isSerialized), Thunk(isThunk),
      ClassSubclassScope(unsigned(classSubclassScope)), GlobalInitFlag(false),
      InlineStrategy(inlineStrategy), Linkage(unsigned(Linkage)),
      HasCReferences(false), IsWeakLinked(false),
      OptMode(OptimizationMode::NotSet), EffectsKindAttr(E),
      EntryCount(entryCount) {
  if (InsertBefore)
    Module.functions.insert(SILModule::iterator(InsertBefore), this);
  else
    Module.functions.push_back(this);

  Module.removeFromZombieList(Name);

  // Set our BB list to have this function as its parent. This enables us to
  // splice efficiently basic blocks in between functions.
  BlockList.Parent = this;
}

SILFunction::~SILFunction() {
  // If the function is recursive, a function_ref inst inside of the function
  // will give the function a non-zero ref count triggering the assertion. Thus
  // we drop all instruction references before we erase.
  // We also need to drop all references if instructions are allocated using
  // an allocator that may recycle freed memory.
  dropAllReferences();

  auto &M = getModule();
  for (auto &BB : *this) {
    for (auto I = BB.begin(), E = BB.end(); I != E;) {
      auto Inst = &*I;
      ++I;
      SILInstruction::destroy(Inst);
      // TODO: It is only safe to directly deallocate an
      // instruction if this BB is being removed in scope
      // of destructing a SILFunction.
      M.deallocateInst(Inst);
    }
    BB.InstList.clearAndLeakNodesUnsafely();
  }

  assert(RefCount == 0 &&
         "Function cannot be deleted while function_ref's still exist");
}

void SILFunction::createProfiler(ASTNode Root, ForDefinition_t forDefinition) {
  assert(!Profiler && "Function already has a profiler");
  Profiler = SILProfiler::create(Module, forDefinition, Root);
}

bool SILFunction::hasForeignBody() const {
  if (!hasClangNode()) return false;
  return SILDeclRef::isClangGenerated(getClangNode());
}

void SILFunction::numberValues(llvm::DenseMap<const SILNode*, unsigned> &
                                 ValueToNumberMap) const {
  unsigned idx = 0;
  for (auto &BB : *this) {
    for (auto I = BB.args_begin(), E = BB.args_end(); I != E; ++I)
      ValueToNumberMap[*I] = idx++;
    
    for (auto &I : BB) {
      auto results = I.getResults();
      if (results.empty()) {
        ValueToNumberMap[&I] = idx++;
      } else {
        // Assign the instruction node the first result ID.
        ValueToNumberMap[&I] = idx;
        for (auto result : results) {
          ValueToNumberMap[result] = idx++;
        }
      }
    }
  }
}


ASTContext &SILFunction::getASTContext() const {
  return getModule().getASTContext();
}

OptimizationMode SILFunction::getEffectiveOptimizationMode() const {
  if (OptMode != OptimizationMode::NotSet)
    return OptMode;

  return getModule().getOptions().OptMode;
}

bool SILFunction::shouldOptimize() const {
  return getEffectiveOptimizationMode() != OptimizationMode::NoOptimization;
}

Type SILFunction::mapTypeIntoContext(Type type) const {
  return GenericEnvironment::mapTypeIntoContext(
      getGenericEnvironment(), type);
}

SILType SILFunction::mapTypeIntoContext(SILType type) const {
  if (auto *genericEnv = getGenericEnvironment())
    return genericEnv->mapTypeIntoContext(getModule(), type);
  return type;
}

SILType GenericEnvironment::mapTypeIntoContext(SILModule &M,
                                               SILType type) const {
  assert(!type.hasArchetype());

  auto genericSig = getGenericSignature()->getCanonicalSignature();
  return type.subst(M,
                    QueryInterfaceTypeSubstitutions(this),
                    LookUpConformanceInSignature(*genericSig),
                    genericSig);
}

bool SILFunction::isNoReturnFunction() const {
  return SILType::getPrimitiveObjectType(getLoweredFunctionType())
      .isNoReturnFunction();
}

SILBasicBlock *SILFunction::createBasicBlock() {
  return new (getModule()) SILBasicBlock(this);
}

SILBasicBlock *SILFunction::createBasicBlock(SILBasicBlock *AfterBlock) {
  return new (getModule()) SILBasicBlock(this, AfterBlock);
}

//===----------------------------------------------------------------------===//
//                          View CFG Implementation
//===----------------------------------------------------------------------===//

#ifndef NDEBUG

static llvm::cl::opt<unsigned>
MaxColumns("view-cfg-max-columns", llvm::cl::init(80),
           llvm::cl::desc("Maximum width of a printed node"));

namespace {
enum class LongLineBehavior { None, Truncate, Wrap };
} // end anonymous namespace
static llvm::cl::opt<LongLineBehavior>
LLBehavior("view-cfg-long-line-behavior",
           llvm::cl::init(LongLineBehavior::Truncate),
           llvm::cl::desc("Behavior when line width is greater than the "
                          "value provided my -view-cfg-max-columns "
                          "option"),
           llvm::cl::values(
               clEnumValN(LongLineBehavior::None, "none", "Print everything"),
               clEnumValN(LongLineBehavior::Truncate, "truncate",
                          "Truncate long lines"),
               clEnumValN(LongLineBehavior::Wrap, "wrap", "Wrap long lines")));

static llvm::cl::opt<bool>
RemoveUseListComments("view-cfg-remove-use-list-comments",
                      llvm::cl::init(false),
                      llvm::cl::desc("Should use list comments be removed"));

template <typename InstTy, typename CaseValueTy>
inline CaseValueTy getCaseValueForBB(const InstTy *Inst,
                                     const SILBasicBlock *BB) {
  for (unsigned i = 0, e = Inst->getNumCases(); i != e; ++i) {
    auto P = Inst->getCase(i);
    if (P.second != BB)
      continue;
    return P.first;
  }
  llvm_unreachable("Error! should never pass in BB that is not a successor");
}

namespace llvm {
template <>
struct DOTGraphTraits<SILFunction *> : public DefaultDOTGraphTraits {

  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}

  static std::string getGraphName(SILFunction *F) {
    return "CFG for '" + F->getName().str() + "' function";
  }

  static std::string getSimpleNodeLabel(SILBasicBlock *Node, SILFunction *F) {
    std::string OutStr;
    raw_string_ostream OSS(OutStr);
    const_cast<SILBasicBlock *>(Node)->printAsOperand(OSS, false);
    return OSS.str();
  }

  static std::string getCompleteNodeLabel(SILBasicBlock *Node, SILFunction *F) {
    std::string Str;
    raw_string_ostream OS(Str);

    OS << *Node;
    std::string OutStr = OS.str();
    if (OutStr[0] == '\n')
      OutStr.erase(OutStr.begin());

    // Process string output to make it nicer...
    unsigned ColNum = 0;
    unsigned LastSpace = 0;
    for (unsigned i = 0; i != OutStr.length(); ++i) {
      if (OutStr[i] == '\n') { // Left justify
        OutStr[i] = '\\';
        OutStr.insert(OutStr.begin() + i + 1, 'l');
        ColNum = 0;
        LastSpace = 0;
      } else if (RemoveUseListComments && OutStr[i] == '/' &&
                 i != (OutStr.size() - 1) && OutStr[i + 1] == '/') {
        unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
        OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx);
        --i;

      } else if (ColNum == MaxColumns) { // Handle long lines.

        if (LLBehavior == LongLineBehavior::Wrap) {
          if (!LastSpace)
            LastSpace = i;
          OutStr.insert(LastSpace, "\\l...");
          ColNum = i - LastSpace;
          LastSpace = 0;
          i += 3; // The loop will advance 'i' again.
        } else if (LLBehavior == LongLineBehavior::Truncate) {
          unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
          OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx);
          --i;
        }

        // Else keep trying to find a space.
      } else
        ++ColNum;
      if (OutStr[i] == ' ')
        LastSpace = i;
    }
    return OutStr;
  }

  std::string getNodeLabel(SILBasicBlock *Node, SILFunction *Graph) {
    if (isSimple())
      return getSimpleNodeLabel(Node, Graph);
    else
      return getCompleteNodeLabel(Node, Graph);
  }

  static std::string getEdgeSourceLabel(SILBasicBlock *Node,
                                        SILBasicBlock::succblock_iterator I) {
    const SILBasicBlock *Succ = *I;
    const TermInst *Term = Node->getTerminator();

    // Label source of conditional branches with "T" or "F"
    if (auto *CBI = dyn_cast<CondBranchInst>(Term))
      return (Succ == CBI->getTrueBB()) ? "T" : "F";

    // Label source of switch edges with the associated value.
    if (auto *SI = dyn_cast<SwitchValueInst>(Term)) {
      if (SI->hasDefault() && SI->getDefaultBB() == Succ)
        return "def";

      std::string Str;
      raw_string_ostream OS(Str);

      SILValue I = getCaseValueForBB<SwitchValueInst, SILValue>(SI, Succ);
      OS << I; // TODO: or should we output the literal value of I?
      return OS.str();
    }

    if (auto *SEIB = dyn_cast<SwitchEnumInst>(Term)) {
      std::string Str;
      raw_string_ostream OS(Str);

      EnumElementDecl *E =
          getCaseValueForBB<SwitchEnumInst, EnumElementDecl *>(SEIB, Succ);
      OS << E->getFullName();
      return OS.str();
    }

    if (auto *SEIB = dyn_cast<SwitchEnumAddrInst>(Term)) {
      std::string Str;
      raw_string_ostream OS(Str);

      EnumElementDecl *E =
          getCaseValueForBB<SwitchEnumAddrInst, EnumElementDecl *>(SEIB, Succ);
      OS << E->getFullName();
      return OS.str();
    }

    if (auto *DMBI = dyn_cast<DynamicMethodBranchInst>(Term))
      return (Succ == DMBI->getHasMethodBB()) ? "T" : "F";

    if (auto *CCBI = dyn_cast<CheckedCastBranchInst>(Term))
      return (Succ == CCBI->getSuccessBB()) ? "T" : "F";

    if (auto *CCBI = dyn_cast<CheckedCastValueBranchInst>(Term))
      return (Succ == CCBI->getSuccessBB()) ? "T" : "F";

    if (auto *CCBI = dyn_cast<CheckedCastAddrBranchInst>(Term))
      return (Succ == CCBI->getSuccessBB()) ? "T" : "F";

    return "";
  }
};
} // namespace llvm
#endif

#ifndef NDEBUG
static llvm::cl::opt<std::string>
TargetFunction("view-cfg-only-for-function", llvm::cl::init(""),
               llvm::cl::desc("Only print out the cfg for this function"));
#endif


void SILFunction::viewCFG() const {
/// When asserts are disabled, this should be a NoOp.
#ifndef NDEBUG
    // If we have a target function, only print that function out.
    if (!TargetFunction.empty() && !(getName().str() == TargetFunction))
      return;

  ViewGraph(const_cast<SILFunction *>(this), "cfg" + getName().str());
#endif
}

bool SILFunction::hasSelfMetadataParam() const {
  auto paramTypes = getConventions().getParameterSILTypes();
  if (paramTypes.empty())
    return false;

  auto silTy = *std::prev(paramTypes.end());
  if (!silTy.isObject())
    return false;

  auto selfTy = silTy.getASTType();

  if (auto metaTy = dyn_cast<MetatypeType>(selfTy)) {
    selfTy = metaTy.getInstanceType();
    if (auto dynamicSelfTy = dyn_cast<DynamicSelfType>(selfTy))
      selfTy = dynamicSelfTy.getSelfType();
  }

  return !!selfTy.getClassOrBoundGenericClass();
}

bool SILFunction::hasName(const char *Name) const {
  return getName() == Name;
}

/// Returns true if this function can be referenced from a fragile function
/// body.
bool SILFunction::hasValidLinkageForFragileRef() const {
  // Fragile functions can reference 'static inline' functions imported
  // from C.
  if (hasForeignBody())
    return true;

  // If we can inline it, we can reference it.
  if (hasValidLinkageForFragileInline())
    return true;

  // If the containing module has been serialized
  if (getModule().isSerialized()) {
    return true;
  }

  // Otherwise, only public functions can be referenced.
  return hasPublicVisibility(getLinkage());
}

bool
SILFunction::isPossiblyUsedExternally() const {
  auto linkage = getLinkage();

  // Hidden functions may be referenced by other C code in the linkage unit.
  if (linkage == SILLinkage::Hidden && hasCReferences())
    return true;

  return swift::isPossiblyUsedExternally(linkage, getModule().isWholeModule());
}

bool SILFunction::isExternallyUsedSymbol() const {
  return swift::isPossiblyUsedExternally(getEffectiveSymbolLinkage(),
                                         getModule().isWholeModule());
}

void SILFunction::convertToDeclaration() {
  assert(isDefinition() && "Can only convert definitions to declarations");
  dropAllReferences();
  getBlocks().clear();
}

SubstitutionMap SILFunction::getForwardingSubstitutionMap() {
  if (ForwardingSubMap)
    return ForwardingSubMap;

  if (auto *env = getGenericEnvironment())
    ForwardingSubMap = env->getForwardingSubstitutionMap();

  return ForwardingSubMap;
}

bool SILFunction::shouldVerifyOwnership() const {
  return !hasSemanticsAttr("verify.ownership.sil.never");
}

// See swift/Basic/Statistic.h for declaration: this enables tracing
// SILFunctions, is defined here to avoid too much layering violation / circular
// linkage dependency.

struct SILFunctionTraceFormatter : public UnifiedStatsReporter::TraceFormatter {
  void traceName(const void *Entity, raw_ostream &OS) const {
    if (!Entity)
      return;
    const SILFunction *F = static_cast<const SILFunction *>(Entity);
    OS << F->getName();
  }

  void traceLoc(const void *Entity, SourceManager *SM,
                clang::SourceManager *CSM, raw_ostream &OS) const {
    if (!Entity)
      return;
    const SILFunction *F = static_cast<const SILFunction *>(Entity);
    F->getLocation().getSourceRange().print(OS, *SM, false);
  }
};

static SILFunctionTraceFormatter TF;

template<>
const UnifiedStatsReporter::TraceFormatter*
FrontendStatsTracer::getTraceFormatter<const SILFunction *>() {
  return &TF;
}