src/IceTargetLoweringMIPS32.cpp

//
//                        The Subzero Code Generator
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief Implements the TargetLoweringMIPS32 class, which consists almost
/// entirely of the lowering sequence for each high-level instruction.
///
//===----------------------------------------------------------------------===//

#include "IceTargetLoweringMIPS32.h"

#include "IceCfg.h"
#include "IceCfgNode.h"
#include "IceClFlags.h"
#include "IceDefs.h"
#include "IceELFObjectWriter.h"
#include "IceGlobalInits.h"
#include "IceInstMIPS32.h"
#include "IceInstVarIter.h"
#include "IceLiveness.h"
#include "IceOperand.h"
#include "IcePhiLoweringImpl.h"
#include "IceRegistersMIPS32.h"
#include "IceTargetLoweringMIPS32.def"
#include "IceUtils.h"
#include "llvm/Support/MathExtras.h"

namespace MIPS32 {
std::unique_ptr<::Ice::TargetLowering> createTargetLowering(::Ice::Cfg *Func) {
  return ::Ice::MIPS32::TargetMIPS32::create(Func);
}

std::unique_ptr<::Ice::TargetDataLowering>
createTargetDataLowering(::Ice::GlobalContext *Ctx) {
  return ::Ice::MIPS32::TargetDataMIPS32::create(Ctx);
}

std::unique_ptr<::Ice::TargetHeaderLowering>
createTargetHeaderLowering(::Ice::GlobalContext *Ctx) {
  return ::Ice::MIPS32::TargetHeaderMIPS32::create(Ctx);
}

void staticInit(::Ice::GlobalContext *Ctx) {
  ::Ice::MIPS32::TargetMIPS32::staticInit(Ctx);
}

bool shouldBePooled(const ::Ice::Constant *C) {
  return ::Ice::MIPS32::TargetMIPS32::shouldBePooled(C);
}
} // end of namespace MIPS32

namespace Ice {
namespace MIPS32 {

using llvm::isInt;

namespace {

// The maximum number of arguments to pass in GPR registers.
constexpr uint32_t MIPS32_MAX_GPR_ARG = 4;

std::array<RegNumT, MIPS32_MAX_GPR_ARG> GPRArgInitializer;
std::array<RegNumT, MIPS32_MAX_GPR_ARG / 2> I64ArgInitializer;

constexpr uint32_t MIPS32_MAX_FP_ARG = 2;

std::array<RegNumT, MIPS32_MAX_FP_ARG> FP32ArgInitializer;
std::array<RegNumT, MIPS32_MAX_FP_ARG> FP64ArgInitializer;

const char *getRegClassName(RegClass C) {
  auto ClassNum = static_cast<RegClassMIPS32>(C);
  assert(ClassNum < RCMIPS32_NUM);
  switch (ClassNum) {
  default:
    assert(C < RC_Target);
    return regClassString(C);
    // Add handling of new register classes below.
  }
}

// Stack alignment
constexpr uint32_t MIPS32_STACK_ALIGNMENT_BYTES = 8;

// Value is in bytes. Return Value adjusted to the next highest multiple of the
// stack alignment required for the given type.
uint32_t applyStackAlignmentTy(uint32_t Value, Type Ty) {
  size_t typeAlignInBytes = typeWidthInBytes(Ty);
  if (isVectorType(Ty))
    UnimplementedError(getFlags());
  return Utils::applyAlignment(Value, typeAlignInBytes);
}

// Value is in bytes. Return Value adjusted to the next highest multiple of the
// stack alignment.
uint32_t applyStackAlignment(uint32_t Value) {
  return Utils::applyAlignment(Value, MIPS32_STACK_ALIGNMENT_BYTES);
}

} // end of anonymous namespace

TargetMIPS32::TargetMIPS32(Cfg *Func) : TargetLowering(Func) {}

void TargetMIPS32::assignVarStackSlots(VarList &SortedSpilledVariables,
                                       size_t SpillAreaPaddingBytes,
                                       size_t SpillAreaSizeBytes,
                                       size_t GlobalsAndSubsequentPaddingSize) {
  const VariablesMetadata *VMetadata = Func->getVMetadata();
  size_t GlobalsSpaceUsed = SpillAreaPaddingBytes;
  size_t NextStackOffset = SpillAreaPaddingBytes;
  CfgVector<size_t> LocalsSize(Func->getNumNodes());
  const bool SimpleCoalescing = !callsReturnsTwice();

  for (Variable *Var : SortedSpilledVariables) {
    size_t Increment = typeWidthInBytesOnStack(Var->getType());
    if (SimpleCoalescing && VMetadata->isTracked(Var)) {
      if (VMetadata->isMultiBlock(Var)) {
        GlobalsSpaceUsed += Increment;
        NextStackOffset = GlobalsSpaceUsed;
      } else {
        SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
        LocalsSize[NodeIndex] += Increment;
        NextStackOffset = SpillAreaPaddingBytes +
                          GlobalsAndSubsequentPaddingSize +
                          LocalsSize[NodeIndex];
      }
    } else {
      NextStackOffset += Increment;
    }
    Var->setStackOffset(SpillAreaSizeBytes - NextStackOffset);
  }
}

void TargetMIPS32::staticInit(GlobalContext *Ctx) {
  (void)Ctx;
  RegNumT::setLimit(RegMIPS32::Reg_NUM);
  SmallBitVector IntegerRegisters(RegMIPS32::Reg_NUM);
  SmallBitVector I64PairRegisters(RegMIPS32::Reg_NUM);
  SmallBitVector Float32Registers(RegMIPS32::Reg_NUM);
  SmallBitVector Float64Registers(RegMIPS32::Reg_NUM);
  SmallBitVector VectorRegisters(RegMIPS32::Reg_NUM);
  SmallBitVector InvalidRegisters(RegMIPS32::Reg_NUM);
#define X(val, encode, name, scratch, preserved, stackptr, frameptr, isInt,    \
          isI64Pair, isFP32, isFP64, isVec128, alias_init)                     \
  IntegerRegisters[RegMIPS32::val] = isInt;                                    \
  I64PairRegisters[RegMIPS32::val] = isI64Pair;                                \
  Float32Registers[RegMIPS32::val] = isFP32;                                   \
  Float64Registers[RegMIPS32::val] = isFP64;                                   \
  VectorRegisters[RegMIPS32::val] = isVec128;                                  \
  RegisterAliases[RegMIPS32::val].resize(RegMIPS32::Reg_NUM);                  \
  for (SizeT RegAlias : alias_init) {                                          \
    assert(!RegisterAliases[RegMIPS32::val][RegAlias] &&                       \
           "Duplicate alias for " #val);                                       \
    RegisterAliases[RegMIPS32::val].set(RegAlias);                             \
  }                                                                            \
  RegisterAliases[RegMIPS32::val].resize(RegMIPS32::Reg_NUM);                  \
  assert(RegisterAliases[RegMIPS32::val][RegMIPS32::val]);
  REGMIPS32_TABLE;
#undef X

  // TODO(mohit.bhakkad): Change these inits once we provide argument related
  // field in register tables
  for (size_t i = 0; i < MIPS32_MAX_GPR_ARG; i++)
    GPRArgInitializer[i] = RegNumT::fixme(RegMIPS32::Reg_A0 + i);

  for (size_t i = 0; i < MIPS32_MAX_GPR_ARG / 2; i++)
    I64ArgInitializer[i] = RegNumT::fixme(RegMIPS32::Reg_A0A1 + i);

  for (size_t i = 0; i < MIPS32_MAX_FP_ARG; i++) {
    FP32ArgInitializer[i] = RegNumT::fixme(RegMIPS32::Reg_F12 + i * 2);
    FP64ArgInitializer[i] = RegNumT::fixme(RegMIPS32::Reg_F12F13 + i);
  }

  TypeToRegisterSet[IceType_void] = InvalidRegisters;
  TypeToRegisterSet[IceType_i1] = IntegerRegisters;
  TypeToRegisterSet[IceType_i8] = IntegerRegisters;
  TypeToRegisterSet[IceType_i16] = IntegerRegisters;
  TypeToRegisterSet[IceType_i32] = IntegerRegisters;
  TypeToRegisterSet[IceType_i64] = IntegerRegisters;
  TypeToRegisterSet[IceType_f32] = Float32Registers;
  TypeToRegisterSet[IceType_f64] = Float64Registers;
  TypeToRegisterSet[IceType_v4i1] = VectorRegisters;
  TypeToRegisterSet[IceType_v8i1] = VectorRegisters;
  TypeToRegisterSet[IceType_v16i1] = VectorRegisters;
  TypeToRegisterSet[IceType_v16i8] = VectorRegisters;
  TypeToRegisterSet[IceType_v8i16] = VectorRegisters;
  TypeToRegisterSet[IceType_v4i32] = VectorRegisters;
  TypeToRegisterSet[IceType_v4f32] = VectorRegisters;

  for (size_t i = 0; i < llvm::array_lengthof(TypeToRegisterSet); ++i)
    TypeToRegisterSetUnfiltered[i] = TypeToRegisterSet[i];

  filterTypeToRegisterSet(Ctx, RegMIPS32::Reg_NUM, TypeToRegisterSet,
                          llvm::array_lengthof(TypeToRegisterSet),
                          RegMIPS32::getRegName, getRegClassName);
}

void TargetMIPS32::unsetIfNonLeafFunc() {
  for (CfgNode *Node : Func->getNodes()) {
    for (Inst &Instr : Node->getInsts()) {
      if (llvm::isa<InstCall>(&Instr)) {
        // Unset MaybeLeafFunc if call instruction exists.
        MaybeLeafFunc = false;
        return;
      }
    }
  }
}

uint32_t TargetMIPS32::getStackAlignment() const {
  return MIPS32_STACK_ALIGNMENT_BYTES;
}

void TargetMIPS32::genTargetHelperCallFor(Inst *Instr) {
  constexpr bool NoTailCall = false;
  constexpr bool IsTargetHelperCall = true;

  switch (Instr->getKind()) {
  default:
    return;
  case Inst::Arithmetic: {
    Variable *Dest = Instr->getDest();
    const Type DestTy = Dest->getType();
    const InstArithmetic::OpKind Op =
        llvm::cast<InstArithmetic>(Instr)->getOp();
    if (isVectorType(DestTy)) {
      switch (Op) {
      default:
        break;
      case InstArithmetic::Fdiv:
      case InstArithmetic::Frem:
      case InstArithmetic::Sdiv:
      case InstArithmetic::Srem:
      case InstArithmetic::Udiv:
      case InstArithmetic::Urem:
        scalarizeArithmetic(Op, Dest, Instr->getSrc(0), Instr->getSrc(1));
        Instr->setDeleted();
        return;
      }
    }
    switch (DestTy) {
    default:
      return;
    case IceType_i64: {
      RuntimeHelper HelperID = RuntimeHelper::H_Num;
      switch (Op) {
      default:
        return;
      case InstArithmetic::Udiv:
        HelperID = RuntimeHelper::H_udiv_i64;
        break;
      case InstArithmetic::Sdiv:
        HelperID = RuntimeHelper::H_sdiv_i64;
        break;
      case InstArithmetic::Urem:
        HelperID = RuntimeHelper::H_urem_i64;
        break;
      case InstArithmetic::Srem:
        HelperID = RuntimeHelper::H_srem_i64;
        break;
      }

      if (HelperID == RuntimeHelper::H_Num) {
        return;
      }

      Operand *TargetHelper = Ctx->getRuntimeHelperFunc(HelperID);
      constexpr SizeT MaxArgs = 2;
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(Instr->getSrc(0));
      Call->addArg(Instr->getSrc(1));
      Instr->setDeleted();
      return;
    }
    case IceType_i32:
    case IceType_i16:
    case IceType_i8: {
      InstCast::OpKind CastKind;
      RuntimeHelper HelperID = RuntimeHelper::H_Num;
      switch (Op) {
      default:
        return;
      case InstArithmetic::Udiv:
        HelperID = RuntimeHelper::H_udiv_i32;
        CastKind = InstCast::Zext;
        break;
      case InstArithmetic::Sdiv:
        HelperID = RuntimeHelper::H_sdiv_i32;
        CastKind = InstCast::Sext;
        break;
      case InstArithmetic::Urem:
        HelperID = RuntimeHelper::H_urem_i32;
        CastKind = InstCast::Zext;
        break;
      case InstArithmetic::Srem:
        HelperID = RuntimeHelper::H_srem_i32;
        CastKind = InstCast::Sext;
        break;
      }

      if (HelperID == RuntimeHelper::H_Num) {
        return;
      }

      Operand *Src0 = Instr->getSrc(0);
      Operand *Src1 = Instr->getSrc(1);
      if (DestTy != IceType_i32) {
        // Src0 and Src1 have to be zero-, or signed-extended to i32. For Src0,
        // we just insert a InstCast right before the call to the helper.
        Variable *Src0_32 = Func->makeVariable(IceType_i32);
        Context.insert<InstCast>(CastKind, Src0_32, Src0);
        Src0 = Src0_32;

        if (auto *C = llvm::dyn_cast<ConstantInteger32>(Src1)) {
          const int32_t ShAmt = (DestTy == IceType_i16) ? 16 : 24;
          int32_t NewC = C->getValue();
          if (CastKind == InstCast::Zext) {
            NewC &= ~(0x80000000l >> ShAmt);
          } else {
            NewC = (NewC << ShAmt) >> ShAmt;
          }
          Src1 = Ctx->getConstantInt32(NewC);
        } else {
          Variable *Src1_32 = Func->makeVariable(IceType_i32);
          Context.insert<InstCast>(CastKind, Src1_32, Src1);
          Src1 = Src1_32;
        }
      }
      Operand *TargetHelper = Ctx->getRuntimeHelperFunc(HelperID);
      constexpr SizeT MaxArgs = 2;
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      assert(Src0->getType() == IceType_i32);
      Call->addArg(Src0);
      assert(Src1->getType() == IceType_i32);
      Call->addArg(Src1);
      Instr->setDeleted();
      return;
    }
    case IceType_f32:
    case IceType_f64: {
      if (Op != InstArithmetic::Frem) {
        return;
      }
      constexpr SizeT MaxArgs = 2;
      Operand *TargetHelper = Ctx->getRuntimeHelperFunc(
          DestTy == IceType_f32 ? RuntimeHelper::H_frem_f32
                                : RuntimeHelper::H_frem_f64);
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(Instr->getSrc(0));
      Call->addArg(Instr->getSrc(1));
      Instr->setDeleted();
      return;
    }
    }
    llvm::report_fatal_error("Control flow should never have reached here.");
  }
  case Inst::Cast: {
    Variable *Dest = Instr->getDest();
    Operand *Src0 = Instr->getSrc(0);
    const Type DestTy = Dest->getType();
    const Type SrcTy = Src0->getType();
    auto *CastInstr = llvm::cast<InstCast>(Instr);
    const InstCast::OpKind CastKind = CastInstr->getCastKind();

    switch (CastKind) {
    default:
      return;
    case InstCast::Fptosi:
    case InstCast::Fptoui: {
      if (DestTy != IceType_i64) {
        return;
      }
      const bool DestIsSigned = CastKind == InstCast::Fptosi;
      const bool Src0IsF32 = isFloat32Asserting32Or64(SrcTy);
      Operand *TargetHelper = Ctx->getRuntimeHelperFunc(
          Src0IsF32 ? (DestIsSigned ? RuntimeHelper::H_fptosi_f32_i64
                                    : RuntimeHelper::H_fptoui_f32_i64)
                    : (DestIsSigned ? RuntimeHelper::H_fptosi_f64_i64
                                    : RuntimeHelper::H_fptoui_f64_i64));
      static constexpr SizeT MaxArgs = 1;
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(Src0);
      Instr->setDeleted();
      return;
    }
    case InstCast::Sitofp:
    case InstCast::Uitofp: {
      if (SrcTy != IceType_i64) {
        return;
      }
      const bool SourceIsSigned = CastKind == InstCast::Sitofp;
      const bool DestIsF32 = isFloat32Asserting32Or64(Dest->getType());
      Operand *TargetHelper = Ctx->getRuntimeHelperFunc(
          DestIsF32 ? (SourceIsSigned ? RuntimeHelper::H_sitofp_i64_f32
                                      : RuntimeHelper::H_uitofp_i64_f32)
                    : (SourceIsSigned ? RuntimeHelper::H_sitofp_i64_f64
                                      : RuntimeHelper::H_uitofp_i64_f64));
      static constexpr SizeT MaxArgs = 1;
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(Src0);
      Instr->setDeleted();
      return;
    }
    case InstCast::Bitcast: {
      if (DestTy == SrcTy) {
        return;
      }
      Variable *CallDest = Dest;
      RuntimeHelper HelperID = RuntimeHelper::H_Num;
      switch (DestTy) {
      default:
        return;
      case IceType_i8:
        assert(SrcTy == IceType_v8i1);
        HelperID = RuntimeHelper::H_bitcast_8xi1_i8;
        CallDest = Func->makeVariable(IceType_i32);
        break;
      case IceType_i16:
        assert(SrcTy == IceType_v16i1);
        HelperID = RuntimeHelper::H_bitcast_16xi1_i16;
        CallDest = Func->makeVariable(IceType_i32);
        break;
      case IceType_v8i1: {
        assert(SrcTy == IceType_i8);
        HelperID = RuntimeHelper::H_bitcast_i8_8xi1;
        Variable *Src0AsI32 = Func->makeVariable(stackSlotType());
        // Arguments to functions are required to be at least 32 bits wide.
        Context.insert<InstCast>(InstCast::Zext, Src0AsI32, Src0);
        Src0 = Src0AsI32;
      } break;
      case IceType_v16i1: {
        assert(SrcTy == IceType_i16);
        HelperID = RuntimeHelper::H_bitcast_i16_16xi1;
        Variable *Src0AsI32 = Func->makeVariable(stackSlotType());
        // Arguments to functions are required to be at least 32 bits wide.
        Context.insert<InstCast>(InstCast::Zext, Src0AsI32, Src0);
        Src0 = Src0AsI32;
      } break;
      }
      constexpr SizeT MaxSrcs = 1;
      InstCall *Call = makeHelperCall(HelperID, CallDest, MaxSrcs);
      Call->addArg(Src0);
      Context.insert(Call);
      // The PNaCl ABI disallows i8/i16 return types, so truncate the helper
      // call result to the appropriate type as necessary.
      if (CallDest->getType() != Dest->getType())
        Context.insert<InstCast>(InstCast::Trunc, Dest, CallDest);
      Instr->setDeleted();
      return;
    }
    case InstCast::Trunc: {
      if (DestTy == SrcTy) {
        return;
      }
      if (!isVectorType(SrcTy)) {
        return;
      }
      assert(typeNumElements(DestTy) == typeNumElements(SrcTy));
      assert(typeElementType(DestTy) == IceType_i1);
      assert(isVectorIntegerType(SrcTy));
      return;
    }
    case InstCast::Sext:
    case InstCast::Zext: {
      if (DestTy == SrcTy) {
        return;
      }
      if (!isVectorType(DestTy)) {
        return;
      }
      assert(typeNumElements(DestTy) == typeNumElements(SrcTy));
      assert(typeElementType(SrcTy) == IceType_i1);
      assert(isVectorIntegerType(DestTy));
      return;
    }
    }
    llvm::report_fatal_error("Control flow should never have reached here.");
  }
  case Inst::IntrinsicCall: {
    Variable *Dest = Instr->getDest();
    auto *IntrinsicCall = llvm::cast<InstIntrinsicCall>(Instr);
    Intrinsics::IntrinsicID ID = IntrinsicCall->getIntrinsicInfo().ID;
    switch (ID) {
    default:
      return;
    case Intrinsics::Ctpop: {
      Operand *Src0 = IntrinsicCall->getArg(0);
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(isInt32Asserting32Or64(Src0->getType())
                                        ? RuntimeHelper::H_call_ctpop_i32
                                        : RuntimeHelper::H_call_ctpop_i64);
      static constexpr SizeT MaxArgs = 1;
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(Src0);
      Instr->setDeleted();
      return;
    }
    case Intrinsics::Longjmp: {
      static constexpr SizeT MaxArgs = 2;
      static constexpr Variable *NoDest = nullptr;
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_longjmp);
      auto *Call = Context.insert<InstCall>(MaxArgs, NoDest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(IntrinsicCall->getArg(0));
      Call->addArg(IntrinsicCall->getArg(1));
      Instr->setDeleted();
      return;
    }
    case Intrinsics::Memcpy: {
      static constexpr SizeT MaxArgs = 3;
      static constexpr Variable *NoDest = nullptr;
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_memcpy);
      auto *Call = Context.insert<InstCall>(MaxArgs, NoDest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(IntrinsicCall->getArg(0));
      Call->addArg(IntrinsicCall->getArg(1));
      Call->addArg(IntrinsicCall->getArg(2));
      Instr->setDeleted();
      return;
    }
    case Intrinsics::Memmove: {
      static constexpr SizeT MaxArgs = 3;
      static constexpr Variable *NoDest = nullptr;
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_memmove);
      auto *Call = Context.insert<InstCall>(MaxArgs, NoDest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(IntrinsicCall->getArg(0));
      Call->addArg(IntrinsicCall->getArg(1));
      Call->addArg(IntrinsicCall->getArg(2));
      Instr->setDeleted();
      return;
    }
    case Intrinsics::Memset: {
      Operand *ValOp = IntrinsicCall->getArg(1);
      assert(ValOp->getType() == IceType_i8);
      Variable *ValExt = Func->makeVariable(stackSlotType());
      Context.insert<InstCast>(InstCast::Zext, ValExt, ValOp);

      static constexpr SizeT MaxArgs = 3;
      static constexpr Variable *NoDest = nullptr;
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_memset);
      auto *Call = Context.insert<InstCall>(MaxArgs, NoDest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(IntrinsicCall->getArg(0));
      Call->addArg(ValExt);
      Call->addArg(IntrinsicCall->getArg(2));
      Instr->setDeleted();
      return;
    }
    case Intrinsics::NaClReadTP: {
      if (SandboxingType == ST_NaCl) {
        return;
      }
      static constexpr SizeT MaxArgs = 0;
      assert(SandboxingType != ST_Nonsfi);
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_read_tp);
      Context.insert<InstCall>(MaxArgs, Dest, TargetHelper, NoTailCall,
                               IsTargetHelperCall);
      Instr->setDeleted();
      return;
    }
    case Intrinsics::Setjmp: {
      static constexpr SizeT MaxArgs = 1;
      Operand *TargetHelper =
          Ctx->getRuntimeHelperFunc(RuntimeHelper::H_call_setjmp);
      auto *Call = Context.insert<InstCall>(MaxArgs, Dest, TargetHelper,
                                            NoTailCall, IsTargetHelperCall);
      Call->addArg(IntrinsicCall->getArg(0));
      Instr->setDeleted();
      return;
    }
    }
    llvm::report_fatal_error("Control flow should never have reached here.");
  }
  }
}

void TargetMIPS32::findMaxStackOutArgsSize() {
  // MinNeededOutArgsBytes should be updated if the Target ever creates a
  // high-level InstCall that requires more stack bytes.
  size_t MinNeededOutArgsBytes = 0;
  if (!MaybeLeafFunc)
    MinNeededOutArgsBytes = MIPS32_MAX_GPR_ARG * 4;
  MaxOutArgsSizeBytes = MinNeededOutArgsBytes;
  for (CfgNode *Node : Func->getNodes()) {
    Context.init(Node);
    while (!Context.atEnd()) {
      PostIncrLoweringContext PostIncrement(Context);
      Inst *CurInstr = iteratorToInst(Context.getCur());
      if (auto *Call = llvm::dyn_cast<InstCall>(CurInstr)) {
        SizeT OutArgsSizeBytes = getCallStackArgumentsSizeBytes(Call);
        MaxOutArgsSizeBytes = std::max(MaxOutArgsSizeBytes, OutArgsSizeBytes);
      }
    }
  }
}

void TargetMIPS32::translateO2() {
  TimerMarker T(TimerStack::TT_O2, Func);

  // TODO(stichnot): share passes with X86?
  // https://code.google.com/p/nativeclient/issues/detail?id=4094
  genTargetHelperCalls();

  unsetIfNonLeafFunc();

  findMaxStackOutArgsSize();

  // Merge Alloca instructions, and lay out the stack.
  static constexpr bool SortAndCombineAllocas = true;
  Func->processAllocas(SortAndCombineAllocas);
  Func->dump("After Alloca processing");

  if (!getFlags().getEnablePhiEdgeSplit()) {
    // Lower Phi instructions.
    Func->placePhiLoads();
    if (Func->hasError())
      return;
    Func->placePhiStores();
    if (Func->hasError())
      return;
    Func->deletePhis();
    if (Func->hasError())
      return;
    Func->dump("After Phi lowering");
  }

  // Address mode optimization.
  Func->getVMetadata()->init(VMK_SingleDefs);
  Func->doAddressOpt();

  // Argument lowering
  Func->doArgLowering();

  // Target lowering. This requires liveness analysis for some parts of the
  // lowering decisions, such as compare/branch fusing. If non-lightweight
  // liveness analysis is used, the instructions need to be renumbered first.
  // TODO: This renumbering should only be necessary if we're actually
  // calculating live intervals, which we only do for register allocation.
  Func->renumberInstructions();
  if (Func->hasError())
    return;

  // TODO: It should be sufficient to use the fastest liveness calculation,
  // i.e. livenessLightweight(). However, for some reason that slows down the
  // rest of the translation. Investigate.
  Func->liveness(Liveness_Basic);
  if (Func->hasError())
    return;
  Func->dump("After MIPS32 address mode opt");

  Func->genCode();
  if (Func->hasError())
    return;
  Func->dump("After MIPS32 codegen");

  // Register allocation. This requires instruction renumbering and full
  // liveness analysis.
  Func->renumberInstructions();
  if (Func->hasError())
    return;
  Func->liveness(Liveness_Intervals);
  if (Func->hasError())
    return;
  // The post-codegen dump is done here, after liveness analysis and associated
  // cleanup, to make the dump cleaner and more useful.
  Func->dump("After initial MIPS32 codegen");
  // Validate the live range computations. The expensive validation call is
  // deliberately only made when assertions are enabled.
  assert(Func->validateLiveness());
  Func->getVMetadata()->init(VMK_All);
  regAlloc(RAK_Global);
  if (Func->hasError())
    return;
  Func->dump("After linear scan regalloc");

  if (getFlags().getEnablePhiEdgeSplit()) {
    Func->advancedPhiLowering();
    Func->dump("After advanced Phi lowering");
  }

  // Stack frame mapping.
  Func->genFrame();
  if (Func->hasError())
    return;
  Func->dump("After stack frame mapping");

  postLowerLegalization();
  if (Func->hasError())
    return;
  Func->dump("After postLowerLegalization");

  Func->contractEmptyNodes();
  Func->reorderNodes();

  // Branch optimization. This needs to be done just before code emission. In
  // particular, no transformations that insert or reorder CfgNodes should be
  // done after branch optimization. We go ahead and do it before nop insertion
  // to reduce the amount of work needed for searching for opportunities.
  Func->doBranchOpt();
  Func->dump("After branch optimization");

  // Nop insertion
  if (getFlags().getShouldDoNopInsertion()) {
    Func->doNopInsertion();
  }
}

void TargetMIPS32::translateOm1() {
  TimerMarker T(TimerStack::TT_Om1, Func);

  // TODO: share passes with X86?
  genTargetHelperCalls();

  unsetIfNonLeafFunc();

  findMaxStackOutArgsSize();

  // Do not merge Alloca instructions, and lay out the stack.
  static constexpr bool SortAndCombineAllocas = false;
  Func->processAllocas(SortAndCombineAllocas);
  Func->dump("After Alloca processing");

  Func->placePhiLoads();
  if (Func->hasError())
    return;
  Func->placePhiStores();
  if (Func->hasError())
    return;
  Func->deletePhis();
  if (Func->hasError())
    return;
  Func->dump("After Phi lowering");

  Func->doArgLowering();

  Func->genCode();
  if (Func->hasError())
    return;
  Func->dump("After initial MIPS32 codegen");

  regAlloc(RAK_InfOnly);
  if (Func->hasError())
    return;
  Func->dump("After regalloc of infinite-weight variables");

  Func->genFrame();
  if (Func->hasError())
    return;
  Func->dump("After stack frame mapping");

  postLowerLegalization();
  if (Func->hasError())
    return;
  Func->dump("After postLowerLegalization");

  // Nop insertion
  if (getFlags().getShouldDoNopInsertion()) {
    Func->doNopInsertion();
  }
}

bool TargetMIPS32::doBranchOpt(Inst *Instr, const CfgNode *NextNode) {
  if (auto *Br = llvm::dyn_cast<InstMIPS32Br>(Instr)) {
    return Br->optimizeBranch(NextNode);
  }
  return false;
}

namespace {

const char *RegNames[RegMIPS32::Reg_NUM] = {
#define X(val, encode, name, scratch, preserved, stackptr, frameptr, isInt,    \
          isI64Pair, isFP32, isFP64, isVec128, alias_init)                     \
  name,
    REGMIPS32_TABLE
#undef X
};

} // end of anonymous namespace

