CanType
SILBoxType::getFieldLoweredType(SILModule &M, unsigned index) const {
  auto fieldTy = getLayout()->getFields()[index].getLoweredType();
  
  // Apply generic arguments if the layout is generic.
  if (!getGenericArgs().empty()) {
    // FIXME: Map the field type into the layout's generic context because
    // SIL TypeLowering currently expects to lower abstract generic parameters
    // with a generic context pushed, but nested generic contexts are not
    // supported by TypeLowering. If TypeLowering were properly
    // de-contextualized and plumbed through the generic signature, this could
    // be avoided.
    auto *env = getLayout()->getGenericSignature()
      .getGenericEnvironment(*M.getSwiftModule());
    auto substMap =
      env->getSubstitutionMap(M.getSwiftModule(), getGenericArgs());
    fieldTy = env->mapTypeIntoContext(M.getSwiftModule(), fieldTy)
      ->getCanonicalType();
    
    fieldTy = SILType::getPrimitiveObjectType(fieldTy)
      .subst(M, substMap)
      .getSwiftRValueType();
  }
  return fieldTy;
}

void swift::runSILPassesForOnone(SILModule &Module) {
  // Verify the module, if required.
  if (Module.getOptions().VerifyAll)
    Module.verify();

  SILPassManager PM(&Module, "Onone");

  // First specialize user-code.
  PM.addUsePrespecialized();
  PM.run();
  PM.resetAndRemoveTransformations();

  // Don't keep external functions from stdlib and other modules.
  // We don't want that our unoptimized version will be linked instead
  // of the optimized version from the stdlib.
  // Here we just convert external definitions to declarations. LLVM will
  // eventually remove unused declarations.
  PM.addExternalDefsToDecls();

  PM.runOneIteration();

  // Verify the module, if required.
  if (Module.getOptions().VerifyAll)
    Module.verify();
  else {
    DEBUG(Module.verify());
  }
}

/// Check if a given class is final in terms of a current
/// compilation, i.e.:
/// - it is really final
/// - or it is private and has not sub-classes
/// - or it is an internal class without sub-classes and
///   it is a whole-module compilation.
static bool isKnownFinalClass(ClassDecl *CD, SILModule &M,
                              ClassHierarchyAnalysis *CHA) {
  const DeclContext *DC = M.getAssociatedContext();

  if (CD->isFinal())
    return true;

  // Without an associated context we cannot perform any
  // access-based optimizations.
  if (!DC)
    return false;

  // Only handle classes defined within the SILModule's associated context.
  if (!CD->isChildContextOf(DC))
    return false;

  if (!CD->hasAccess())
    return false;

  // Only consider 'private' members, unless we are in whole-module compilation.
  switch (CD->getEffectiveAccess()) {
  case AccessLevel::Open:
    return false;
  case AccessLevel::Public:
  case AccessLevel::Internal:
    if (!M.isWholeModule())
      return false;
    break;
  case AccessLevel::FilePrivate:
  case AccessLevel::Private:
    break;
  }

  // Take the ClassHierarchyAnalysis into account.
  // If a given class has no subclasses and
  // - private
  // - or internal and it is a WMO compilation
  // then this class can be considered final for the purpose
  // of devirtualization.
  if (CHA) {
    if (!CHA->hasKnownDirectSubclasses(CD)) {
      switch (CD->getEffectiveAccess()) {
      case AccessLevel::Open:
        return false;
      case AccessLevel::Public:
      case AccessLevel::Internal:
        if (!M.isWholeModule())
          return false;
        break;
      case AccessLevel::FilePrivate:
      case AccessLevel::Private:
        break;
      }

      return true;
    }
  }

  return false;
}

SILBasicBlock::~SILBasicBlock() {
  // Invalidate all of the basic block arguments.
  for (auto *Arg : ArgumentList) {
    getModule().notifyDeleteHandlers(Arg);
  }

  dropAllReferences();

  SILModule *M = nullptr;
  if (getParent())
    M = &getParent()->getModule();

  for (auto I = begin(), E = end(); I != E;) {
    auto Inst = &*I;
    ++I;
    if (M) {
      // Notify the delete handlers that the instructions in this block are
      // being deleted.
      M->notifyDeleteHandlers(Inst);
    }
    erase(Inst);
  }

  // iplist's destructor is going to destroy the InstList.
  InstList.clearAndLeakNodesUnsafely();
}

