/// Replace load sequence which may contain
/// a chain of struct_element_addr followed by a load.
/// The sequence is traversed starting from the load
/// instruction.
static SILValue convertLoadSequence(SILValue oldSequence,
                                    SILValue newRootValue,
                                    SILBuilder &B) {

  if (isa<GlobalAddrInst>(oldSequence))
    return newRootValue;

  if (auto *LI = dyn_cast<LoadInst>(oldSequence)) {
    auto newValue = convertLoadSequence(LI->getOperand(), newRootValue, B);
    LI->replaceAllUsesWith(newValue);
    return newValue;
  }

  // It is a series of struct_element_addr followed by load.
  if (auto *SEAI = dyn_cast<StructElementAddrInst>(oldSequence)) {
    auto newValue = convertLoadSequence(SEAI->getOperand(), newRootValue, B);
    newValue = B.createStructExtract(SEAI->getLoc(), newValue, SEAI->getField());
    return newValue;
  }

  if (auto *TEAI = dyn_cast<TupleElementAddrInst>(oldSequence)) {
    auto newValue = convertLoadSequence(TEAI->getOperand(), newRootValue, B);
    newValue = B.createTupleExtract(TEAI->getLoc(), newValue, TEAI->getFieldNo());
    return newValue;
  }

  llvm_unreachable("Unknown instruction sequence for reading from a global");
  return nullptr;
}

// A utility function for cloning the apply instruction.
static FullApplySite CloneApply(FullApplySite AI, SILBuilder &Builder) {
  // Clone the Apply.
  Builder.setCurrentDebugScope(AI.getDebugScope());
  Builder.addOpenedArchetypeOperands(AI.getInstruction());
  auto Args = AI.getArguments();
  SmallVector<SILValue, 8> Ret(Args.size());
  for (unsigned i = 0, e = Args.size(); i != e; ++i)
    Ret[i] = Args[i];

  FullApplySite NAI;

  switch (AI.getInstruction()->getKind()) {
  case SILInstructionKind::ApplyInst:
    NAI = Builder.createApply(AI.getLoc(), AI.getCallee(),
                                   AI.getSubstitutions(),
                                   Ret,
                                   cast<ApplyInst>(AI)->isNonThrowing());
    break;
  case SILInstructionKind::TryApplyInst: {
    auto *TryApplyI = cast<TryApplyInst>(AI.getInstruction());
    NAI = Builder.createTryApply(AI.getLoc(), AI.getCallee(),
                                      AI.getSubstitutions(),
                                      Ret,
                                      TryApplyI->getNormalBB(),
                                      TryApplyI->getErrorBB());
    }
    break;
  default:
    llvm_unreachable("Trying to clone an unsupported apply instruction");
  }

  NAI.getInstruction();
  return NAI;
}

void swift::
addRetainsForConvertedDirectResults(SILBuilder &Builder,
                                    SILLocation Loc,
                                    SILValue ReturnValue,
                                    SILInstruction *AI,
                                    ArrayRef<ResultDescriptor> DirectResults) {
  for (auto I : indices(DirectResults)) {
    auto &RV = DirectResults[I];
    if (RV.CalleeRetain.empty()) continue;

    bool IsSelfRecursionEpilogueRetain = false;
    for (auto &X : RV.CalleeRetain) {
      IsSelfRecursionEpilogueRetain |= (AI == X);
    }

    // We do not create a retain if this ApplyInst is a self-recursion.
    if (IsSelfRecursionEpilogueRetain)
      continue;

    // Extract the return value if necessary.
    SILValue SpecificResultValue = ReturnValue;
    if (DirectResults.size() != 1)
      SpecificResultValue = Builder.createTupleExtract(Loc, ReturnValue, I);

    Builder.createRetainValue(Loc, SpecificResultValue);
  }
}

/// Promote a DebugValueAddr to a DebugValue of the given value.
static void
promoteDebugValueAddr(DebugValueAddrInst *DVAI, SILValue Value, SILBuilder &B) {
  assert(Value && "Expected valid value");
  B.setInsertionPoint(DVAI);
  B.setCurrentDebugScope(DVAI->getDebugScope());
  B.createDebugValue(DVAI->getLoc(), Value, DVAI->getVarInfo());
  DVAI->eraseFromParent();
}