const char *RegMIPS32::getRegName(RegNumT RegNum) {
  RegNum.assertIsValid();
  return RegNames[RegNum];
}

const char *TargetMIPS32::getRegName(RegNumT RegNum, Type Ty) const {
  (void)Ty;
  return RegMIPS32::getRegName(RegNum);
}

Variable *TargetMIPS32::getPhysicalRegister(RegNumT RegNum, Type Ty) {
  if (Ty == IceType_void)
    Ty = IceType_i32;
  if (PhysicalRegisters[Ty].empty())
    PhysicalRegisters[Ty].resize(RegMIPS32::Reg_NUM);
  RegNum.assertIsValid();
  Variable *Reg = PhysicalRegisters[Ty][RegNum];
  if (Reg == nullptr) {
    Reg = Func->makeVariable(Ty);
    Reg->setRegNum(RegNum);
    PhysicalRegisters[Ty][RegNum] = Reg;
    // Specially mark a named physical register as an "argument" so that it is
    // considered live upon function entry.  Otherwise it's possible to get
    // liveness validation errors for saving callee-save registers.
    Func->addImplicitArg(Reg);
    // Don't bother tracking the live range of a named physical register.
    Reg->setIgnoreLiveness();
  }
  return Reg;
}

void TargetMIPS32::emitJumpTable(const Cfg *Func,
                                 const InstJumpTable *JumpTable) const {
  (void)Func;
  (void)JumpTable;
  UnimplementedError(getFlags());
}

/// Provide a trivial wrapper to legalize() for this common usage.
Variable *TargetMIPS32::legalizeToReg(Operand *From, RegNumT RegNum) {
  return llvm::cast<Variable>(legalize(From, Legal_Reg, RegNum));
}

/// Legalize undef values to concrete values.
Operand *TargetMIPS32::legalizeUndef(Operand *From, RegNumT RegNum) {
  (void)RegNum;
  Type Ty = From->getType();
  if (llvm::isa<ConstantUndef>(From)) {
    // Lower undefs to zero.  Another option is to lower undefs to an
    // uninitialized register; however, using an uninitialized register
    // results in less predictable code.
    //
    // If in the future the implementation is changed to lower undef
    // values to uninitialized registers, a FakeDef will be needed:
    //     Context.insert(InstFakeDef::create(Func, Reg));
    // This is in order to ensure that the live range of Reg is not
    // overestimated.  If the constant being lowered is a 64 bit value,
    // then the result should be split and the lo and hi components will
    // need to go in uninitialized registers.
    if (isVectorType(Ty))
      UnimplementedError(getFlags());
    return Ctx->getConstantZero(Ty);
  }
  return From;
}

Variable *TargetMIPS32::makeReg(Type Type, RegNumT RegNum) {
  // There aren't any 64-bit integer registers for Mips32.
  assert(Type != IceType_i64);
  Variable *Reg = Func->makeVariable(Type);
  if (RegNum.hasValue())
    Reg->setRegNum(RegNum);
  else
    Reg->setMustHaveReg();
  return Reg;
}

OperandMIPS32Mem *TargetMIPS32::formMemoryOperand(Operand *Operand, Type Ty) {
  // It may be the case that address mode optimization already creates an
  // OperandMIPS32Mem, so in that case it wouldn't need another level of
  // transformation.
  if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(Operand)) {
    return llvm::cast<OperandMIPS32Mem>(legalize(Mem));
  }

  // If we didn't do address mode optimization, then we only have a base/offset
  // to work with. MIPS always requires a base register, so just use that to
  // hold the operand.
  auto *Base = llvm::cast<Variable>(
      legalize(Operand, Legal_Reg | Legal_Rematerializable));
  const int32_t Offset = Base->hasStackOffset() ? Base->getStackOffset() : 0;
  return OperandMIPS32Mem::create(
      Func, Ty, Base,
      llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(Offset)));
}

void TargetMIPS32::emitVariable(const Variable *Var) const {
  if (!BuildDefs::dump())
    return;
  Ostream &Str = Ctx->getStrEmit();
  const Type FrameSPTy = IceType_i32;
  if (Var->hasReg()) {
    Str << '$' << getRegName(Var->getRegNum(), Var->getType());
    return;
  }
  if (Var->mustHaveReg()) {
    llvm::report_fatal_error("Infinite-weight Variable (" + Var->getName() +
                             ") has no register assigned - function " +
                             Func->getFunctionName());
  }
  const int32_t Offset = Var->getStackOffset();
  Str << Offset;
  Str << "($" << getRegName(getFrameOrStackReg(), FrameSPTy);
  Str << ")";
}