// During SIL Lowering, passes may see partially lowered SIL, which is
// inconsistent with the current (canonical) stage. We don't change the SIL
// stage until lowering is complete. Consequently, any pass added to this
// PassManager needs to be able to handle the output of the previous pass. If
// the function pass needs to read SIL from other functions, it may be best to
// convert it to a module pass to ensure that the SIL input is always at the
// same stage of lowering.
void swift::runSILLoweringPasses(SILModule &Module) {
  SILPassManager PM(&Module, "LoweringPasses", /*isMandatoryPipeline=*/ true);
  PM.executePassPipelinePlan(
      SILPassPipelinePlan::getLoweringPassPipeline(Module.getOptions()));

  assert(Module.getStage() == SILStage::Lowered);
}

/// Can the given cast be performed by the scalar checked-cast
/// instructions?
bool swift::canUseScalarCheckedCastInstructions(SILModule &M,
                                                CanType sourceType,
                                                CanType targetType) {
  // Look through one level of optionality on the source.
  auto objectType = sourceType;
  if (auto type = objectType.getOptionalObjectType())
    objectType = type;

  // Casting to NSError needs to go through the indirect-cast case,
  // since it may conform to Error and require Error-to-NSError
  // bridging, unless we can statically see that the source type inherits
  // NSError.
  
  // A class-constrained archetype may be bound to NSError, unless it has a
  // non-NSError superclass constraint. Casts to archetypes thus must always be
  // indirect.
  if (auto archetype = targetType->getAs<ArchetypeType>()) {
    // Only ever permit this if the source type is a reference type.
    if (!objectType.isAnyClassReferenceType())
      return false;
    
      auto super = archetype->getSuperclass();
      if (super.isNull())
        return false;

    // A base class constraint that isn't NSError rules out the archetype being
    // bound to NSError.
    if (M.getASTContext().LangOpts.EnableObjCInterop) {
      if (auto nserror = M.Types.getNSErrorType())
         return !super->isEqual(nserror);
    }
    
    // If NSError wasn't loaded, any base class constraint must not be NSError.
    return true;
  }
  
  if (M.getASTContext().LangOpts.EnableObjCInterop
      && targetType == M.Types.getNSErrorType()) {
    // If we statically know the source is an NSError subclass, then the cast
    // can go through the scalar path (and it's trivially true so can be
    // killed).
    return targetType->isExactSuperclassOf(objectType);
  }
  
  // Three supported cases:
  // - metatype to metatype
  // - metatype to object
  // - object to object
  if ((objectType.isAnyClassReferenceType() || isa<AnyMetatypeType>(objectType))
      && targetType.isAnyClassReferenceType())
    return true;

  if (isa<AnyMetatypeType>(objectType) && isa<AnyMetatypeType>(targetType))
    return true;
  
  // Otherwise, we need to use the general indirect-cast functions.
  return false;
}

Emitter::Emitter(StringRef PassName, SILModule &M)
    : Module(M), PassName(PassName),
      PassedEnabled(
          M.getASTContext().LangOpts.OptimizationRemarkPassedPattern &&
          M.getASTContext().LangOpts.OptimizationRemarkPassedPattern->match(
              PassName)),
      MissedEnabled(
          M.getASTContext().LangOpts.OptimizationRemarkMissedPattern &&
          M.getASTContext().LangOpts.OptimizationRemarkMissedPattern->match(
              PassName)) {}

bool swift::runSILOwnershipEliminatorPass(SILModule &Module) {
  auto &Ctx = Module.getASTContext();

  SILPassManager PM(&Module);
  PM.executePassPipelinePlan(
      SILPassPipelinePlan::getOwnershipEliminatorPassPipeline(
          Module.getOptions()));

  return Ctx.hadError();
}