/// Promote a DebugValueAddr to a DebugValue of the given value.
static void
promoteDebugValueAddr(DebugValueAddrInst *DVAI, SILValue Value, SILBuilder &B) {
  assert(DVAI->getOperand()->getType().isLoadable(DVAI->getModule()) &&
         "Unexpected promotion of address-only type!");
  assert(Value && "Expected valid value");
  B.setInsertionPoint(DVAI);
  B.setCurrentDebugScope(DVAI->getDebugScope());
  B.createDebugValue(DVAI->getLoc(), Value, *DVAI->getVarInfo());
  DVAI->eraseFromParent();
}

/// Set up epilogue work for the thunk arguments based in the given argument.
/// Default implementation simply passes it through.
void
FunctionSignatureTransform::
OwnedToGuaranteedAddArgumentRelease(ArgumentDescriptor &AD, SILBuilder &Builder,
                                    SILFunction *F) {
  // If we have any arguments that were consumed but are now guaranteed,
  // insert a release_value.
  if (!AD.OwnedToGuaranteed) {
    return;
  }

  SILInstruction *Call = findOnlyApply(F);
  if (isa<ApplyInst>(Call)) {
    Builder.setInsertionPoint(&*std::next(SILBasicBlock::iterator(Call)));
    Builder.createReleaseValue(RegularLocation(SourceLoc()),
                               F->getArguments()[AD.Index],
                               Builder.getDefaultAtomicity());
  } else {
    SILBasicBlock *NormalBB = dyn_cast<TryApplyInst>(Call)->getNormalBB();
    Builder.setInsertionPoint(&*NormalBB->begin());
    Builder.createReleaseValue(RegularLocation(SourceLoc()),
                               F->getArguments()[AD.Index],
                               Builder.getDefaultAtomicity());

    SILBasicBlock *ErrorBB = dyn_cast<TryApplyInst>(Call)->getErrorBB();
    Builder.setInsertionPoint(&*ErrorBB->begin());
    Builder.createReleaseValue(RegularLocation(SourceLoc()),
                               F->getArguments()[AD.Index],
                               Builder.getDefaultAtomicity());
  }
}

/// Subtract a constant from a builtin integer value.
static SILValue getSub(SILLocation Loc, SILValue Val, unsigned SubVal,
                       SILBuilder &B) {
  SmallVector<SILValue, 4> Args(1, Val);
  Args.push_back(B.createIntegerLiteral(Loc, Val->getType(), SubVal));
  Args.push_back(B.createIntegerLiteral(
      Loc, SILType::getBuiltinIntegerType(1, B.getASTContext()), -1));

  auto *AI = B.createBuiltinBinaryFunctionWithOverflow(
      Loc, "ssub_with_overflow", Args);
  return B.createTupleExtract(Loc, AI, 0);
}

SILValue 
SROAMemoryUseAnalyzer::createAgg(SILBuilder &B, SILLocation Loc,
                                 SILType Ty,
                                 ArrayRef<SILValue> Elements) {
  if (TT)
    return B.createTuple(Loc, Ty, Elements);

  assert(SD && "SD must not be null here since it or TT must be set to call"
         " this method.");
  return B.createStruct(Loc, Ty, Elements);
}