TargetMIPS32::CallingConv::CallingConv()
    : GPRegsUsed(RegMIPS32::Reg_NUM),
      GPRArgs(GPRArgInitializer.rbegin(), GPRArgInitializer.rend()),
      I64Args(I64ArgInitializer.rbegin(), I64ArgInitializer.rend()),
      VFPRegsUsed(RegMIPS32::Reg_NUM),
      FP32Args(FP32ArgInitializer.rbegin(), FP32ArgInitializer.rend()),
      FP64Args(FP64ArgInitializer.rbegin(), FP64ArgInitializer.rend()) {}

// In MIPS O32 abi FP argument registers can be used only if first argument is
// of type float/double. UseFPRegs flag is used to care of that. Also FP arg
// registers can be used only for first 2 arguments, so we require argument
// number to make register allocation decisions.
bool TargetMIPS32::CallingConv::argInReg(Type Ty, uint32_t ArgNo,
                                         RegNumT *Reg) {
  if (isScalarIntegerType(Ty))
    return argInGPR(Ty, Reg);
  if (isScalarFloatingType(Ty)) {
    if (ArgNo == 0) {
      UseFPRegs = true;
      return argInVFP(Ty, Reg);
    }
    if (UseFPRegs && ArgNo == 1) {
      UseFPRegs = false;
      return argInVFP(Ty, Reg);
    }
    return argInGPR(Ty, Reg);
  }
  UnimplementedError(getFlags());
  return false;
}

bool TargetMIPS32::CallingConv::argInGPR(Type Ty, RegNumT *Reg) {
  CfgVector<RegNumT> *Source;

  switch (Ty) {
  default: {
    UnimplementedError(getFlags());
    return false;
  } break;
  case IceType_i32:
  case IceType_f32: {
    Source = &GPRArgs;
  } break;
  case IceType_i64:
  case IceType_f64: {
    Source = &I64Args;
  } break;
  }

  discardUnavailableGPRsAndTheirAliases(Source);

  if (Source->empty()) {
    GPRegsUsed.set();
    return false;
  }

  *Reg = Source->back();
  // Note that we don't Source->pop_back() here. This is intentional. Notice how
  // we mark all of Reg's aliases as Used. So, for the next argument,
  // Source->back() is marked as unavailable, and it is thus implicitly popped
  // from the stack.
  GPRegsUsed |= RegisterAliases[*Reg];
  return true;
}

inline void TargetMIPS32::CallingConv::discardNextGPRAndItsAliases(
    CfgVector<RegNumT> *Regs) {
  GPRegsUsed |= RegisterAliases[Regs->back()];
  Regs->pop_back();
}

inline void TargetMIPS32::CallingConv::alignGPR(CfgVector<RegNumT> *Regs) {
  if (Regs->back() == RegMIPS32::Reg_A1 || Regs->back() == RegMIPS32::Reg_A3)
    discardNextGPRAndItsAliases(Regs);
}

// GPR are not packed when passing parameters. Thus, a function foo(i32, i64,
// i32) will have the first argument in a0, the second in a2-a3, and the third
// on the stack. To model this behavior, whenever we pop a register from Regs,
// we remove all of its aliases from the pool of available GPRs. This has the
// effect of computing the "closure" on the GPR registers.
void TargetMIPS32::CallingConv::discardUnavailableGPRsAndTheirAliases(
    CfgVector<RegNumT> *Regs) {
  while (!Regs->empty() && GPRegsUsed[Regs->back()]) {
    discardNextGPRAndItsAliases(Regs);
  }
}

bool TargetMIPS32::CallingConv::argInVFP(Type Ty, RegNumT *Reg) {
  CfgVector<RegNumT> *Source;

  switch (Ty) {
  default: {
    UnimplementedError(getFlags());
    return false;
  } break;
  case IceType_f32: {
    Source = &FP32Args;
  } break;
  case IceType_f64: {
    Source = &FP64Args;
  } break;
  }

  discardUnavailableVFPRegsAndTheirAliases(Source);

  if (Source->empty()) {
    VFPRegsUsed.set();
    return false;
  }

  *Reg = Source->back();
  VFPRegsUsed |= RegisterAliases[*Reg];

  // In MIPS O32 abi if fun arguments are (f32, i32) then one can not use reg_a0
  // for second argument even though it's free. f32 arg goes in reg_f12, i32 arg
  // goes in reg_a1. Similarly if arguments are (f64, i32) second argument goes
  // in reg_a3 and a0, a1 are not used.
  Source = &GPRArgs;
  // Discard one GPR reg for f32(4 bytes), two for f64(4 + 4 bytes)
  if (Ty == IceType_f64) {
    // In MIPS o32 abi, when we use GPR argument pairs to store F64 values, pair
    // must be aligned at even register. Similarly when we discard GPR registers
    // when some arguments from starting 16 bytes goes in FPR, we must take care
    // of alignment. For example if fun args are (f32, f64, f32), for first f32
    // we discard a0, now for f64 argument, which will go in F14F15, we must
    // first align GPR vector to even register by discarding a1, then discard
    // two GPRs a2 and a3. Now last f32 argument will go on stack.
    alignGPR(Source);
    discardNextGPRAndItsAliases(Source);
  }
  discardNextGPRAndItsAliases(Source);
  return true;
}

void TargetMIPS32::CallingConv::discardUnavailableVFPRegsAndTheirAliases(
    CfgVector<RegNumT> *Regs) {
  while (!Regs->empty() && VFPRegsUsed[Regs->back()]) {
    Regs->pop_back();
  }
}

void TargetMIPS32::lowerArguments() {
  VarList &Args = Func->getArgs();
  TargetMIPS32::CallingConv CC;

  // For each register argument, replace Arg in the argument list with the home
  // register. Then generate an instruction in the prolog to copy the home
  // register to the assigned location of Arg.
  Context.init(Func->getEntryNode());
  Context.setInsertPoint(Context.getCur());

  for (SizeT I = 0, E = Args.size(); I < E; ++I) {
    Variable *Arg = Args[I];
    Type Ty = Arg->getType();
    RegNumT RegNum;
    if (!CC.argInReg(Ty, I, &RegNum)) {
      continue;
    }
    Variable *RegisterArg = Func->makeVariable(Ty);
    if (BuildDefs::dump()) {
      RegisterArg->setName(Func, "home_reg:" + Arg->getName());
    }
    RegisterArg->setIsArg();
    Arg->setIsArg(false);
    Args[I] = RegisterArg;
    switch (Ty) {
    default: { RegisterArg->setRegNum(RegNum); } break;
    case IceType_i64: {
      auto *RegisterArg64 = llvm::cast<Variable64On32>(RegisterArg);
      RegisterArg64->initHiLo(Func);
      RegisterArg64->getLo()->setRegNum(
          RegNumT::fixme(RegMIPS32::get64PairFirstRegNum(RegNum)));
      RegisterArg64->getHi()->setRegNum(
          RegNumT::fixme(RegMIPS32::get64PairSecondRegNum(RegNum)));
    } break;
    }
    Context.insert<InstAssign>(Arg, RegisterArg);
  }
}

Type TargetMIPS32::stackSlotType() { return IceType_i32; }

// Helper function for addProlog().
//
// This assumes Arg is an argument passed on the stack. This sets the frame
// offset for Arg and updates InArgsSizeBytes according to Arg's width. For an
// I64 arg that has been split into Lo and Hi components, it calls itself
// recursively on the components, taking care to handle Lo first because of the
// little-endian architecture. Lastly, this function generates an instruction
// to copy Arg into its assigned register if applicable.
void TargetMIPS32::finishArgumentLowering(Variable *Arg, Variable *FramePtr,
                                          size_t BasicFrameOffset,
                                          size_t *InArgsSizeBytes) {
  const Type Ty = Arg->getType();
  *InArgsSizeBytes = applyStackAlignmentTy(*InArgsSizeBytes, Ty);

  if (auto *Arg64On32 = llvm::dyn_cast<Variable64On32>(Arg)) {
    Variable *const Lo = Arg64On32->getLo();
    Variable *const Hi = Arg64On32->getHi();
    finishArgumentLowering(Lo, FramePtr, BasicFrameOffset, InArgsSizeBytes);
    finishArgumentLowering(Hi, FramePtr, BasicFrameOffset, InArgsSizeBytes);
    return;
  }
  assert(Ty != IceType_i64);

  const int32_t ArgStackOffset = BasicFrameOffset + *InArgsSizeBytes;
  *InArgsSizeBytes += typeWidthInBytesOnStack(Ty);

  if (!Arg->hasReg()) {
    Arg->setStackOffset(ArgStackOffset);
    return;
  }

  // If the argument variable has been assigned a register, we need to copy the
  // value from the stack slot.
  Variable *Parameter = Func->makeVariable(Ty);
  Parameter->setMustNotHaveReg();
  Parameter->setStackOffset(ArgStackOffset);
  _mov(Arg, Parameter);
}

void TargetMIPS32::addProlog(CfgNode *Node) {
  // Stack frame layout:
  //
  // +------------------------+
  // | 1. preserved registers |
  // +------------------------+
  // | 2. padding             |
  // +------------------------+
  // | 3. global spill area   |
  // +------------------------+
  // | 4. padding             |
  // +------------------------+
  // | 5. local spill area    |
  // +------------------------+
  // | 6. padding             |
  // +------------------------+
  // | 7. allocas             |
  // +------------------------+
  // | 8. padding             |
  // +------------------------+
  // | 9. out args           |
  // +------------------------+ <--- StackPointer
  //
  // The following variables record the size in bytes of the given areas:
  //  * PreservedRegsSizeBytes: area 1
  //  * SpillAreaPaddingBytes:  area 2
  //  * GlobalsSize:            area 3
  //  * GlobalsAndSubsequentPaddingSize: areas 3 - 4
  //  * LocalsSpillAreaSize:    area 5
  //  * SpillAreaSizeBytes:     areas 2 - 9
  //  * maxOutArgsSizeBytes():  area 9

  Context.init(Node);
  Context.setInsertPoint(Context.getCur());

  SmallBitVector CalleeSaves = getRegisterSet(RegSet_CalleeSave, RegSet_None);
  RegsUsed = SmallBitVector(CalleeSaves.size());

  VarList SortedSpilledVariables;

  size_t GlobalsSize = 0;
  // If there is a separate locals area, this represents that area. Otherwise
  // it counts any variable not counted by GlobalsSize.
  SpillAreaSizeBytes = 0;
  // If there is a separate locals area, this specifies the alignment for it.
  uint32_t LocalsSlotsAlignmentBytes = 0;
  // The entire spill locations area gets aligned to largest natural alignment
  // of the variables that have a spill slot.
  uint32_t SpillAreaAlignmentBytes = 0;
  // For now, we don't have target-specific variables that need special
  // treatment (no stack-slot-linked SpillVariable type).
  std::function<bool(Variable *)> TargetVarHook = [](Variable *Var) {
    static constexpr bool AssignStackSlot = false;
    static constexpr bool DontAssignStackSlot = !AssignStackSlot;
    if (llvm::isa<Variable64On32>(Var)) {
      return DontAssignStackSlot;
    }
    return AssignStackSlot;
  };

  // Compute the list of spilled variables and bounds for GlobalsSize, etc.
  getVarStackSlotParams(SortedSpilledVariables, RegsUsed, &GlobalsSize,
                        &SpillAreaSizeBytes, &SpillAreaAlignmentBytes,
                        &LocalsSlotsAlignmentBytes, TargetVarHook);
  uint32_t LocalsSpillAreaSize = SpillAreaSizeBytes;
  SpillAreaSizeBytes += GlobalsSize;

  PreservedGPRs.reserve(CalleeSaves.size());

  // Consider FP and RA as callee-save / used as needed.
  if (UsesFramePointer) {
    if (RegsUsed[RegMIPS32::Reg_FP]) {
      llvm::report_fatal_error("Frame pointer has been used.");
    }
    CalleeSaves[RegMIPS32::Reg_FP] = true;
    RegsUsed[RegMIPS32::Reg_FP] = true;
  }
  if (!MaybeLeafFunc) {
    CalleeSaves[RegMIPS32::Reg_RA] = true;
    RegsUsed[RegMIPS32::Reg_RA] = true;
  }

  // Make two passes over the used registers. The first pass records all the
  // used registers -- and their aliases. Then, we figure out which GPR
  // registers should be saved.
  SmallBitVector ToPreserve(RegMIPS32::Reg_NUM);
  for (SizeT i = 0; i < CalleeSaves.size(); ++i) {
    if (CalleeSaves[i] && RegsUsed[i]) {
      ToPreserve |= RegisterAliases[i];
    }
  }

  uint32_t NumCallee = 0;

  // RegClasses is a tuple of
  //
  // <First Register in Class, Last Register in Class, Vector of Save Registers>
  //
  // We use this tuple to figure out which register we should save/restore
  // during
  // prolog/epilog.
  using RegClassType = std::tuple<uint32_t, uint32_t, VarList *>;
  const RegClassType RegClass = RegClassType(
      RegMIPS32::Reg_GPR_First, RegMIPS32::Reg_GPR_Last, &PreservedGPRs);
  const uint32_t FirstRegInClass = std::get<0>(RegClass);
  const uint32_t LastRegInClass = std::get<1>(RegClass);
  VarList *const PreservedRegsInClass = std::get<2>(RegClass);
  for (uint32_t Reg = LastRegInClass; Reg > FirstRegInClass; Reg--) {
    if (!ToPreserve[Reg]) {
      continue;
    }
    ++NumCallee;
    Variable *PhysicalRegister = getPhysicalRegister(RegNumT::fromInt(Reg));
    PreservedRegsSizeBytes +=
        typeWidthInBytesOnStack(PhysicalRegister->getType());
    PreservedRegsInClass->push_back(PhysicalRegister);
  }

  Ctx->statsUpdateRegistersSaved(NumCallee);

  // Align the variables area. SpillAreaPaddingBytes is the size of the region
  // after the preserved registers and before the spill areas.
  // LocalsSlotsPaddingBytes is the amount of padding between the globals and
  // locals area if they are separate.
  assert(SpillAreaAlignmentBytes <= MIPS32_STACK_ALIGNMENT_BYTES);
  (void)MIPS32_STACK_ALIGNMENT_BYTES;
  assert(LocalsSlotsAlignmentBytes <= SpillAreaAlignmentBytes);
  uint32_t SpillAreaPaddingBytes = 0;
  uint32_t LocalsSlotsPaddingBytes = 0;
  alignStackSpillAreas(PreservedRegsSizeBytes, SpillAreaAlignmentBytes,
                       GlobalsSize, LocalsSlotsAlignmentBytes,
                       &SpillAreaPaddingBytes, &LocalsSlotsPaddingBytes);
  SpillAreaSizeBytes += SpillAreaPaddingBytes + LocalsSlotsPaddingBytes;
  uint32_t GlobalsAndSubsequentPaddingSize =
      GlobalsSize + LocalsSlotsPaddingBytes;

  // Adds the out args space to the stack, and align SP if necessary.
  if (!NeedsStackAlignment) {
    SpillAreaSizeBytes += MaxOutArgsSizeBytes * (VariableAllocaUsed ? 0 : 1);
  } else {
    uint32_t StackOffset = PreservedRegsSizeBytes;
    uint32_t StackSize = applyStackAlignment(StackOffset + SpillAreaSizeBytes);
    if (!VariableAllocaUsed)
      StackSize = applyStackAlignment(StackSize + MaxOutArgsSizeBytes);
    SpillAreaSizeBytes = StackSize - StackOffset;
  }

  // Combine fixed alloca with SpillAreaSize.
  SpillAreaSizeBytes += FixedAllocaSizeBytes;

  TotalStackSizeBytes = PreservedRegsSizeBytes + SpillAreaSizeBytes;

  // Generate "addiu sp, sp, -TotalStackSizeBytes"
  if (TotalStackSizeBytes) {
    // Use the scratch register if needed to legalize the immediate.
    Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
    _addiu(SP, SP, -(TotalStackSizeBytes));
  }

  Ctx->statsUpdateFrameBytes(TotalStackSizeBytes);

  if (!PreservedGPRs.empty()) {
    uint32_t StackOffset = TotalStackSizeBytes;
    for (Variable *Var : *PreservedRegsInClass) {
      Variable *PhysicalRegister = getPhysicalRegister(Var->getRegNum());
      StackOffset -= typeWidthInBytesOnStack(PhysicalRegister->getType());
      Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
      OperandMIPS32Mem *MemoryLocation = OperandMIPS32Mem::create(
          Func, IceType_i32, SP,
          llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(StackOffset)));
      _sw(PhysicalRegister, MemoryLocation);
    }
  }

  Variable *FP = getPhysicalRegister(RegMIPS32::Reg_FP);

  // Generate "mov FP, SP" if needed.
  if (UsesFramePointer) {
    Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
    _mov(FP, SP);
    // Keep FP live for late-stage liveness analysis (e.g. asm-verbose mode).
    Context.insert<InstFakeUse>(FP);
  }

  // Fill in stack offsets for stack args, and copy args into registers for
  // those that were register-allocated. Args are pushed right to left, so
  // Arg[0] is closest to the stack/frame pointer.
  const VarList &Args = Func->getArgs();
  size_t InArgsSizeBytes = MIPS32_MAX_GPR_ARG * 4;
  TargetMIPS32::CallingConv CC;
  uint32_t ArgNo = 0;

  for (Variable *Arg : Args) {
    RegNumT DummyReg;
    const Type Ty = Arg->getType();
    // Skip arguments passed in registers.
    if (CC.argInReg(Ty, ArgNo, &DummyReg)) {
      ArgNo++;
      continue;
    } else {
      finishArgumentLowering(Arg, FP, TotalStackSizeBytes, &InArgsSizeBytes);
    }
  }

  // Fill in stack offsets for locals.
  assignVarStackSlots(SortedSpilledVariables, SpillAreaPaddingBytes,
                      SpillAreaSizeBytes, GlobalsAndSubsequentPaddingSize);
  this->HasComputedFrame = true;

  if (BuildDefs::dump() && Func->isVerbose(IceV_Frame)) {
    OstreamLocker _(Func->getContext());
    Ostream &Str = Func->getContext()->getStrDump();

    Str << "Stack layout:\n";
    uint32_t SPAdjustmentPaddingSize =
        SpillAreaSizeBytes - LocalsSpillAreaSize -
        GlobalsAndSubsequentPaddingSize - SpillAreaPaddingBytes -
        MaxOutArgsSizeBytes;
    Str << " in-args = " << InArgsSizeBytes << " bytes\n"
        << " preserved registers = " << PreservedRegsSizeBytes << " bytes\n"
        << " spill area padding = " << SpillAreaPaddingBytes << " bytes\n"
        << " globals spill area = " << GlobalsSize << " bytes\n"
        << " globals-locals spill areas intermediate padding = "
        << GlobalsAndSubsequentPaddingSize - GlobalsSize << " bytes\n"
        << " locals spill area = " << LocalsSpillAreaSize << " bytes\n"
        << " SP alignment padding = " << SPAdjustmentPaddingSize << " bytes\n";

    Str << "Stack details:\n"
        << " SP adjustment = " << SpillAreaSizeBytes << " bytes\n"
        << " spill area alignment = " << SpillAreaAlignmentBytes << " bytes\n"
        << " outgoing args size = " << MaxOutArgsSizeBytes << " bytes\n"
        << " locals spill area alignment = " << LocalsSlotsAlignmentBytes
        << " bytes\n"
        << " is FP based = " << 1 << "\n";
  }
  return;
}