static void emitRemark(SILModule &Module, const Remark<RemarkT> &R,
                       Diag<ArgTypes...> ID, bool DiagEnabled) {
  if (R.getLocation().isInvalid())
    return;
  if (auto *Out = Module.getOptRecordStream())
    // YAMLTraits takes a non-const reference even when outputting.
    *Out << const_cast<Remark<RemarkT> &>(R);
  if (DiagEnabled)
    Module.getASTContext().Diags.diagnose(R.getLocation(), ID, R.getMsg());
}

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,
                         IsDynamicallyReplaceable_t isDynamic)
    : 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),
      IsDynamicReplaceable(isDynamic), OptMode(OptimizationMode::NotSet),
      EffectsKindAttr(E), EntryCount(entryCount) {
  assert(!Transparent || !IsDynamicReplaceable);
  validateSubclassScope(classSubclassScope, isThunk, nullptr);

  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(SILModule &Module, SILLinkage Linkage, StringRef Name,
                         CanSILFunctionType LoweredType,
                         GenericEnvironment *genericEnv,
                         Optional<SILLocation> Loc, IsBare_t isBareSILFunction,
                         IsTransparent_t isTrans, IsSerialized_t isSerialized,
                         IsThunk_t isThunk, SubclassScope classSubclassScope,
                         Inline_t inlineStrategy, EffectsKind E,
                         SILFunction *InsertBefore,
                         const SILDebugScope *DebugScope)
    : Module(Module), Name(Name), LoweredType(LoweredType),
      GenericEnv(genericEnv), DebugScope(DebugScope), Bare(isBareSILFunction),
      Transparent(isTrans), Serialized(isSerialized), Thunk(isThunk),
      ClassSubclassScope(unsigned(classSubclassScope)), GlobalInitFlag(false),
      InlineStrategy(inlineStrategy), Linkage(unsigned(Linkage)),
      KeepAsPublic(false), EffectsKindAttr(E) {

  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;
}

void swift::runSILOptimizationPassesWithFileSpecification(SILModule &Module,
                                                          StringRef FileName) {
#ifndef NDEBUG
  if (Module.getOptions().DisableSILPerfOptimizations)
    return;

  llvm::SmallVector<PMDescriptor, 4> Descriptors;
  PMDescriptor::descriptorsForFile(FileName, Descriptors);

  for (auto &Desc : Descriptors) {
    DEBUG(llvm::dbgs() << "Creating PM: " << Desc.Id << "\n");
    SILPassManager PM(&Module, Desc.Id);

    for (auto &P : Desc.Passes) {
      DEBUG(llvm::dbgs() << "  Adding Pass: " << P << "\n");
      PM.addPassForName(P);
    }

    if (Desc.ActionName.equals("run_n_times")) {
      unsigned Count = Desc.ActionCount.getValue();
      DEBUG(llvm::dbgs() << "    Running " << Count << " iterations...\n");
      for (unsigned i = 0, e = Count; i < e; ++i) {
        PM.runOneIteration();
      }
    } else if (Desc.ActionName.equals("run_to_fixed_point")) {
      DEBUG(llvm::dbgs() << "    Running until fixed point...\n");
      PM.run();
    } else {
      llvm_unreachable("unknown action");
    }
  }
#endif
}

/// Returns the outlined function type.
///
/// This depends on the first instruction we matched. Either we matched a load
/// or we started the match at the class method instruction.
///
/// load %30 : *UITextField:
///   (@in_guaranteed InstanceType) -> (@owned Optional<BridgedInstanceType>)
/// objc_method %31 : UITextField
///   (@unowned InstanceType) -> (@owned Optional<BridgedInstanceType>)
///
CanSILFunctionType BridgedProperty::getOutlinedFunctionType(SILModule &M) {
  SmallVector<SILParameterInfo, 4> Parameters;
  if (auto *Load = dyn_cast<LoadInst>(FirstInst))
    Parameters.push_back(
      SILParameterInfo(Load->getType().getASTType(),
                       ParameterConvention::Indirect_In_Guaranteed));
  else
    Parameters.push_back(SILParameterInfo(cast<ObjCMethodInst>(FirstInst)
                                              ->getOperand()
                                              ->getType()
                                              .getASTType(),
                                          ParameterConvention::Direct_Unowned));
  SmallVector<SILResultInfo, 4> Results;

  Results.push_back(SILResultInfo(
                      switchInfo.Br->getArg(0)->getType().getASTType(),
                      ResultConvention::Owned));
  auto ExtInfo =
      SILFunctionType::ExtInfo(SILFunctionType::Representation::Thin,
                               /*pseudogeneric*/ false, /*noescape*/ false);
  auto FunctionType = SILFunctionType::get(
      nullptr, ExtInfo, SILCoroutineKind::None,
      ParameterConvention::Direct_Unowned, Parameters, /*yields*/ {},
      Results, None, M.getASTContext());
  return FunctionType;
}

SILType GenericEnvironment::mapTypeIntoContext(SILModule &M,
                                               SILType type) const {
  return doSubstDependentSILType(M,
    [&](CanType t) {
      return mapTypeIntoContext(M.getSwiftModule(), t)->getCanonicalType();
    },
    type);
}

// Start with the substitutions from the apply.
// Try to propagate them to find out the real substitutions required
// to invoke the method.
static SubstitutionMap
getSubstitutionsForCallee(SILModule &M,
                          CanSILFunctionType baseCalleeType,
                          CanType derivedSelfType,
                          FullApplySite AI) {

  // If the base method is not polymorphic, no substitutions are required,
  // even if we originally had substitutions for calling the derived method.
  if (!baseCalleeType->isPolymorphic())
    return SubstitutionMap();

  // Add any generic substitutions for the base class.
  Type baseSelfType = baseCalleeType->getSelfParameter().getType();
  if (auto metatypeType = baseSelfType->getAs<MetatypeType>())
    baseSelfType = metatypeType->getInstanceType();

  auto *baseClassDecl = baseSelfType->getClassOrBoundGenericClass();
  assert(baseClassDecl && "not a class method");

  unsigned baseDepth = 0;
  SubstitutionMap baseSubMap;
  if (auto baseClassSig = baseClassDecl->getGenericSignatureOfContext()) {
    baseDepth = baseClassSig->getGenericParams().back()->getDepth() + 1;

    // Compute the type of the base class, starting from the
    // derived class type and the type of the method's self
    // parameter.
    Type derivedClass = derivedSelfType;
    if (auto metatypeType = derivedClass->getAs<MetatypeType>())
      derivedClass = metatypeType->getInstanceType();
    baseSubMap = derivedClass->getContextSubstitutionMap(
        M.getSwiftModule(), baseClassDecl);
  }

  SubstitutionMap origSubMap = AI.getSubstitutionMap();

  Type calleeSelfType = AI.getOrigCalleeType()->getSelfParameter().getType();
  if (auto metatypeType = calleeSelfType->getAs<MetatypeType>())
    calleeSelfType = metatypeType->getInstanceType();
  auto *calleeClassDecl = calleeSelfType->getClassOrBoundGenericClass();
  assert(calleeClassDecl && "self is not a class type");

  // Add generic parameters from the method itself, ignoring any generic
  // parameters from the derived class.
  unsigned origDepth = 0;
  if (auto calleeClassSig = calleeClassDecl->getGenericSignatureOfContext())
    origDepth = calleeClassSig->getGenericParams().back()->getDepth() + 1;

  auto baseCalleeSig = baseCalleeType->getGenericSignature();

  return
    SubstitutionMap::combineSubstitutionMaps(baseSubMap,
                                             origSubMap,
                                             CombineSubstitutionMaps::AtDepth,
                                             baseDepth,
                                             origDepth,
                                             baseCalleeSig);
}

/// Writes SIL out to the given file.
static bool writeSIL(SILModule &SM, Module *M, bool EmitVerboseSIL,
                     StringRef OutputFilename, bool SortSIL) {
  std::error_code EC;
  llvm::raw_fd_ostream OS(OutputFilename, EC, llvm::sys::fs::F_None);
  if (EC) {
    M->getASTContext().Diags.diagnose(SourceLoc(), diag::error_opening_output,
                                      OutputFilename, EC.message());
    return true;
  }
  SM.print(OS, EmitVerboseSIL, M, SortSIL);
  return false;
}

SILType SILType::getEnumElementType(EnumElementDecl *elt, SILModule &M) const {
  assert(elt->getDeclContext() == getEnumOrBoundGenericEnum());
  assert(elt->hasAssociatedValues());

  if (auto objectType = getSwiftRValueType().getAnyOptionalObjectType()) {
    assert(elt == M.getASTContext().getOptionalSomeDecl());
    return SILType(objectType, getCategory());
  }

  auto substEltTy =
    getSwiftRValueType()->getTypeOfMember(M.getSwiftModule(), elt,
                                          elt->getArgumentInterfaceType());
  auto loweredTy =
    M.Types.getLoweredType(M.Types.getAbstractionPattern(elt), substEltTy);

  // If the case is indirect, then the payload is boxed.
  if (elt->isIndirect() || elt->getParentEnum()->isIndirect())
    loweredTy = SILType::getPrimitiveObjectType(
      SILBoxType::get(loweredTy.getSwiftRValueType()));

  return SILType(loweredTy.getSwiftRValueType(), getCategory());
}

/// Emit a diagnostic for `poundAssert` builtins whose condition is
/// false or whose condition cannot be evaluated.
static void diagnosePoundAssert(const SILInstruction *I,
                                SILModule &M,
                                ConstExprEvaluator &constantEvaluator) {
  auto *builtinInst = dyn_cast<BuiltinInst>(I);
  if (!builtinInst ||
      builtinInst->getBuiltinKind() != BuiltinValueKind::PoundAssert)
    return;

  SmallVector<SymbolicValue, 1> values;
  constantEvaluator.computeConstantValues({builtinInst->getArguments()[0]},
                                          values);
  SymbolicValue value = values[0];
  if (!value.isConstant()) {
    diagnose(M.getASTContext(), I->getLoc().getSourceLoc(),
             diag::pound_assert_condition_not_constant);

    // If we have more specific information about what went wrong, emit
    // notes.
    if (value.getKind() == SymbolicValue::Unknown)
      value.emitUnknownDiagnosticNotes(builtinInst->getLoc());
    return;
  }
  assert(value.getKind() == SymbolicValue::Integer &&
         "sema prevents non-integer #assert condition");

  APInt intValue = value.getIntegerValue();
  assert(intValue.getBitWidth() == 1 &&
         "sema prevents non-int1 #assert condition");
  if (intValue.isNullValue()) {
    auto *message = cast<StringLiteralInst>(builtinInst->getArguments()[1]);
    StringRef messageValue = message->getValue();
    if (messageValue.empty())
      messageValue = "assertion failed";
    diagnose(M.getASTContext(), I->getLoc().getSourceLoc(),
             diag::pound_assert_failure, messageValue);
    return;
  }
}

SILType SILType::substGenericArgs(SILModule &M,
                                  ArrayRef<Substitution> Subs) const {
  SILFunctionType *fnTy = getSwiftRValueType()->castTo<SILFunctionType>();
  if (Subs.empty()) {
    assert(!fnTy->isPolymorphic() && "function type without subs must not "
           "be polymorphic.");
    return *this;
  }
  assert(fnTy->isPolymorphic() && "Can only subst interface generic args on "
         "polymorphic function types.");
  CanSILFunctionType canFnTy =
    fnTy->substGenericArgs(M, M.getSwiftModule(), Subs);
  return SILType::getPrimitiveObjectType(canFnTy);
}

// Convert the substituted function type into a specialized function type based
// on the ReabstractionInfo.
CanSILFunctionType ReabstractionInfo::
createSpecializedType(CanSILFunctionType SubstFTy, SILModule &M) const {
  llvm::SmallVector<SILResultInfo, 8> SpecializedResults;
  llvm::SmallVector<SILParameterInfo, 8> SpecializedParams;

  unsigned ResultIdx = 0;
  for (SILResultInfo RI : SubstFTy->getAllResults()) {
    if (RI.isDirect()) {
      SpecializedResults.push_back(RI);
    } else {
      if (isResultConverted(ResultIdx++)) {
        // Convert the indirect result to a direct result.
        SILType SILResTy = SILType::getPrimitiveObjectType(RI.getType());
        // Indirect results are passed as owned, so we also need to pass the
        // direct result as owned (except it's a trivial type).
        auto C = (SILResTy.isTrivial(M) ? ResultConvention::Unowned :
                  ResultConvention::Owned);
        SpecializedResults.push_back(SILResultInfo(RI.getType(), C));
      } else {
        // No conversion: re-use the original result info.
        SpecializedResults.push_back(RI);
      }
    }
  }
  unsigned ParamIdx = 0;
  for (SILParameterInfo PI : SubstFTy->getParameters()) {
    if (isParamConverted(ParamIdx++)) {
      // Convert the indirect parameter to a direct parameter.
      SILType SILParamTy = SILType::getPrimitiveObjectType(PI.getType());
      // Indirect parameters are passed as owned, so we also need to pass the
      // direct parameter as owned (except it's a trivial type).
      auto C = (SILParamTy.isTrivial(M) ? ParameterConvention::Direct_Unowned :
                ParameterConvention::Direct_Owned);
      SpecializedParams.push_back(SILParameterInfo(PI.getType(), C));
    } else {
      // No conversion: re-use the original parameter info.
      SpecializedParams.push_back(PI);
    }
  }
  return
    SILFunctionType::get(SubstFTy->getGenericSignature(),
                         SubstFTy->getExtInfo(),
                         SubstFTy->getCalleeConvention(), SpecializedParams,
                         SpecializedResults, SubstFTy->getOptionalErrorResult(),
                         M.getASTContext());
}