/// Carry out the operations required for an indirect conditional cast
/// using a scalar cast operation.
void swift::emitIndirectConditionalCastWithScalar(
    SILBuilder &B, ModuleDecl *M, SILLocation loc,
    CastConsumptionKind consumption, SILValue src, CanType sourceType,
    SILValue dest, CanType targetType, SILBasicBlock *indirectSuccBB,
    SILBasicBlock *indirectFailBB, ProfileCounter TrueCount,
    ProfileCounter FalseCount) {
  assert(canUseScalarCheckedCastInstructions(B.getModule(),
                                             sourceType, targetType));

  // We only need a different failure block if the cast consumption
  // requires us to destroy the source value.
  SILBasicBlock *scalarFailBB;
  if (!shouldDestroyOnFailure(consumption)) {
    scalarFailBB = indirectFailBB;
  } else {
    scalarFailBB = B.splitBlockForFallthrough();
  }

  // We always need a different success block.
  SILBasicBlock *scalarSuccBB = B.splitBlockForFallthrough();

  auto &srcTL = B.getModule().Types.getTypeLowering(src->getType());

  // Always take; this works under an assumption that retaining the
  // result is equivalent to retaining the source.  That means that
  // these casts would not be appropriate for bridging-like conversions.
  SILValue srcValue = srcTL.emitLoadOfCopy(B, loc, src, IsTake);

  SILType targetValueType = dest->getType().getObjectType();
  B.createCheckedCastBranch(loc, /*exact*/ false, srcValue, targetValueType,
                            scalarSuccBB, scalarFailBB, TrueCount, FalseCount);

  // Emit the success block.
  B.setInsertionPoint(scalarSuccBB); {
    auto &targetTL = B.getModule().Types.getTypeLowering(targetValueType);
    SILValue succValue = scalarSuccBB->createPHIArgument(
        targetValueType, ValueOwnershipKind::Owned);
    if (!shouldTakeOnSuccess(consumption))
      targetTL.emitCopyValue(B, loc, succValue);
    targetTL.emitStoreOfCopy(B, loc, succValue, dest, IsInitialization);
    B.createBranch(loc, indirectSuccBB);
  }

  // Emit the failure block.
  if (shouldDestroyOnFailure(consumption)) {
    B.setInsertionPoint(scalarFailBB);
    srcTL.emitDestroyValue(B, loc, srcValue);
    B.createBranch(loc, indirectFailBB);
  }
}

NullablePtr<SILInstruction>
Projection::
createAggFromFirstLevelProjections(SILBuilder &B, SILLocation Loc,
                                   SILType BaseType,
                                   llvm::SmallVectorImpl<SILValue> &Values) {
    if (BaseType.getStructOrBoundGenericStruct()) {
        return B.createStruct(Loc, BaseType, Values);
    }

    if (BaseType.is<TupleType>()) {
        return B.createTuple(Loc, BaseType, Values);
    }

    return nullptr;
}

static void addRetainsForConvertedDirectResults(SILBuilder &Builder,
                                                SILLocation Loc,
                                                SILValue ReturnValue,
                                     ArrayRef<ResultDescriptor> DirectResults) {
  for (auto I : indices(DirectResults)) {
    auto &RV = DirectResults[I];
    if (RV.CalleeRetain.empty()) continue;

    // Extract the return value if necessary.
    SILValue SpecificResultValue = ReturnValue;
    if (DirectResults.size() != 1)
      SpecificResultValue = Builder.createTupleExtract(Loc, ReturnValue, I);

    Builder.createRetainValue(Loc, SpecificResultValue);
  }
}

/// Given an RValue of aggregate type, compute the values of the elements by
/// emitting a series of tuple_element instructions.
static void getScalarizedElements(SILValue V,
                                  SmallVectorImpl<SILValue> &ElementVals,
                                  SILLocation Loc, SILBuilder &B) {
  TupleType *TT = V->getType().castTo<TupleType>();
  for (auto Index : indices(TT->getElements())) {
    ElementVals.push_back(B.emitTupleExtract(Loc, V, Index));
  }
}