void TargetMIPS32::addEpilog(CfgNode *Node) {
  InstList &Insts = Node->getInsts();
  InstList::reverse_iterator RI, E;
  for (RI = Insts.rbegin(), E = Insts.rend(); RI != E; ++RI) {
    if (llvm::isa<InstMIPS32Ret>(*RI))
      break;
  }
  if (RI == E)
    return;

  // Convert the reverse_iterator position into its corresponding (forward)
  // iterator position.
  InstList::iterator InsertPoint = reverseToForwardIterator(RI);
  --InsertPoint;
  Context.init(Node);
  Context.setInsertPoint(InsertPoint);

  Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
  if (UsesFramePointer) {
    Variable *FP = getPhysicalRegister(RegMIPS32::Reg_FP);
    // For late-stage liveness analysis (e.g. asm-verbose mode), adding a fake
    // use of SP before the assignment of SP=FP keeps previous SP adjustments
    // from being dead-code eliminated.
    Context.insert<InstFakeUse>(SP);
    _mov(SP, FP);
  }

  VarList::reverse_iterator RIter, END;

  if (!PreservedGPRs.empty()) {
    uint32_t StackOffset = TotalStackSizeBytes - PreservedRegsSizeBytes;
    for (RIter = PreservedGPRs.rbegin(), END = PreservedGPRs.rend();
         RIter != END; ++RIter) {
      Variable *PhysicalRegister = getPhysicalRegister((*RIter)->getRegNum());
      Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
      OperandMIPS32Mem *MemoryLocation = OperandMIPS32Mem::create(
          Func, IceType_i32, SP,
          llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(StackOffset)));
      _lw(PhysicalRegister, MemoryLocation);
      StackOffset += typeWidthInBytesOnStack(PhysicalRegister->getType());
    }
  }

  if (TotalStackSizeBytes) {
    _addiu(SP, SP, TotalStackSizeBytes);
  }

  return;
}

Variable *TargetMIPS32::PostLoweringLegalizer::newBaseRegister(
    Variable *Base, int32_t Offset, RegNumT ScratchRegNum) {
  // Legalize will likely need a lui/ori combination, but if the top bits are
  // all 0 from negating the offset and subtracting, we could use that instead.
  const bool ShouldSub = Offset != 0 && (-Offset & 0xFFFF0000) == 0;
  Variable *ScratchReg = Target->makeReg(IceType_i32, ScratchRegNum);
  if (ShouldSub) {
    Variable *OffsetVal = Target->legalizeToReg(
        Target->Ctx->getConstantInt32(-Offset), ScratchRegNum);
    Target->_sub(ScratchReg, Base, OffsetVal);
  } else {
    Target->_addiu(ScratchReg, Base, Offset);
  }

  return ScratchReg;
}

void TargetMIPS32::PostLoweringLegalizer::legalizeMov(InstMIPS32Mov *MovInstr) {
  Variable *Dest = MovInstr->getDest();
  assert(Dest != nullptr);
  const Type DestTy = Dest->getType();
  assert(DestTy != IceType_i64);

  Operand *Src = MovInstr->getSrc(0);
  const Type SrcTy = Src->getType();
  (void)SrcTy;
  assert(SrcTy != IceType_i64);

  if (MovInstr->isMultiDest() || MovInstr->isMultiSource())
    return;

  bool Legalized = false;
  auto *SrcR = llvm::cast<Variable>(Src);
  if (Dest->hasReg() && SrcR->hasReg()) {
    // This might be a GP to/from FP move generated due to argument passing.
    // Use mtc1/mfc1 instead of mov.[s/d] if src and dst registers are of
    // different types.
    const bool IsDstGPR = RegMIPS32::isGPRReg(Dest->getRegNum());
    const bool IsSrcGPR = RegMIPS32::isGPRReg(SrcR->getRegNum());
    const RegNumT SRegNum = SrcR->getRegNum();
    const RegNumT DRegNum = Dest->getRegNum();
    if (IsDstGPR != IsSrcGPR) {
      if (IsDstGPR) {
        // Dest is GPR and SrcR is FPR. Use mfc1.
        if (typeWidthInBytes(Dest->getType()) == 8) {
          // Split it into two mfc1 instructions
          Variable *SrcGPRHi = Target->makeReg(
              IceType_f32, RegMIPS32::get64PairFirstRegNum(SRegNum));
          Variable *SrcGPRLo = Target->makeReg(
              IceType_f32, RegMIPS32::get64PairSecondRegNum(SRegNum));
          Variable *DstFPRHi = Target->makeReg(
              IceType_i32, RegMIPS32::get64PairFirstRegNum(DRegNum));
          Variable *DstFPRLo = Target->makeReg(
              IceType_i32, RegMIPS32::get64PairSecondRegNum(DRegNum));
          Target->_mov(DstFPRHi, SrcGPRLo);
          Target->_mov(DstFPRLo, SrcGPRHi);
          Legalized = true;
        } else {
          Variable *SrcGPR = Target->makeReg(IceType_f32, SRegNum);
          Variable *DstFPR = Target->makeReg(IceType_i32, DRegNum);
          Target->_mov(DstFPR, SrcGPR);
          Legalized = true;
        }
      } else {
        // Dest is FPR and SrcR is GPR. Use mtc1.
        if (typeWidthInBytes(SrcR->getType()) == 8) {
          // Split it into two mtc1 instructions
          Variable *SrcGPRHi = Target->makeReg(
              IceType_i32, RegMIPS32::get64PairFirstRegNum(SRegNum));
          Variable *SrcGPRLo = Target->makeReg(
              IceType_i32, RegMIPS32::get64PairSecondRegNum(SRegNum));
          Variable *DstFPRHi = Target->makeReg(
              IceType_f32, RegMIPS32::get64PairFirstRegNum(DRegNum));
          Variable *DstFPRLo = Target->makeReg(
              IceType_f32, RegMIPS32::get64PairSecondRegNum(DRegNum));
          Target->_mov(DstFPRHi, SrcGPRLo);
          Target->_mov(DstFPRLo, SrcGPRHi);
          Legalized = true;
        } else {
          Variable *SrcGPR = Target->makeReg(IceType_i32, SRegNum);
          Variable *DstFPR = Target->makeReg(IceType_f32, DRegNum);
          Target->_mov(DstFPR, SrcGPR);
          Legalized = true;
        }
      }
    }
    if (Legalized) {
      if (MovInstr->isDestRedefined()) {
        Target->_set_dest_redefined();
      }
      MovInstr->setDeleted();
      return;
    }
  }

  if (!Dest->hasReg()) {
    auto *SrcR = llvm::cast<Variable>(Src);
    assert(SrcR->hasReg());
    assert(!SrcR->isRematerializable());
    const int32_t Offset = Dest->getStackOffset();

    // This is a _mov(Mem(), Variable), i.e., a store.
    auto *Base = Target->getPhysicalRegister(Target->getFrameOrStackReg());

    OperandMIPS32Mem *Addr = OperandMIPS32Mem::create(
        Target->Func, DestTy, Base,
        llvm::cast<ConstantInteger32>(Target->Ctx->getConstantInt32(Offset)));

    // FP arguments are passed in GP reg if first argument is in GP. In this
    // case type of the SrcR is still FP thus we need to explicitly generate sw
    // instead of swc1.
    const RegNumT RegNum = SrcR->getRegNum();
    const bool IsSrcGPReg = RegMIPS32::isGPRReg(SrcR->getRegNum());
    if (SrcTy == IceType_f32 && IsSrcGPReg == true) {
      Variable *SrcGPR = Target->makeReg(IceType_i32, RegNum);
      Target->_sw(SrcGPR, Addr);
    } else if (SrcTy == IceType_f64 && IsSrcGPReg == true) {
      Variable *SrcGPRHi =
          Target->makeReg(IceType_i32, RegMIPS32::get64PairFirstRegNum(RegNum));
      Variable *SrcGPRLo = Target->makeReg(
          IceType_i32, RegMIPS32::get64PairSecondRegNum(RegNum));
      OperandMIPS32Mem *AddrHi = OperandMIPS32Mem::create(
          Target->Func, DestTy, Base,
          llvm::cast<ConstantInteger32>(
              Target->Ctx->getConstantInt32(Offset + 4)));
      Target->_sw(SrcGPRLo, Addr);
      Target->_sw(SrcGPRHi, AddrHi);
    } else {
      Target->_sw(SrcR, Addr);
    }

    Target->Context.insert<InstFakeDef>(Dest);
    Legalized = true;
  } else if (auto *Var = llvm::dyn_cast<Variable>(Src)) {
    if (Var->isRematerializable()) {
      // This is equivalent to an x86 _lea(RematOffset(%esp/%ebp), Variable).

      // ExtraOffset is only needed for frame-pointer based frames as we have
      // to account for spill storage.
      const int32_t ExtraOffset = (Var->getRegNum() == Target->getFrameReg())
                                      ? Target->getFrameFixedAllocaOffset()
                                      : 0;

      const int32_t Offset = Var->getStackOffset() + ExtraOffset;
      Variable *Base = Target->getPhysicalRegister(Var->getRegNum());
      Variable *T = newBaseRegister(Base, Offset, Dest->getRegNum());
      Target->_mov(Dest, T);
      Legalized = true;
    } else {
      if (!Var->hasReg()) {
        // This is a _mov(Variable, Mem()), i.e., a load.
        const int32_t Offset = Var->getStackOffset();
        auto *Base = Target->getPhysicalRegister(Target->getFrameOrStackReg());
        OperandMIPS32Mem *Addr;
        Addr = OperandMIPS32Mem::create(
            Target->Func, DestTy, Base,
            llvm::cast<ConstantInteger32>(
                Target->Ctx->getConstantInt32(Offset)));
        Target->_lw(Dest, Addr);
        Legalized = true;
      }
    }
  }

  if (Legalized) {
    if (MovInstr->isDestRedefined()) {
      Target->_set_dest_redefined();
    }
    MovInstr->setDeleted();
  }
}

void TargetMIPS32::postLowerLegalization() {
  Func->dump("Before postLowerLegalization");
  assert(hasComputedFrame());
  for (CfgNode *Node : Func->getNodes()) {
    Context.init(Node);
    PostLoweringLegalizer Legalizer(this);
    while (!Context.atEnd()) {
      PostIncrLoweringContext PostIncrement(Context);
      Inst *CurInstr = iteratorToInst(Context.getCur());

      // TODO(sagar.thakur): Add remaining cases of legalization.

      if (auto *MovInstr = llvm::dyn_cast<InstMIPS32Mov>(CurInstr)) {
        Legalizer.legalizeMov(MovInstr);
      }
    }
  }
}

Operand *TargetMIPS32::loOperand(Operand *Operand) {
  assert(Operand->getType() == IceType_i64);
  if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Operand))
    return Var64On32->getLo();
  if (auto *Const = llvm::dyn_cast<ConstantInteger64>(Operand)) {
    return Ctx->getConstantInt32(static_cast<uint32_t>(Const->getValue()));
  }
  if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(Operand)) {
    // Conservatively disallow memory operands with side-effects (pre/post
    // increment) in case of duplication.
    assert(Mem->getAddrMode() == OperandMIPS32Mem::Offset);
    return OperandMIPS32Mem::create(Func, IceType_i32, Mem->getBase(),
                                    Mem->getOffset(), Mem->getAddrMode());
  }
  llvm_unreachable("Unsupported operand type");
  return nullptr;
}

Operand *TargetMIPS32::hiOperand(Operand *Operand) {
  assert(Operand->getType() == IceType_i64);
  if (Operand->getType() != IceType_i64)
    return Operand;
  if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Operand))
    return Var64On32->getHi();
  if (auto *Const = llvm::dyn_cast<ConstantInteger64>(Operand)) {
    return Ctx->getConstantInt32(
        static_cast<uint32_t>(Const->getValue() >> 32));
  }
  if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(Operand)) {
    // Conservatively disallow memory operands with side-effects
    // in case of duplication.
    assert(Mem->getAddrMode() == OperandMIPS32Mem::Offset);
    const Type SplitType = IceType_i32;
    Variable *Base = Mem->getBase();
    auto *Offset = llvm::cast<ConstantInteger32>(Mem->getOffset());
    assert(!Utils::WouldOverflowAdd(Offset->getValue(), 4));
    int32_t NextOffsetVal = Offset->getValue() + 4;
    constexpr bool SignExt = false;
    if (!OperandMIPS32Mem::canHoldOffset(SplitType, SignExt, NextOffsetVal)) {
      // We have to make a temp variable and add 4 to either Base or Offset.
      // If we add 4 to Offset, this will convert a non-RegReg addressing
      // mode into a RegReg addressing mode. Since NaCl sandboxing disallows
      // RegReg addressing modes, prefer adding to base and replacing instead.
      // Thus we leave the old offset alone.
      Constant *Four = Ctx->getConstantInt32(4);
      Variable *NewBase = Func->makeVariable(Base->getType());
      lowerArithmetic(InstArithmetic::create(Func, InstArithmetic::Add, NewBase,
                                             Base, Four));
      Base = NewBase;
    } else {
      Offset =
          llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(NextOffsetVal));
    }
    return OperandMIPS32Mem::create(Func, SplitType, Base, Offset,
                                    Mem->getAddrMode());
  }
  llvm_unreachable("Unsupported operand type");
  return nullptr;
}

SmallBitVector TargetMIPS32::getRegisterSet(RegSetMask Include,
                                            RegSetMask Exclude) const {
  SmallBitVector Registers(RegMIPS32::Reg_NUM);

#define X(val, encode, name, scratch, preserved, stackptr, frameptr, isInt,    \
          isI64Pair, isFP32, isFP64, isVec128, alias_init)                     \
  if (scratch && (Include & RegSet_CallerSave))                                \
    Registers[RegMIPS32::val] = true;                                          \
  if (preserved && (Include & RegSet_CalleeSave))                              \
    Registers[RegMIPS32::val] = true;                                          \
  if (stackptr && (Include & RegSet_StackPointer))                             \
    Registers[RegMIPS32::val] = true;                                          \
  if (frameptr && (Include & RegSet_FramePointer))                             \
    Registers[RegMIPS32::val] = true;                                          \
  if (scratch && (Exclude & RegSet_CallerSave))                                \
    Registers[RegMIPS32::val] = false;                                         \
  if (preserved && (Exclude & RegSet_CalleeSave))                              \
    Registers[RegMIPS32::val] = false;                                         \
  if (stackptr && (Exclude & RegSet_StackPointer))                             \
    Registers[RegMIPS32::val] = false;                                         \
  if (frameptr && (Exclude & RegSet_FramePointer))                             \
    Registers[RegMIPS32::val] = false;

  REGMIPS32_TABLE