/// Given a pointer to a tuple type, compute the addresses of each element and
/// add them to the ElementAddrs vector.
static void
getScalarizedElementAddresses(SILValue Pointer, SILBuilder &B, SILLocation Loc,
                              SmallVectorImpl<SILValue> &ElementAddrs) {
  TupleType *TT = Pointer->getType().castTo<TupleType>();
  for (auto Index : indices(TT->getElements())) {
    ElementAddrs.push_back(B.createTupleElementAddr(Loc, Pointer, Index));
  }
}

  /// If necessary insert an overflow for this induction variable.
  /// If we compare for equality we need to make sure that the range does wrap.
  /// We would have trapped either when overflowing or when accessing an array
  /// out of bounds in the original loop.
  void checkOverflow(SILBuilder &Builder) {
    if (IsOverflowCheckInserted || Cmp != BuiltinValueKind::ICMP_EQ)
      return;

    auto Loc = Inc->getLoc();
    auto ResultTy = SILType::getBuiltinIntegerType(1, Builder.getASTContext());
    auto *CmpSGE = Builder.createBuiltinBinaryFunction(
        Loc, "cmp_sge", Start->getType(), ResultTy, {Start, End});
    Builder.createCondFail(Loc, CmpSGE);
    IsOverflowCheckInserted = true;

    // We can now remove the cond fail on the increment the above comparison
    // guarantees that the addition won't overflow.
    auto *CondFail = isOverflowChecked(cast<BuiltinInst>(Inc));
    if (CondFail)
      CondFail->eraseFromParent();
  }

// Clone a chain of ConvertFunctionInsts.
SILValue ClosureSpecCloner::cloneCalleeConversion(SILValue calleeValue,
                                                  SILValue NewClosure,
                                                  SILBuilder &Builder) {
  if (calleeValue == CallSiteDesc.getClosure())
    return NewClosure;

  if (auto *CFI = dyn_cast<ConvertFunctionInst>(calleeValue)) {
    calleeValue = cloneCalleeConversion(CFI->getOperand(), NewClosure, Builder);
    return Builder.createConvertFunction(CallSiteDesc.getLoc(), calleeValue,
                                         CFI->getType());
  }

  auto *Cvt = cast<ConvertEscapeToNoEscapeInst>(calleeValue);
  calleeValue = cloneCalleeConversion(Cvt->getOperand(), NewClosure, Builder);
  return Builder.createConvertEscapeToNoEscape(
      CallSiteDesc.getLoc(), calleeValue, Cvt->getType(), false, true);
}

void SILInstruction::setDebugScope(SILBuilder &B, const SILDebugScope *DS) {
  if (getDebugScope() && getDebugScope()->InlinedCallSite)
    assert(DS->InlinedCallSite && "throwing away inlined scope info");

  assert(DS->InlinedCallSite || DS->SILFn == getFunction() &&
         "scope of a non-inlined instruction points to different function");

  Location = *B.getOrCreateDebugLocation(getLoc(), DS);
}

/// Given an aggregate value and an access path, extract the value indicated by
/// the path.
static SILValue ExtractSubElement(SILValue Val, unsigned SubElementNumber,
                                  SILBuilder &B, SILLocation Loc) {
  SILType ValTy = Val.getType();
  
  // Extract tuple elements.
  if (auto TT = ValTy.getAs<TupleType>()) {
    for (unsigned EltNo : indices(TT.getElementTypes())) {
      // Keep track of what subelement is being referenced.
      SILType EltTy = ValTy.getTupleElementType(EltNo);
      unsigned NumSubElt = getNumSubElements(EltTy, B.getModule());
      if (SubElementNumber < NumSubElt) {
        Val = B.emitTupleExtract(Loc, Val, EltNo, EltTy);
        return ExtractSubElement(Val, SubElementNumber, B, Loc);
      }
      
      SubElementNumber -= NumSubElt;
    }
    
    llvm_unreachable("Didn't find field");
  }
  
  // Extract struct elements.
  if (auto *SD = getFullyReferenceableStruct(ValTy)) {
    for (auto *D : SD->getStoredProperties()) {
      auto fieldType = ValTy.getFieldType(D, B.getModule());
      unsigned NumSubElt = getNumSubElements(fieldType, B.getModule());
      
      if (SubElementNumber < NumSubElt) {
        Val = B.emitStructExtract(Loc, Val, D);
        return ExtractSubElement(Val, SubElementNumber, B, Loc);
      }
      
      SubElementNumber -= NumSubElt;
      
    }
    llvm_unreachable("Didn't find field");
  }
  
  // Otherwise, we're down to a scalar.
  assert(SubElementNumber == 0 && "Miscalculation indexing subelements");
  return Val;
}