#undef X

  return Registers;
}

void TargetMIPS32::lowerAlloca(const InstAlloca *Instr) {
  // Conservatively require the stack to be aligned. Some stack adjustment
  // operations implemented below assume that the stack is aligned before the
  // alloca. All the alloca code ensures that the stack alignment is preserved
  // after the alloca. The stack alignment restriction can be relaxed in some
  // cases.
  NeedsStackAlignment = true;

  // For default align=0, set it to the real value 1, to avoid any
  // bit-manipulation problems below.
  const uint32_t AlignmentParam = std::max(1u, Instr->getAlignInBytes());

  // LLVM enforces power of 2 alignment.
  assert(llvm::isPowerOf2_32(AlignmentParam));
  assert(llvm::isPowerOf2_32(MIPS32_STACK_ALIGNMENT_BYTES));

  const uint32_t Alignment =
      std::max(AlignmentParam, MIPS32_STACK_ALIGNMENT_BYTES);
  const bool OverAligned = Alignment > MIPS32_STACK_ALIGNMENT_BYTES;
  const bool OptM1 = Func->getOptLevel() == Opt_m1;
  const bool AllocaWithKnownOffset = Instr->getKnownFrameOffset();
  const bool UseFramePointer =
      hasFramePointer() || OverAligned || !AllocaWithKnownOffset || OptM1;

  if (UseFramePointer)
    setHasFramePointer();

  Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);

  Variable *Dest = Instr->getDest();
  Operand *TotalSize = Instr->getSizeInBytes();

  if (const auto *ConstantTotalSize =
          llvm::dyn_cast<ConstantInteger32>(TotalSize)) {
    const uint32_t Value =
        Utils::applyAlignment(ConstantTotalSize->getValue(), Alignment);
    FixedAllocaSizeBytes += Value;
    // Constant size alloca.
    if (!UseFramePointer) {
      // If we don't need a Frame Pointer, this alloca has a known offset to the
      // stack pointer. We don't need adjust the stack pointer, nor assign any
      // value to Dest, as Dest is rematerializable.
      assert(Dest->isRematerializable());
      Context.insert<InstFakeDef>(Dest);
      return;
    }
  } else {
    // Non-constant sizes need to be adjusted to the next highest multiple of
    // the required alignment at runtime.
    VariableAllocaUsed = true;
    Variable *AlignAmount;
    auto *TotalSizeR = legalizeToReg(TotalSize, Legal_Reg);
    auto *T1 = I32Reg();
    auto *T2 = I32Reg();
    auto *T3 = I32Reg();
    auto *T4 = I32Reg();
    auto *T5 = I32Reg();
    _addiu(T1, TotalSizeR, MIPS32_STACK_ALIGNMENT_BYTES - 1);
    _addiu(T2, getZero(), -MIPS32_STACK_ALIGNMENT_BYTES);
    _and(T3, T1, T2);
    _subu(T4, SP, T3);
    if (Instr->getAlignInBytes()) {
      AlignAmount =
          legalizeToReg(Ctx->getConstantInt32(-AlignmentParam), Legal_Reg);
      _and(T5, T4, AlignAmount);
      _mov(Dest, T5);
    } else {
      _mov(Dest, T4);
    }
    _mov(SP, Dest);
    return;
  }

  // Add enough to the returned address to account for the out args area.
  if (MaxOutArgsSizeBytes > 0) {
    Variable *T = makeReg(getPointerType());
    _addiu(T, SP, MaxOutArgsSizeBytes);
    _mov(Dest, T);
  } else {
    _mov(Dest, SP);
  }
}

void TargetMIPS32::lowerInt64Arithmetic(const InstArithmetic *Instr,
                                        Variable *Dest, Operand *Src0,
                                        Operand *Src1) {
  InstArithmetic::OpKind Op = Instr->getOp();
  switch (Op) {
  case InstArithmetic::Add:
  case InstArithmetic::And:
  case InstArithmetic::Or:
  case InstArithmetic::Sub:
  case InstArithmetic::Xor:
  case InstArithmetic::Mul:
    break;
  default:
    UnimplementedLoweringError(this, Instr);
    return;
  }
  auto *DestLo = llvm::cast<Variable>(loOperand(Dest));
  auto *DestHi = llvm::cast<Variable>(hiOperand(Dest));
  Variable *Src0LoR = legalizeToReg(loOperand(Src0));
  Variable *Src1LoR = legalizeToReg(loOperand(Src1));
  Variable *Src0HiR = legalizeToReg(hiOperand(Src0));
  Variable *Src1HiR = legalizeToReg(hiOperand(Src1));

  switch (Op) {
  case InstArithmetic::_num:
    llvm::report_fatal_error("Unknown arithmetic operator");
    return;
  case InstArithmetic::Add: {
    auto *T_Carry = I32Reg(), *T_Lo = I32Reg(), *T_Hi = I32Reg(),
         *T_Hi2 = I32Reg();
    _addu(T_Lo, Src0LoR, Src1LoR);
    _mov(DestLo, T_Lo);
    _sltu(T_Carry, T_Lo, Src0LoR);
    _addu(T_Hi, T_Carry, Src0HiR);
    _addu(T_Hi2, Src1HiR, T_Hi);
    _mov(DestHi, T_Hi2);
    return;
  }
  case InstArithmetic::And: {
    auto *T_Lo = I32Reg(), *T_Hi = I32Reg();
    _and(T_Lo, Src0LoR, Src1LoR);
    _mov(DestLo, T_Lo);
    _and(T_Hi, Src0HiR, Src1HiR);
    _mov(DestHi, T_Hi);
    return;
  }
  case InstArithmetic::Sub: {
    auto *T_Borrow = I32Reg(), *T_Lo = I32Reg(), *T_Hi = I32Reg(),
         *T_Hi2 = I32Reg();
    _subu(T_Lo, Src0LoR, Src1LoR);
    _mov(DestLo, T_Lo);
    _sltu(T_Borrow, Src0LoR, Src1LoR);
    _addu(T_Hi, T_Borrow, Src1HiR);
    _subu(T_Hi2, Src0HiR, T_Hi);
    _mov(DestHi, T_Hi2);
    return;
  }
  case InstArithmetic::Or: {
    auto *T_Lo = I32Reg(), *T_Hi = I32Reg();
    _or(T_Lo, Src0LoR, Src1LoR);
    _mov(DestLo, T_Lo);
    _or(T_Hi, Src0HiR, Src1HiR);
    _mov(DestHi, T_Hi);
    return;
  }
  case InstArithmetic::Xor: {
    auto *T_Lo = I32Reg(), *T_Hi = I32Reg();
    _xor(T_Lo, Src0LoR, Src1LoR);
    _mov(DestLo, T_Lo);
    _xor(T_Hi, Src0HiR, Src1HiR);
    _mov(DestHi, T_Hi);
    return;
  }
  case InstArithmetic::Mul: {
    // TODO(rkotler): Make sure that mul has the side effect of clobbering
    // LO, HI. Check for any other LO, HI quirkiness in this section.
    auto *T_Lo = I32Reg(RegMIPS32::Reg_LO), *T_Hi = I32Reg(RegMIPS32::Reg_HI);
    auto *T1 = I32Reg(), *T2 = I32Reg();
    auto *TM1 = I32Reg(), *TM2 = I32Reg(), *TM3 = I32Reg(), *TM4 = I32Reg();
    _multu(T_Lo, Src0LoR, Src1LoR);
    Context.insert<InstFakeDef>(T_Hi, T_Lo);
    _mflo(T1, T_Lo);
    _mfhi(T2, T_Hi);
    _mov(DestLo, T1);
    _mul(TM1, Src0HiR, Src1LoR);
    _mul(TM2, Src0LoR, Src1HiR);
    _addu(TM3, TM1, T2);
    _addu(TM4, TM3, TM2);
    _mov(DestHi, TM4);
    return;
  }
  default:
    UnimplementedLoweringError(this, Instr);
    return;
  }
}

void TargetMIPS32::lowerArithmetic(const InstArithmetic *Instr) {
  Variable *Dest = Instr->getDest();
  // We need to signal all the UnimplementedLoweringError errors before any
  // legalization into new variables, otherwise Om1 register allocation may fail
  // when it sees variables that are defined but not used.
  Type DestTy = Dest->getType();
  Operand *Src0 = legalizeUndef(Instr->getSrc(0));
  Operand *Src1 = legalizeUndef(Instr->getSrc(1));
  if (DestTy == IceType_i64) {
    lowerInt64Arithmetic(Instr, Instr->getDest(), Src0, Src1);
    return;
  }
  if (isVectorType(Dest->getType())) {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  switch (Instr->getOp()) {
  default:
    break;
  case InstArithmetic::Frem:
    UnimplementedLoweringError(this, Instr);
    return;
  }

  // At this point Dest->getType() is non-i64 scalar

  Variable *T = makeReg(Dest->getType());
  Variable *Src0R = legalizeToReg(Src0);
  Variable *Src1R = legalizeToReg(Src1);

  switch (Instr->getOp()) {
  case InstArithmetic::_num:
    break;
  case InstArithmetic::Add:
    _addu(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  case InstArithmetic::And:
    _and(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  case InstArithmetic::Or:
    _or(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  case InstArithmetic::Xor:
    _xor(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  case InstArithmetic::Sub:
    _subu(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  case InstArithmetic::Mul: {
    _mul(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Shl: {
    _sllv(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Lshr: {
    _srlv(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Ashr: {
    _srav(T, Src0R, Src1R);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Udiv: {
    auto *T_Zero = I32Reg(RegMIPS32::Reg_ZERO);
    _divu(T_Zero, Src0R, Src1R);
    _mflo(T, T_Zero);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Sdiv: {
    auto *T_Zero = I32Reg(RegMIPS32::Reg_ZERO);
    _div(T_Zero, Src0R, Src1R);
    _mflo(T, T_Zero);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Urem: {
    auto *T_Zero = I32Reg(RegMIPS32::Reg_ZERO);
    _divu(T_Zero, Src0R, Src1R);
    _mfhi(T, T_Zero);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Srem: {
    auto *T_Zero = I32Reg(RegMIPS32::Reg_ZERO);
    _div(T_Zero, Src0R, Src1R);
    _mfhi(T, T_Zero);
    _mov(Dest, T);
    return;
  }
  case InstArithmetic::Fadd: {
    if (DestTy == IceType_f32) {
      _add_s(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    if (DestTy == IceType_f64) {
      _add_d(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    break;
  }
  case InstArithmetic::Fsub:
    if (DestTy == IceType_f32) {
      _sub_s(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    if (DestTy == IceType_f64) {
      _sub_d(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    break;
  case InstArithmetic::Fmul:
    if (DestTy == IceType_f32) {
      _mul_s(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    if (DestTy == IceType_f64) {
      _mul_d(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    break;
  case InstArithmetic::Fdiv:
    if (DestTy == IceType_f32) {
      _div_s(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    if (DestTy == IceType_f64) {
      _div_d(T, Src0R, Src1R);
      _mov(Dest, T);
      return;
    }
    break;
  case InstArithmetic::Frem:
    break;
  }
  UnimplementedLoweringError(this, Instr);
}

void TargetMIPS32::lowerAssign(const InstAssign *Instr) {
  Variable *Dest = Instr->getDest();

  if (Dest->isRematerializable()) {
    Context.insert<InstFakeDef>(Dest);
    return;
  }

  Operand *Src0 = Instr->getSrc(0);
  assert(Dest->getType() == Src0->getType());
  if (Dest->getType() == IceType_i64) {
    Src0 = legalizeUndef(Src0);
    Operand *Src0Lo = legalize(loOperand(Src0), Legal_Reg);
    Operand *Src0Hi = legalize(hiOperand(Src0), Legal_Reg);
    auto *DestLo = llvm::cast<Variable>(loOperand(Dest));
    auto *DestHi = llvm::cast<Variable>(hiOperand(Dest));
    auto *T_Lo = I32Reg(), *T_Hi = I32Reg();
    _mov(T_Lo, Src0Lo);
    _mov(DestLo, T_Lo);
    _mov(T_Hi, Src0Hi);
    _mov(DestHi, T_Hi);
  } else {
    Operand *SrcR;
    if (Dest->hasReg()) {
      // If Dest already has a physical register, then legalize the Src operand
      // into a Variable with the same register assignment.  This especially
      // helps allow the use of Flex operands.
      SrcR = legalize(Src0, Legal_Reg, Dest->getRegNum());
    } else {
      // Dest could be a stack operand. Since we could potentially need
      // to do a Store (and store can only have Register operands),
      // legalize this to a register.
      SrcR = legalize(Src0, Legal_Reg);
    }
    if (isVectorType(Dest->getType())) {
      UnimplementedLoweringError(this, Instr);
    } else {
      _mov(Dest, SrcR);
    }
  }
}

void TargetMIPS32::lowerBr(const InstBr *Instr) {
  if (Instr->isUnconditional()) {
    _br(Instr->getTargetUnconditional());
    return;
  }
  CfgNode *TargetTrue = Instr->getTargetTrue();
  CfgNode *TargetFalse = Instr->getTargetFalse();
  Operand *Boolean = Instr->getCondition();
  const Inst *Producer = Computations.getProducerOf(Boolean);
  if (Producer == nullptr) {
    // Since we don't know the producer of this boolean we will assume its
    // producer will keep it in positive logic and just emit beqz with this
    // Boolean as an operand.
    auto *BooleanR = legalizeToReg(Boolean);
    _br(TargetTrue, TargetFalse, BooleanR, CondMIPS32::Cond::EQZ);
    return;
  }
  if (Producer->getKind() == Inst::Icmp) {
    const InstIcmp *CompareInst = llvm::cast<InstIcmp>(Producer);
    Operand *Src0 = CompareInst->getSrc(0);
    Operand *Src1 = CompareInst->getSrc(1);
    const Type Src0Ty = Src0->getType();
    assert(Src0Ty == Src1->getType());
    if (Src0Ty == IceType_i64) {
      UnimplementedLoweringError(this, Instr);
      return;
    }
    auto *Src0R = legalizeToReg(Src0);
    auto *Src1R = legalizeToReg(Src1);
    auto *DestT = makeReg(Src0Ty);
    switch (CompareInst->getCondition()) {
    default:
      break;
    case InstIcmp::Eq: {
      _br(TargetTrue, TargetFalse, Src0R, Src1R, CondMIPS32::Cond::NE);
      break;
    }
    case InstIcmp::Ne: {
      _br(TargetTrue, TargetFalse, Src0R, Src1R, CondMIPS32::Cond::EQ);
      break;
    }
    case InstIcmp::Ugt: {
      _sltu(DestT, Src1R, Src0R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::EQZ);
      break;
    }
    case InstIcmp::Uge: {
      _sltu(DestT, Src0R, Src1R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::NEZ);
      break;
    }
    case InstIcmp::Ult: {
      _sltu(DestT, Src0R, Src1R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::EQZ);
      break;
    }
    case InstIcmp::Ule: {
      _sltu(DestT, Src1R, Src0R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::NEZ);
      break;
    }
    case InstIcmp::Sgt: {
      _slt(DestT, Src1R, Src0R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::EQZ);
      break;
    }
    case InstIcmp::Sge: {
      _slt(DestT, Src0R, Src1R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::NEZ);
      break;
    }
    case InstIcmp::Slt: {
      _slt(DestT, Src0R, Src1R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::EQZ);
      break;
    }
    case InstIcmp::Sle: {
      _slt(DestT, Src1R, Src0R);
      _br(TargetTrue, TargetFalse, DestT, CondMIPS32::Cond::NEZ);
      break;
    }
    }
  }
}

void TargetMIPS32::lowerCall(const InstCall *Instr) {
  NeedsStackAlignment = true;

  //  Assign arguments to registers and stack. Also reserve stack.
  TargetMIPS32::CallingConv CC;

  // Pair of Arg Operand -> GPR number assignments.
  llvm::SmallVector<std::pair<Operand *, RegNumT>, MIPS32_MAX_GPR_ARG> GPRArgs;
  llvm::SmallVector<std::pair<Operand *, RegNumT>, MIPS32_MAX_FP_ARG> FPArgs;
  // Pair of Arg Operand -> stack offset.
  llvm::SmallVector<std::pair<Operand *, int32_t>, 8> StackArgs;
  size_t ParameterAreaSizeBytes = 16;

  // Classify each argument operand according to the location where the
  // argument is passed.

  for (SizeT i = 0, NumArgs = Instr->getNumArgs(); i < NumArgs; ++i) {
    Operand *Arg = legalizeUndef(Instr->getArg(i));
    const Type Ty = Arg->getType();
    bool InReg = false;
    RegNumT Reg;

    InReg = CC.argInReg(Ty, i, &Reg);

    if (!InReg) {
      ParameterAreaSizeBytes =
          applyStackAlignmentTy(ParameterAreaSizeBytes, Ty);
      StackArgs.push_back(std::make_pair(Arg, ParameterAreaSizeBytes));
      ParameterAreaSizeBytes += typeWidthInBytesOnStack(Ty);
      continue;
    }

    if (Ty == IceType_i64) {
      Operand *Lo = loOperand(Arg);
      Operand *Hi = hiOperand(Arg);
      GPRArgs.push_back(
          std::make_pair(Lo, RegMIPS32::get64PairFirstRegNum(Reg)));
      GPRArgs.push_back(
          std::make_pair(Hi, RegMIPS32::get64PairSecondRegNum(Reg)));
    } else if (isScalarIntegerType(Ty)) {
      GPRArgs.push_back(std::make_pair(Arg, Reg));
    } else {
      FPArgs.push_back(std::make_pair(Arg, Reg));
    }
  }

  // Adjust the parameter area so that the stack is aligned. It is assumed that
  // the stack is already aligned at the start of the calling sequence.
  ParameterAreaSizeBytes = applyStackAlignment(ParameterAreaSizeBytes);

  // Copy arguments that are passed on the stack to the appropriate stack
  // locations.
  Variable *SP = getPhysicalRegister(RegMIPS32::Reg_SP);
  for (auto &StackArg : StackArgs) {
    ConstantInteger32 *Loc =
        llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(StackArg.second));
    Type Ty = StackArg.first->getType();
    OperandMIPS32Mem *Addr;
    constexpr bool SignExt = false;
    if (OperandMIPS32Mem::canHoldOffset(Ty, SignExt, StackArg.second)) {
      Addr = OperandMIPS32Mem::create(Func, Ty, SP, Loc);
    } else {
      Variable *NewBase = Func->makeVariable(SP->getType());
      lowerArithmetic(
          InstArithmetic::create(Func, InstArithmetic::Add, NewBase, SP, Loc));
      Addr = formMemoryOperand(NewBase, Ty);
    }
    lowerStore(InstStore::create(Func, StackArg.first, Addr));
  }

  // Generate the call instruction.  Assign its result to a temporary with high
  // register allocation weight.
  Variable *Dest = Instr->getDest();
  // ReturnReg doubles as ReturnRegLo as necessary.
  Variable *ReturnReg = nullptr;
  Variable *ReturnRegHi = nullptr;
  if (Dest) {
    switch (Dest->getType()) {
    case IceType_NUM:
      llvm_unreachable("Invalid Call dest type");
      return;
    case IceType_void:
      break;
    case IceType_i1:
    case IceType_i8:
    case IceType_i16:
    case IceType_i32:
      ReturnReg = makeReg(Dest->getType(), RegMIPS32::Reg_V0);
      break;
    case IceType_i64:
      ReturnReg = I32Reg(RegMIPS32::Reg_V0);
      ReturnRegHi = I32Reg(RegMIPS32::Reg_V1);
      break;
    case IceType_f32:
      ReturnReg = makeReg(Dest->getType(), RegMIPS32::Reg_F0);
      break;
    case IceType_f64:
      ReturnReg = makeReg(IceType_f64, RegMIPS32::Reg_F0);
      break;
    case IceType_v4i1:
    case IceType_v8i1:
    case IceType_v16i1:
    case IceType_v16i8:
    case IceType_v8i16:
    case IceType_v4i32:
    case IceType_v4f32:
      UnimplementedLoweringError(this, Instr);
      return;
    }
  }
  Operand *CallTarget = Instr->getCallTarget();
  // Allow ConstantRelocatable to be left alone as a direct call,
  // but force other constants like ConstantInteger32 to be in
  // a register and make it an indirect call.
  if (!llvm::isa<ConstantRelocatable>(CallTarget)) {
    CallTarget = legalize(CallTarget, Legal_Reg);
  }

  // Copy arguments to be passed in registers to the appropriate registers.
  CfgVector<Variable *> RegArgs;
  for (auto &FPArg : FPArgs) {
    RegArgs.emplace_back(legalizeToReg(FPArg.first, FPArg.second));
  }
  for (auto &GPRArg : GPRArgs) {
    RegArgs.emplace_back(legalizeToReg(GPRArg.first, GPRArg.second));
  }

  // Generate a FakeUse of register arguments so that they do not get dead code
  // eliminated as a result of the FakeKill of scratch registers after the call.
  // These fake-uses need to be placed here to avoid argument registers from
  // being used during the legalizeToReg() calls above.
  for (auto *RegArg : RegArgs) {
    Context.insert<InstFakeUse>(RegArg);
  }

  // If variable alloca is used the extra 16 bytes for argument build area
  // will be allocated on stack before a call.
  if (VariableAllocaUsed)
    _addiu(SP, SP, -MaxOutArgsSizeBytes);

  Inst *NewCall = InstMIPS32Call::create(Func, ReturnReg, CallTarget);
  Context.insert(NewCall);

  if (VariableAllocaUsed)
    _addiu(SP, SP, MaxOutArgsSizeBytes);

  // Insert a fake use of stack pointer to avoid dead code elimination of addiu
  // instruction.
  Context.insert<InstFakeUse>(SP);

  if (ReturnRegHi)
    Context.insert(InstFakeDef::create(Func, ReturnRegHi));
  // Insert a register-kill pseudo instruction.
  Context.insert(InstFakeKill::create(Func, NewCall));
  // Generate a FakeUse to keep the call live if necessary.
  if (Instr->hasSideEffects() && ReturnReg) {
    Context.insert<InstFakeUse>(ReturnReg);
  }
  if (Dest == nullptr)
    return;

  // Assign the result of the call to Dest.
  if (ReturnReg) {
    if (ReturnRegHi) {
      assert(Dest->getType() == IceType_i64);
      auto *Dest64On32 = llvm::cast<Variable64On32>(Dest);
      Variable *DestLo = Dest64On32->getLo();
      Variable *DestHi = Dest64On32->getHi();
      _mov(DestLo, ReturnReg);
      _mov(DestHi, ReturnRegHi);
    } else {
      assert(Dest->getType() == IceType_i32 || Dest->getType() == IceType_i16 ||
             Dest->getType() == IceType_i8 || Dest->getType() == IceType_i1 ||
             isScalarFloatingType(Dest->getType()) ||
             isVectorType(Dest->getType()));
      if (isVectorType(Dest->getType())) {
        UnimplementedLoweringError(this, Instr);
        return;
      } else {
        _mov(Dest, ReturnReg);
      }
    }
  }
}

void TargetMIPS32::lowerCast(const InstCast *Instr) {
  InstCast::OpKind CastKind = Instr->getCastKind();
  Variable *Dest = Instr->getDest();
  Operand *Src0 = legalizeUndef(Instr->getSrc(0));
  const Type DestTy = Dest->getType();
  const Type Src0Ty = Src0->getType();
  const uint32_t ShiftAmount =
      (Src0Ty == IceType_i1
           ? INT32_BITS - 1
           : INT32_BITS - (CHAR_BITS * typeWidthInBytes(Src0Ty)));
  const uint32_t Mask =
      (Src0Ty == IceType_i1
           ? 1
           : (1 << (CHAR_BITS * typeWidthInBytes(Src0Ty))) - 1);

  if (isVectorType(DestTy)) {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  switch (CastKind) {
  default:
    Func->setError("Cast type not supported");
    return;
  case InstCast::Sext: {
    if (DestTy == IceType_i64) {
      auto *DestLo = llvm::cast<Variable>(loOperand(Dest));
      auto *DestHi = llvm::cast<Variable>(hiOperand(Dest));
      Variable *Src0R = legalizeToReg(Src0);
      Variable *T1_Lo = I32Reg();
      Variable *T2_Lo = I32Reg();
      Variable *T_Hi = I32Reg();
      if (Src0Ty == IceType_i1) {
        _sll(T1_Lo, Src0R, INT32_BITS - 1);
        _sra(T2_Lo, T1_Lo, INT32_BITS - 1);
        _mov(DestHi, T2_Lo);
        _mov(DestLo, T2_Lo);
      } else if (Src0Ty == IceType_i8 || Src0Ty == IceType_i16) {
        _sll(T1_Lo, Src0R, ShiftAmount);
        _sra(T2_Lo, T1_Lo, ShiftAmount);
        _sra(T_Hi, T2_Lo, INT32_BITS - 1);
        _mov(DestHi, T_Hi);
        _mov(DestLo, T2_Lo);
      } else if (Src0Ty == IceType_i32) {
        _mov(T1_Lo, Src0R);
        _sra(T_Hi, T1_Lo, INT32_BITS - 1);
        _mov(DestHi, T_Hi);
        _mov(DestLo, T1_Lo);
      }
    } else {
      Variable *Src0R = legalizeToReg(Src0);
      Variable *T1 = makeReg(DestTy);
      Variable *T2 = makeReg(DestTy);
      if (Src0Ty == IceType_i1 || Src0Ty == IceType_i8 ||
          Src0Ty == IceType_i16) {
        _sll(T1, Src0R, ShiftAmount);
        _sra(T2, T1, ShiftAmount);
        _mov(Dest, T2);
      }
    }
    break;
  }
  case InstCast::Zext: {
    if (DestTy == IceType_i64) {
      auto *DestLo = llvm::cast<Variable>(loOperand(Dest));
      auto *DestHi = llvm::cast<Variable>(hiOperand(Dest));
      Variable *Src0R = legalizeToReg(Src0);
      Variable *T_Lo = I32Reg();
      Variable *T_Hi = I32Reg();

      if (Src0Ty == IceType_i1 || Src0Ty == IceType_i8 || Src0Ty == IceType_i16)
        _andi(T_Lo, Src0R, Mask);
      else if (Src0Ty == IceType_i32)
        _mov(T_Lo, Src0R);
      else
        assert(Src0Ty != IceType_i64);
      _mov(DestLo, T_Lo);

      auto *Zero = getZero();
      _addiu(T_Hi, Zero, 0);
      _mov(DestHi, T_Hi);
    } else {
      Variable *Src0R = legalizeToReg(Src0);
      Variable *T = makeReg(DestTy);
      if (Src0Ty == IceType_i1 || Src0Ty == IceType_i8 ||
          Src0Ty == IceType_i16) {
        _andi(T, Src0R, Mask);
        _mov(Dest, T);
      }
    }
    break;
  }
  case InstCast::Trunc: {
    if (Src0Ty == IceType_i64)
      Src0 = loOperand(Src0);
    Variable *Src0R = legalizeToReg(Src0);
    Variable *T = makeReg(DestTy);
    _mov(T, Src0R);
    _mov(Dest, T);
    break;
  }
  case InstCast::Fptrunc: {
    assert(Dest->getType() == IceType_f32);
    assert(Src0->getType() == IceType_f64);
    auto *DestR = legalizeToReg(Dest);
    auto *Src0R = legalizeToReg(Src0);
    _cvt_s_d(DestR, Src0R);
    _mov(Dest, DestR);
    break;
  }
  case InstCast::Fpext: {
    assert(Dest->getType() == IceType_f64);
    assert(Src0->getType() == IceType_f32);
    auto *DestR = legalizeToReg(Dest);
    auto *Src0R = legalizeToReg(Src0);
    _cvt_d_s(DestR, Src0R);
    _mov(Dest, DestR);
    break;
  }
  case InstCast::Fptosi: {
    if (Src0Ty == IceType_f32 && DestTy == IceType_i32) {
      Variable *Src0R = legalizeToReg(Src0);
      Variable *FTmp = makeReg(IceType_f32);
      _trunc_w_s(FTmp, Src0R);
      _mov(Dest, FTmp);
    } else {
      UnimplementedLoweringError(this, Instr);
    }
    break;
  }
  case InstCast::Fptoui:
    UnimplementedLoweringError(this, Instr);
    break;
  case InstCast::Sitofp: {
    if (Src0Ty == IceType_i32 && DestTy == IceType_f32) {
      Variable *Src0R = legalizeToReg(Src0);
      Variable *FTmp1 = makeReg(IceType_f32);
      Variable *FTmp2 = makeReg(IceType_f32);
      _mov(FTmp1, Src0R);
      _cvt_s_w(FTmp2, FTmp1);
      _mov(Dest, FTmp2);
    } else {
      UnimplementedLoweringError(this, Instr);
    }
    break;
  }
  case InstCast::Uitofp: {
    UnimplementedLoweringError(this, Instr);
    break;
  }
  case InstCast::Bitcast: {
    UnimplementedLoweringError(this, Instr);
    break;
  }
  }
}

void TargetMIPS32::lowerExtractElement(const InstExtractElement *Instr) {
  UnimplementedLoweringError(this, Instr);
}

void TargetMIPS32::lowerFcmp(const InstFcmp *Instr) {
  Variable *Dest = Instr->getDest();
  if (isVectorType(Dest->getType())) {
    UnimplementedLoweringError(this, Instr);
    return;
  }

  auto *Src0 = Instr->getSrc(0);
  auto *Src1 = Instr->getSrc(1);
  auto *Zero = getZero();

  InstFcmp::FCond Cond = Instr->getCondition();
  auto *DestR = legalizeToReg(Dest);
  auto *Src0R = legalizeToReg(Src0);
  auto *Src1R = legalizeToReg(Src1);
  const Type Src0Ty = Src0->getType();

  Operand *FCC0 = OperandMIPS32FCC::create(getFunc(), OperandMIPS32FCC::FCC0);

  switch (Cond) {
  default: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case InstFcmp::False: {
    Context.insert<InstFakeUse>(Src0R);
    Context.insert<InstFakeUse>(Src1R);
    _addiu(DestR, Zero, 0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Oeq: {
    if (Src0Ty == IceType_f32) {
      _c_eq_s(Src0R, Src1R);
    } else {
      _c_eq_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ogt: {
    if (Src0Ty == IceType_f32) {
      _c_ule_s(Src0R, Src1R);
    } else {
      _c_ule_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Oge: {
    if (Src0Ty == IceType_f32) {
      _c_ult_s(Src0R, Src1R);
    } else {
      _c_ult_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Olt: {
    if (Src0Ty == IceType_f32) {
      _c_olt_s(Src0R, Src1R);
    } else {
      _c_olt_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ole: {
    if (Src0Ty == IceType_f32) {
      _c_ole_s(Src0R, Src1R);
    } else {
      _c_ole_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::One: {
    if (Src0Ty == IceType_f32) {
      _c_ueq_s(Src0R, Src1R);
    } else {
      _c_ueq_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ord: {
    if (Src0Ty == IceType_f32) {
      _c_un_s(Src0R, Src1R);
    } else {
      _c_un_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ueq: {
    if (Src0Ty == IceType_f32) {
      _c_ueq_s(Src0R, Src1R);
    } else {
      _c_ueq_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ugt: {
    if (Src0Ty == IceType_f32) {
      _c_ole_s(Src0R, Src1R);
    } else {
      _c_ole_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Uge: {
    if (Src0Ty == IceType_f32) {
      _c_olt_s(Src0R, Src1R);
    } else {
      _c_olt_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ult: {
    if (Src0Ty == IceType_f32) {
      _c_ult_s(Src0R, Src1R);
    } else {
      _c_ult_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Ule: {
    if (Src0Ty == IceType_f32) {
      _c_ule_s(Src0R, Src1R);
    } else {
      _c_ule_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Une: {
    if (Src0Ty == IceType_f32) {
      _c_eq_s(Src0R, Src1R);
    } else {
      _c_eq_d(Src0R, Src1R);
    }
    _movt(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::Uno: {
    if (Src0Ty == IceType_f32) {
      _c_un_s(Src0R, Src1R);
    } else {
      _c_un_d(Src0R, Src1R);
    }
    _movf(DestR, Zero, FCC0);
    _mov(Dest, DestR);
    break;
  }
  case InstFcmp::True: {
    Context.insert<InstFakeUse>(Src0R);
    Context.insert<InstFakeUse>(Src1R);
    _addiu(DestR, Zero, 1);
    _mov(Dest, DestR);
    break;
  }
  }
}

void TargetMIPS32::lower64Icmp(const InstIcmp *Instr) {
  UnimplementedLoweringError(this, Instr);
  return;
}

void TargetMIPS32::lowerIcmp(const InstIcmp *Instr) {
  auto *Src0 = Instr->getSrc(0);
  auto *Src1 = Instr->getSrc(1);
  if (Src0->getType() == IceType_i64) {
    lower64Icmp(Instr);
    return;
  }
  Variable *Dest = Instr->getDest();
  if (isVectorType(Dest->getType())) {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  InstIcmp::ICond Cond = Instr->getCondition();
  auto *Src0R = legalizeToReg(Src0);
  auto *Src1R = legalizeToReg(Src1);
  const Type Src0Ty = Src0R->getType();
  const uint32_t ShAmt = INT32_BITS - getScalarIntBitWidth(Src0->getType());
  Variable *Src0RT = I32Reg();
  Variable *Src1RT = I32Reg();

  if (Src0Ty != IceType_i32) {
    _sll(Src0RT, Src0R, ShAmt);
    _sll(Src1RT, Src1R, ShAmt);
  } else {
    _mov(Src0RT, Src0R);
    _mov(Src1RT, Src1R);
  }

  switch (Cond) {
  case InstIcmp::Eq: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    _xor(T, Src0RT, Src1RT);
    _sltiu(DestT, T, 1);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Ne: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    auto *Zero = getZero();
    _xor(T, Src0RT, Src1RT);
    _sltu(DestT, Zero, T);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Ugt: {
    auto *DestT = I32Reg();
    _sltu(DestT, Src1RT, Src0RT);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Uge: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    _sltu(T, Src0RT, Src1RT);
    _xori(DestT, T, 1);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Ult: {
    auto *DestT = I32Reg();
    _sltu(DestT, Src0RT, Src1RT);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Ule: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    _sltu(T, Src1RT, Src0RT);
    _xori(DestT, T, 1);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Sgt: {
    auto *DestT = I32Reg();
    _slt(DestT, Src1RT, Src0RT);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Sge: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    _slt(T, Src0RT, Src1RT);
    _xori(DestT, T, 1);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Slt: {
    auto *DestT = I32Reg();
    _slt(DestT, Src0RT, Src1RT);
    _mov(Dest, DestT);
    return;
  }
  case InstIcmp::Sle: {
    auto *DestT = I32Reg();
    auto *T = I32Reg();
    _slt(T, Src1RT, Src0RT);
    _xori(DestT, T, 1);
    _mov(Dest, DestT);
    return;
  }
  default:
    llvm_unreachable("Invalid ICmp operator");
    return;
  }
}

void TargetMIPS32::lowerInsertElement(const InstInsertElement *Instr) {
  UnimplementedLoweringError(this, Instr);
}

void TargetMIPS32::lowerIntrinsicCall(const InstIntrinsicCall *Instr) {
  Variable *Dest = Instr->getDest();
  Type DestTy = (Dest == nullptr) ? IceType_void : Dest->getType();
  switch (Instr->getIntrinsicInfo().ID) {
  case Intrinsics::AtomicCmpxchg: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::AtomicFence:
    UnimplementedLoweringError(this, Instr);
    return;
  case Intrinsics::AtomicFenceAll:
    // NOTE: FenceAll should prevent and load/store from being moved across the
    // fence (both atomic and non-atomic). The InstMIPS32Mfence instruction is
    // currently marked coarsely as "HasSideEffects".
    UnimplementedLoweringError(this, Instr);
    return;
  case Intrinsics::AtomicIsLockFree: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::AtomicLoad: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::AtomicRMW:
    UnimplementedLoweringError(this, Instr);
    return;
  case Intrinsics::AtomicStore: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Bswap: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Ctpop: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Ctlz: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Cttz: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Fabs: {
    if (isScalarFloatingType(DestTy)) {
      Variable *T = makeReg(DestTy);
      if (DestTy == IceType_f32) {
        _abs_s(T, legalizeToReg(Instr->getArg(0)));
      } else {
        _abs_d(T, legalizeToReg(Instr->getArg(0)));
      }
      _mov(Dest, T);
    }
    return;
  }
  case Intrinsics::Longjmp: {
    InstCall *Call = makeHelperCall(RuntimeHelper::H_call_longjmp, nullptr, 2);
    Call->addArg(Instr->getArg(0));
    Call->addArg(Instr->getArg(1));
    lowerCall(Call);
    return;
  }
  case Intrinsics::Memcpy: {
    // In the future, we could potentially emit an inline memcpy/memset, etc.
    // for intrinsic calls w/ a known length.
    InstCall *Call = makeHelperCall(RuntimeHelper::H_call_memcpy, nullptr, 3);
    Call->addArg(Instr->getArg(0));
    Call->addArg(Instr->getArg(1));
    Call->addArg(Instr->getArg(2));
    lowerCall(Call);
    return;
  }
  case Intrinsics::Memmove: {
    InstCall *Call = makeHelperCall(RuntimeHelper::H_call_memmove, nullptr, 3);
    Call->addArg(Instr->getArg(0));
    Call->addArg(Instr->getArg(1));
    Call->addArg(Instr->getArg(2));
    lowerCall(Call);
    return;
  }
  case Intrinsics::Memset: {
    // The value operand needs to be extended to a stack slot size because the
    // PNaCl ABI requires arguments to be at least 32 bits wide.
    Operand *ValOp = Instr->getArg(1);
    assert(ValOp->getType() == IceType_i8);
    Variable *ValExt = Func->makeVariable(stackSlotType());
    lowerCast(InstCast::create(Func, InstCast::Zext, ValExt, ValOp));
    InstCall *Call = makeHelperCall(RuntimeHelper::H_call_memset, nullptr, 3);
    Call->addArg(Instr->getArg(0));
    Call->addArg(ValExt);
    Call->addArg(Instr->getArg(2));
    lowerCall(Call);
    return;
  }
  case Intrinsics::NaClReadTP: {
    if (getFlags().getUseSandboxing()) {
      UnimplementedLoweringError(this, Instr);
    } else {
      InstCall *Call =
          makeHelperCall(RuntimeHelper::H_call_read_tp, Instr->getDest(), 0);
      lowerCall(Call);
    }
    return;
  }
  case Intrinsics::Setjmp: {
    InstCall *Call =
        makeHelperCall(RuntimeHelper::H_call_setjmp, Instr->getDest(), 1);
    Call->addArg(Instr->getArg(0));
    lowerCall(Call);
    return;
  }
  case Intrinsics::Sqrt: {
    if (isScalarFloatingType(DestTy)) {
      Variable *T = makeReg(DestTy);
      if (DestTy == IceType_f32) {
        _sqrt_s(T, legalizeToReg(Instr->getArg(0)));
      } else {
        _sqrt_d(T, legalizeToReg(Instr->getArg(0)));
      }
      _mov(Dest, T);
    }
    return;
  }
  case Intrinsics::Stacksave: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Stackrestore: {
    UnimplementedLoweringError(this, Instr);
    return;
  }
  case Intrinsics::Trap:
    UnimplementedLoweringError(this, Instr);
    return;
  case Intrinsics::UnknownIntrinsic:
    Func->setError("Should not be lowering UnknownIntrinsic");
    return;
  }
  return;
}

void TargetMIPS32::lowerLoad(const InstLoad *Instr) {
  // A Load instruction can be treated the same as an Assign instruction, after
  // the source operand is transformed into an OperandMIPS32Mem operand.
  Type Ty = Instr->getDest()->getType();
  Operand *Src0 = formMemoryOperand(Instr->getSourceAddress(), Ty);
  Variable *DestLoad = Instr->getDest();
  auto *Assign = InstAssign::create(Func, DestLoad, Src0);
  lowerAssign(Assign);
}

namespace {
void dumpAddressOpt(const Cfg *Func, const Variable *Base, int32_t Offset,
                    const Inst *Reason) {
  if (!BuildDefs::dump())
    return;
  if (!Func->isVerbose(IceV_AddrOpt))
    return;
  OstreamLocker _(Func->getContext());
  Ostream &Str = Func->getContext()->getStrDump();
  Str << "Instruction: ";
  Reason->dumpDecorated(Func);
  Str << "  results in Base=";
  if (Base)
    Base->dump(Func);
  else
    Str << "<null>";
  Str << ", Offset=" << Offset << "\n";
}

bool matchAssign(const VariablesMetadata *VMetadata, Variable **Var,
                 int32_t *Offset, const Inst **Reason) {
  // Var originates from Var=SrcVar ==> set Var:=SrcVar
  if (*Var == nullptr)
    return false;
  const Inst *VarAssign = VMetadata->getSingleDefinition(*Var);
  if (!VarAssign)
    return false;
  assert(!VMetadata->isMultiDef(*Var));
  if (!llvm::isa<InstAssign>(VarAssign))
    return false;

  Operand *SrcOp = VarAssign->getSrc(0);
  bool Optimized = false;
  if (auto *SrcVar = llvm::dyn_cast<Variable>(SrcOp)) {
    if (!VMetadata->isMultiDef(SrcVar) ||
        // TODO: ensure SrcVar stays single-BB
        false) {
      Optimized = true;
      *Var = SrcVar;
    } else if (auto *Const = llvm::dyn_cast<ConstantInteger32>(SrcOp)) {
      int32_t MoreOffset = Const->getValue();
      int32_t NewOffset = MoreOffset + *Offset;
      if (Utils::WouldOverflowAdd(*Offset, MoreOffset))
        return false;
      *Var = nullptr;
      *Offset += NewOffset;
      Optimized = true;
    }
  }

  if (Optimized) {
    *Reason = VarAssign;
  }

  return Optimized;
}

bool isAddOrSub(const Inst *Instr, InstArithmetic::OpKind *Kind) {
  if (const auto *Arith = llvm::dyn_cast<InstArithmetic>(Instr)) {
    switch (Arith->getOp()) {
    default:
      return false;
    case InstArithmetic::Add:
    case InstArithmetic::Sub:
      *Kind = Arith->getOp();
      return true;
    }
  }
  return false;
}

bool matchOffsetBase(const VariablesMetadata *VMetadata, Variable **Base,
                     int32_t *Offset, const Inst **Reason) {
  // Base is Base=Var+Const || Base is Base=Const+Var ==>
  //   set Base=Var, Offset+=Const
  // Base is Base=Var-Const ==>
  //   set Base=Var, Offset-=Const
  if (*Base == nullptr)
    return false;
  const Inst *BaseInst = VMetadata->getSingleDefinition(*Base);
  if (BaseInst == nullptr) {
    return false;
  }
  assert(!VMetadata->isMultiDef(*Base));

  auto *ArithInst = llvm::dyn_cast<const InstArithmetic>(BaseInst);
  if (ArithInst == nullptr)
    return false;
  InstArithmetic::OpKind Kind;
  if (!isAddOrSub(ArithInst, &Kind))
    return false;
  bool IsAdd = Kind == InstArithmetic::Add;
  Operand *Src0 = ArithInst->getSrc(0);
  Operand *Src1 = ArithInst->getSrc(1);
  auto *Var0 = llvm::dyn_cast<Variable>(Src0);
  auto *Var1 = llvm::dyn_cast<Variable>(Src1);
  auto *Const0 = llvm::dyn_cast<ConstantInteger32>(Src0);
  auto *Const1 = llvm::dyn_cast<ConstantInteger32>(Src1);
  Variable *NewBase = nullptr;
  int32_t NewOffset = *Offset;

  if (Var0 == nullptr && Const0 == nullptr) {
    assert(llvm::isa<ConstantRelocatable>(Src0));
    return false;
  }

  if (Var1 == nullptr && Const1 == nullptr) {
    assert(llvm::isa<ConstantRelocatable>(Src1));
    return false;
  }

  if (Var0 && Var1)
    // TODO(jpp): merge base/index splitting into here.
    return false;
  if (!IsAdd && Var1)
    return false;
  if (Var0)
    NewBase = Var0;
  else if (Var1)
    NewBase = Var1;
  // Compute the updated constant offset.
  if (Const0) {
    int32_t MoreOffset = IsAdd ? Const0->getValue() : -Const0->getValue();
    if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
      return false;
    NewOffset += MoreOffset;
  }
  if (Const1) {
    int32_t MoreOffset = IsAdd ? Const1->getValue() : -Const1->getValue();
    if (Utils::WouldOverflowAdd(NewOffset, MoreOffset))
      return false;
    NewOffset += MoreOffset;
  }

  // Update the computed address parameters once we are sure optimization
  // is valid.
  *Base = NewBase;
  *Offset = NewOffset;
  *Reason = BaseInst;
  return true;
}
} // end of anonymous namespace

OperandMIPS32Mem *TargetMIPS32::formAddressingMode(Type Ty, Cfg *Func,
                                                   const Inst *LdSt,
                                                   Operand *Base) {
  assert(Base != nullptr);
  int32_t OffsetImm = 0;

  Func->resetCurrentNode();
  if (Func->isVerbose(IceV_AddrOpt)) {
    OstreamLocker _(Func->getContext());
    Ostream &Str = Func->getContext()->getStrDump();
    Str << "\nAddress mode formation:\t";
    LdSt->dumpDecorated(Func);
  }

  if (isVectorType(Ty)) {
    UnimplementedError(getFlags());
    return nullptr;
  }

  auto *BaseVar = llvm::dyn_cast<Variable>(Base);
  if (BaseVar == nullptr)
    return nullptr;

  const VariablesMetadata *VMetadata = Func->getVMetadata();
  const Inst *Reason = nullptr;

  do {
    if (Reason != nullptr) {
      dumpAddressOpt(Func, BaseVar, OffsetImm, Reason);
      Reason = nullptr;
    }

    if (matchAssign(VMetadata, &BaseVar, &OffsetImm, &Reason)) {
      continue;
    }

    if (matchOffsetBase(VMetadata, &BaseVar, &OffsetImm, &Reason)) {
      continue;
    }
  } while (Reason);

  if (BaseVar == nullptr) {
    // We need base register rather than just OffsetImm. Move the OffsetImm to
    // BaseVar and form 0(BaseVar) addressing.
    const Type PointerType = getPointerType();
    BaseVar = makeReg(PointerType);
    Context.insert<InstAssign>(BaseVar, Ctx->getConstantInt32(OffsetImm));
    OffsetImm = 0;
  } else if (OffsetImm != 0) {
    // If the OffsetImm is more than signed 16-bit value then add it in the
    // BaseVar and form 0(BaseVar) addressing.
    const int32_t PositiveOffset = OffsetImm > 0 ? OffsetImm : -OffsetImm;
    const InstArithmetic::OpKind Op =
        OffsetImm > 0 ? InstArithmetic::Add : InstArithmetic::Sub;
    constexpr bool ZeroExt = false;
    if (!OperandMIPS32Mem::canHoldOffset(Ty, ZeroExt, OffsetImm)) {
      const Type PointerType = getPointerType();
      Variable *T = makeReg(PointerType);
      Context.insert<InstArithmetic>(Op, T, BaseVar,
                                     Ctx->getConstantInt32(PositiveOffset));
      BaseVar = T;
      OffsetImm = 0;
    }
  }

  assert(BaseVar != nullptr);
  assert(OffsetImm < 0 ? (-OffsetImm & 0x0000ffff) == -OffsetImm
                       : (OffsetImm & 0x0000ffff) == OffsetImm);

  return OperandMIPS32Mem::create(
      Func, Ty, BaseVar,
      llvm::cast<ConstantInteger32>(Ctx->getConstantInt32(OffsetImm)));
}

void TargetMIPS32::doAddressOptLoad() {
  Inst *Instr = iteratorToInst(Context.getCur());
  assert(llvm::isa<InstLoad>(Instr));
  Variable *Dest = Instr->getDest();
  Operand *Addr = Instr->getSrc(0);
  if (OperandMIPS32Mem *Mem =
          formAddressingMode(Dest->getType(), Func, Instr, Addr)) {
    Instr->setDeleted();
    Context.insert<InstLoad>(Dest, Mem);
  }
}

void TargetMIPS32::randomlyInsertNop(float Probability,
                                     RandomNumberGenerator &RNG) {
  RandomNumberGeneratorWrapper RNGW(RNG);
  if (RNGW.getTrueWithProbability(Probability)) {
    UnimplementedError(getFlags());
  }
}

void TargetMIPS32::lowerPhi(const InstPhi * /*Instr*/) {
  Func->setError("Phi found in regular instruction list");
}

void TargetMIPS32::lowerRet(const InstRet *Instr) {
  Variable *Reg = nullptr;
  if (Instr->hasRetValue()) {
    Operand *Src0 = Instr->getRetValue();
    switch (Src0->getType()) {
    case IceType_f32: {
      Operand *Src0F = legalizeToReg(Src0);
      Reg = makeReg(Src0F->getType(), RegMIPS32::Reg_F0);
      _mov(Reg, Src0F);
      break;
    }
    case IceType_f64: {
      Operand *Src0F = legalizeToReg(Src0);
      Reg = makeReg(Src0F->getType(), RegMIPS32::Reg_F0F1);
      _mov(Reg, Src0F);
      break;
    }
    case IceType_i1:
    case IceType_i8:
    case IceType_i16:
    case IceType_i32: {
      Operand *Src0F = legalizeToReg(Src0);
      Reg = makeReg(Src0F->getType(), RegMIPS32::Reg_V0);
      _mov(Reg, Src0F);
      break;
    }
    case IceType_i64: {
      Src0 = legalizeUndef(Src0);
      Variable *R0 = legalizeToReg(loOperand(Src0), RegMIPS32::Reg_V0);
      Variable *R1 = legalizeToReg(hiOperand(Src0), RegMIPS32::Reg_V1);
      Reg = R0;
      Context.insert<InstFakeUse>(R1);
      break;
    }
    default:
      UnimplementedLoweringError(this, Instr);
    }
  }
  _ret(getPhysicalRegister(RegMIPS32::Reg_RA), Reg);
}

void TargetMIPS32::lowerSelect(const InstSelect *Instr) {
  Variable *Dest = Instr->getDest();
  const Type DestTy = Dest->getType();

  if (DestTy == IceType_i64 || isVectorType(DestTy)) {
    UnimplementedLoweringError(this, Instr);
    return;
  }

  Variable *DestR = legalizeToReg(Dest);
  Variable *SrcTR = legalizeToReg(Instr->getTrueOperand());
  Variable *SrcFR = legalizeToReg(Instr->getFalseOperand());

  Variable *ConditionR = legalizeToReg(Instr->getCondition());

  assert(Instr->getCondition()->getType() == IceType_i1);

  switch (DestTy) {
  case IceType_i1:
  case IceType_i8:
  case IceType_i16:
  case IceType_i32:
    _movn(SrcFR, SrcTR, ConditionR);
    _mov(DestR, SrcFR);
    _mov(Dest, DestR);
    break;
  case IceType_f32:
    _movn_s(SrcFR, SrcTR, ConditionR);
    _mov(DestR, SrcFR);
    _mov(Dest, DestR);
    break;
  case IceType_f64:
    _movn_d(SrcFR, SrcTR, ConditionR);
    _mov(DestR, SrcFR);
    _mov(Dest, DestR);
    break;
  default:
    UnimplementedLoweringError(this, Instr);
  }
}

void TargetMIPS32::lowerShuffleVector(const InstShuffleVector *Instr) {
  UnimplementedLoweringError(this, Instr);
}

void TargetMIPS32::lowerStore(const InstStore *Instr) {
  Operand *Value = Instr->getData();
  Operand *Addr = Instr->getAddr();
  OperandMIPS32Mem *NewAddr = formMemoryOperand(Addr, Value->getType());
  Type Ty = NewAddr->getType();

  if (Ty == IceType_i64) {
    Value = legalizeUndef(Value);
    Variable *ValueHi = legalizeToReg(hiOperand(Value));
    Variable *ValueLo = legalizeToReg(loOperand(Value));
    _sw(ValueHi, llvm::cast<OperandMIPS32Mem>(hiOperand(NewAddr)));
    _sw(ValueLo, llvm::cast<OperandMIPS32Mem>(loOperand(NewAddr)));
  } else {
    Variable *ValueR = legalizeToReg(Value);
    _sw(ValueR, NewAddr);
  }
}

void TargetMIPS32::doAddressOptStore() {
  Inst *Instr = iteratorToInst(Context.getCur());
  assert(llvm::isa<InstStore>(Instr));
  Operand *Src = Instr->getSrc(0);
  Operand *Addr = Instr->getSrc(1);
  if (OperandMIPS32Mem *Mem =
          formAddressingMode(Src->getType(), Func, Instr, Addr)) {
    Instr->setDeleted();
    Context.insert<InstStore>(Src, Mem);
  }
}

void TargetMIPS32::lowerSwitch(const InstSwitch *Instr) {
  Operand *Src = Instr->getComparison();
  SizeT NumCases = Instr->getNumCases();
  if (Src->getType() == IceType_i64) {
    Src = legalizeUndef(Src);
    Variable *Src0Lo = legalizeToReg(loOperand(Src));
    Variable *Src0Hi = legalizeToReg(hiOperand(Src));
    for (SizeT I = 0; I < NumCases; ++I) {
      Operand *ValueLo = Ctx->getConstantInt32(Instr->getValue(I));
      Operand *ValueHi = Ctx->getConstantInt32(Instr->getValue(I) >> 32);
      CfgNode *TargetTrue = Instr->getLabel(I);
      constexpr CfgNode *NoTarget = nullptr;
      ValueHi = legalizeToReg(ValueHi);
      InstMIPS32Label *IntraLabel = InstMIPS32Label::create(Func, this);
      _br(NoTarget, NoTarget, Src0Hi, ValueHi, IntraLabel,
          CondMIPS32::Cond::NE);
      ValueLo = legalizeToReg(ValueLo);
      _br(NoTarget, TargetTrue, Src0Lo, ValueLo, CondMIPS32::Cond::EQ);
      Context.insert(IntraLabel);
    }
    _br(Instr->getLabelDefault());
    return;
  }
  Variable *SrcVar = legalizeToReg(Src);
  assert(SrcVar->mustHaveReg());
  for (SizeT I = 0; I < NumCases; ++I) {
    Operand *Value = Ctx->getConstantInt32(Instr->getValue(I));
    CfgNode *TargetTrue = Instr->getLabel(I);
    constexpr CfgNode *NoTargetFalse = nullptr;
    Value = legalizeToReg(Value);
    _br(NoTargetFalse, TargetTrue, SrcVar, Value, CondMIPS32::Cond::EQ);
  }
  _br(Instr->getLabelDefault());
}

void TargetMIPS32::lowerBreakpoint(const InstBreakpoint *Instr) {
  UnimplementedLoweringError(this, Instr);
}

void TargetMIPS32::lowerUnreachable(const InstUnreachable *Instr) {
  UnimplementedLoweringError(this, Instr);
}

// Turn an i64 Phi instruction into a pair of i32 Phi instructions, to preserve
// integrity of liveness analysis. Undef values are also turned into zeroes,
// since loOperand() and hiOperand() don't expect Undef input.
void TargetMIPS32::prelowerPhis() {
  PhiLowering::prelowerPhis32Bit<TargetMIPS32>(this, Context.getNode(), Func);
}

void TargetMIPS32::postLower() {
  if (Func->getOptLevel() == Opt_m1)
    return;
  // TODO(rkotler): Find two-address non-SSA instructions where Dest==Src0,
  // and set the IsDestRedefined flag to keep liveness analysis consistent.
  UnimplementedError(getFlags());
}

void TargetMIPS32::makeRandomRegisterPermutation(
    llvm::SmallVectorImpl<RegNumT> &Permutation,
    const SmallBitVector &ExcludeRegisters, uint64_t Salt) const {
  (void)Permutation;
  (void)ExcludeRegisters;
  (void)Salt;
  UnimplementedError(getFlags());
}

/* TODO(jvoung): avoid duplicate symbols with multiple targets.
void ConstantUndef::emitWithoutDollar(GlobalContext *) const {
  llvm_unreachable("Not expecting to emitWithoutDollar undef");
}

void ConstantUndef::emit(GlobalContext *) const {
  llvm_unreachable("undef value encountered by emitter.");
}
*/

TargetDataMIPS32::TargetDataMIPS32(GlobalContext *Ctx)
    : TargetDataLowering(Ctx) {}

void TargetDataMIPS32::lowerGlobals(const VariableDeclarationList &Vars,
                                    const std::string &SectionSuffix) {
  const bool IsPIC = getFlags().getUseNonsfi();
  switch (getFlags().getOutFileType()) {
  case FT_Elf: {
    ELFObjectWriter *Writer = Ctx->getObjectWriter();
    Writer->writeDataSection(Vars, llvm::ELF::R_MIPS_GLOB_DAT, SectionSuffix,
                             IsPIC);
  } break;
  case FT_Asm:
  case FT_Iasm: {
    OstreamLocker L(Ctx);
    for (const VariableDeclaration *Var : Vars) {
      if (getFlags().matchTranslateOnly(Var->getName(), 0)) {
        emitGlobal(*Var, SectionSuffix);
      }
    }
  } break;
  }
}

void TargetDataMIPS32::lowerConstants() {
  if (getFlags().getDisableTranslation())
    return;
}

void TargetDataMIPS32::lowerJumpTables() {
  if (getFlags().getDisableTranslation())
    return;
}

// Helper for legalize() to emit the right code to lower an operand to a
// register of the appropriate type.
Variable *TargetMIPS32::copyToReg(Operand *Src, RegNumT RegNum) {
  Type Ty = Src->getType();
  Variable *Reg = makeReg(Ty, RegNum);
  if (isVectorType(Ty)) {
    UnimplementedError(getFlags());
  } else {
    if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(Src)) {
      _lw(Reg, Mem);
    } else {
      _mov(Reg, Src);
    }
  }
  return Reg;
}

Operand *TargetMIPS32::legalize(Operand *From, LegalMask Allowed,
                                RegNumT RegNum) {
  Type Ty = From->getType();
  // Assert that a physical register is allowed.  To date, all calls
  // to legalize() allow a physical register. Legal_Flex converts
  // registers to the right type OperandMIPS32FlexReg as needed.
  assert(Allowed & Legal_Reg);

  if (RegNum.hasNoValue()) {
    if (Variable *Subst = getContext().availabilityGet(From)) {
      // At this point we know there is a potential substitution available.
      if (!Subst->isRematerializable() && Subst->mustHaveReg() &&
          !Subst->hasReg()) {
        // At this point we know the substitution will have a register.
        if (From->getType() == Subst->getType()) {
          // At this point we know the substitution's register is compatible.
          return Subst;
        }
      }
    }
  }

  // Go through the various types of operands:
  // OperandMIPS32Mem, Constant, and Variable.
  // Given the above assertion, if type of operand is not legal
  // (e.g., OperandMIPS32Mem and !Legal_Mem), we can always copy
  // to a register.
  if (auto *Mem = llvm::dyn_cast<OperandMIPS32Mem>(From)) {
    // Base must be in a physical register.
    Variable *Base = Mem->getBase();
    ConstantInteger32 *Offset = llvm::cast<ConstantInteger32>(Mem->getOffset());
    Variable *RegBase = nullptr;
    assert(Base);

    RegBase = llvm::cast<Variable>(
        legalize(Base, Legal_Reg | Legal_Rematerializable));

    if (Offset != nullptr && Offset->getValue() != 0) {
      static constexpr bool ZeroExt = false;
      if (!OperandMIPS32Mem::canHoldOffset(Ty, ZeroExt, Offset->getValue())) {
        llvm::report_fatal_error("Invalid memory offset.");
      }
    }

    // Create a new operand if there was a change.
    if (Base != RegBase) {
      Mem = OperandMIPS32Mem::create(Func, Ty, RegBase, Offset,
                                     Mem->getAddrMode());
    }

    if (Allowed & Legal_Mem) {
      From = Mem;
    } else {
      Variable *Reg = makeReg(Ty, RegNum);
      _lw(Reg, Mem);
      From = Reg;
    }
    return From;
  }

  if (llvm::isa<Constant>(From)) {
    if (auto *C = llvm::dyn_cast<ConstantRelocatable>(From)) {
      (void)C;
      // TODO(reed kotler): complete this case for proper implementation
      Variable *Reg = makeReg(Ty, RegNum);
      Context.insert<InstFakeDef>(Reg);
      return Reg;
    } else if (auto *C32 = llvm::dyn_cast<ConstantInteger32>(From)) {
      const uint32_t Value = C32->getValue();
      // Check if the immediate will fit in a Flexible second operand,
      // if a Flexible second operand is allowed. We need to know the exact
      // value, so that rules out relocatable constants.
      // Also try the inverse and use MVN if possible.
      // Do a movw/movt to a register.
      Variable *Reg;
      if (RegNum.hasValue())
        Reg = getPhysicalRegister(RegNum);
      else
        Reg = makeReg(Ty, RegNum);
      if (isInt<16>(int32_t(Value))) {
        Variable *Zero = getPhysicalRegister(RegMIPS32::Reg_ZERO, Ty);
        Context.insert<InstFakeDef>(Zero);
        _addiu(Reg, Zero, Value);
      } else {
        uint32_t UpperBits = (Value >> 16) & 0xFFFF;
        (void)UpperBits;
        uint32_t LowerBits = Value & 0xFFFF;
        Variable *TReg = makeReg(Ty, RegNum);
        if (LowerBits) {
          _lui(TReg, Ctx->getConstantInt32(UpperBits));
          _ori(Reg, TReg, LowerBits);
        } else {
          _lui(Reg, Ctx->getConstantInt32(UpperBits));
        }
      }
      return Reg;
    } else if (isScalarFloatingType(Ty)) {
      // Load floats/doubles from literal pool.
      auto *CFrom = llvm::cast<Constant>(From);
      assert(CFrom->getShouldBePooled());
      Constant *Offset = Ctx->getConstantSym(0, CFrom->getLabelName());
      Variable *TReg1 = makeReg(getPointerType());
      Variable *TReg2 = makeReg(Ty);
      Context.insert<InstFakeDef>(TReg2);
      _lui(TReg1, Offset, RO_Hi);
      OperandMIPS32Mem *Addr =
          OperandMIPS32Mem::create(Func, Ty, TReg1, Offset);
      if (Ty == IceType_f32)
        _lwc1(TReg2, Addr, RO_Lo);
      else
        _ldc1(TReg2, Addr, RO_Lo);
      return copyToReg(TReg2, RegNum);
    }
  }

  if (auto *Var = llvm::dyn_cast<Variable>(From)) {
    if (Var->isRematerializable()) {
      if (Allowed & Legal_Rematerializable) {
        return From;
      }

      Variable *T = makeReg(Var->getType(), RegNum);
      _mov(T, Var);
      return T;
    }
    // Check if the variable is guaranteed a physical register.  This
    // can happen either when the variable is pre-colored or when it is
    // assigned infinite weight.
    bool MustHaveRegister = (Var->hasReg() || Var->mustHaveReg());
    // We need a new physical register for the operand if:
    //   Mem is not allowed and Var isn't guaranteed a physical
    //   register, or
    //   RegNum is required and Var->getRegNum() doesn't match.
    if ((!(Allowed & Legal_Mem) && !MustHaveRegister) ||
        (RegNum.hasValue() && RegNum != Var->getRegNum())) {
      From = copyToReg(From, RegNum);
    }
    return From;
  }
  return From;
}

namespace BoolFolding {
// TODO(sagar.thakur): Add remaining instruction kinds to shouldTrackProducer()
// and isValidConsumer()
bool shouldTrackProducer(const Inst &Instr) {
  return Instr.getKind() == Inst::Icmp;
}

bool isValidConsumer(const Inst &Instr) { return Instr.getKind() == Inst::Br; }
} // end of namespace BoolFolding

void TargetMIPS32::ComputationTracker::recordProducers(CfgNode *Node) {
  for (Inst &Instr : Node->getInsts()) {
    if (Instr.isDeleted())
      continue;
    // Check whether Instr is a valid producer.
    Variable *Dest = Instr.getDest();
    if (Dest // only consider instructions with an actual dest var; and
        && Dest->getType() == IceType_i1 // only bool-type dest vars; and
        && BoolFolding::shouldTrackProducer(Instr)) { // white-listed instr.
      KnownComputations.emplace(Dest->getIndex(),
                                ComputationEntry(&Instr, IceType_i1));
    }
    // Check each src variable against the map.
    FOREACH_VAR_IN_INST(Var, Instr) {
      SizeT VarNum = Var->getIndex();
      auto ComputationIter = KnownComputations.find(VarNum);
      if (ComputationIter == KnownComputations.end()) {
        continue;
      }

      ++ComputationIter->second.NumUses;
      switch (ComputationIter->second.ComputationType) {
      default:
        KnownComputations.erase(VarNum);
        continue;
      case IceType_i1:
        if (!BoolFolding::isValidConsumer(Instr)) {
          KnownComputations.erase(VarNum);
          continue;
        }
        break;
      }

      if (Instr.isLastUse(Var)) {
        ComputationIter->second.IsLiveOut = false;
      }
    }
  }

  for (auto Iter = KnownComputations.begin(), End = KnownComputations.end();
       Iter != End;) {
    // Disable the folding if its dest may be live beyond this block.
    if (Iter->second.IsLiveOut || Iter->second.NumUses > 1) {
      Iter = KnownComputations.erase(Iter);
      continue;
    }

    // Mark as "dead" rather than outright deleting. This is so that other
    // peephole style optimizations during or before lowering have access to
    // this instruction in undeleted form. See for example
    // tryOptimizedCmpxchgCmpBr().
    Iter->second.Instr->setDead();
    ++Iter;
  }
}

TargetHeaderMIPS32::TargetHeaderMIPS32(GlobalContext *Ctx)
    : TargetHeaderLowering(Ctx) {}

void TargetHeaderMIPS32::lower() {
  OstreamLocker L(Ctx);
  Ostream &Str = Ctx->getStrEmit();
  Str << "\t.set\t"
      << "nomicromips\n";
  Str << "\t.set\t"
      << "nomips16\n";
}

SmallBitVector TargetMIPS32::TypeToRegisterSet[RCMIPS32_NUM];
SmallBitVector TargetMIPS32::TypeToRegisterSetUnfiltered[RCMIPS32_NUM];
SmallBitVector TargetMIPS32::RegisterAliases[RegMIPS32::Reg_NUM];

} // end of namespace MIPS32
} // end of namespace Ice