void swift::
addReleasesForConvertedOwnedParameter(SILBuilder &Builder,
                                      SILLocation Loc,
                                      OperandValueArrayRef Parameters,
                                      ArrayRef<ArgumentDescriptor> &ArgDescs) {
  // If we have any arguments that were consumed but are now guaranteed,
  // insert a release_value.
  for (auto &ArgDesc : ArgDescs) {
    // The argument is dead. Make sure we have a release to balance out
    // the retain for creating the @owned parameter.
    if (ArgDesc.IsEntirelyDead && 
        ArgDesc.Arg->getKnownParameterInfo().getConvention() ==
        ParameterConvention::Direct_Owned) {
       Builder.createReleaseValue(Loc, Parameters[ArgDesc.Index]);
       continue;
    }
    if (ArgDesc.CalleeRelease.empty())
      continue;
    Builder.createReleaseValue(Loc, Parameters[ArgDesc.Index]);
  }
}

bool swift::emitSuccessfulIndirectUnconditionalCast(SILBuilder &B, Module *M,
                                                    SILLocation loc,
                                               CastConsumptionKind consumption,
                                                    SILValue src,
                                                    CanType sourceType,
                                                    SILValue dest,
                                                    CanType targetType,
                                                    SILInstruction *existingCast) {
  assert(classifyDynamicCast(M, sourceType, targetType)
           == DynamicCastFeasibility::WillSucceed);

  assert(src->getType().isAddress());
  assert(dest->getType().isAddress());

  // Casts between the same types can be always handled here.
  // Casts from non-existentials into existentials and
  // vice-versa cannot be improved yet.
  // Casts between a value type and a class cannot be optimized.
  // Therefore generate a simple unconditional_checked_cast_aadr.

  if (src->getType() != dest->getType())
  if (src->getType().isAnyExistentialType() !=
      dest->getType().isAnyExistentialType() ||
      !(src->getType().getClassOrBoundGenericClass() &&
       dest->getType().getClassOrBoundGenericClass())) {
    // If there is an existing cast with the same arguments,
    // indicate we cannot improve it.
    if (existingCast) {
      auto *UCCAI = dyn_cast<UnconditionalCheckedCastAddrInst>(existingCast);
      if (UCCAI && UCCAI->getSrc() == src && UCCAI->getDest() == dest &&
          UCCAI->getSourceType() == sourceType &&
          UCCAI->getTargetType() == targetType &&
          UCCAI->getConsumptionKind() == consumption) {
        // Indicate that the existing cast cannot be further improved.
        return false;
      }
    }

    B.createUnconditionalCheckedCastAddr(loc, consumption, src, sourceType,
                                         dest, targetType);
    return true;
  }

  Source source(src, sourceType, consumption);
  Target target(dest, targetType);
  Source result = CastEmitter(B, M, loc).emitTopLevel(source, target);
  assert(result.isAddress());
  assert(result.Value == dest);
  assert(result.Consumption == CastConsumptionKind::TakeAlways);
  (void) result;
  return true;
}

void
FunctionSignatureTransform::
OwnedToGuaranteedAddResultRelease(ResultDescriptor &RD, SILBuilder &Builder,
                                  SILFunction *F) {
 // If we have any result that were consumed but are now guaranteed,
  // insert a release_value.
  if (!RD.OwnedToGuaranteed) {
    return;
  }

  SILInstruction *Call = findOnlyApply(F);
  if (isa<ApplyInst>(Call)) {
    Builder.setInsertionPoint(&*std::next(SILBasicBlock::iterator(Call)));
    Builder.createRetainValue(RegularLocation(SourceLoc()), Call,
                              Atomicity::Atomic);
  } else {
    SILBasicBlock *NormalBB = dyn_cast<TryApplyInst>(Call)->getNormalBB();
    Builder.setInsertionPoint(&*NormalBB->begin());
    Builder.createRetainValue(RegularLocation(SourceLoc()),
                              NormalBB->getArgument(0), Atomicity::Atomic);
  }
}