ExpandLargeIntegers.cpp

//===- ExpandLargeIntegers.cpp - Expand illegal integers for PNaCl ABI ----===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
// A limited set of transformations to expand illegal-sized int types.
//
//===----------------------------------------------------------------------===//
//
// Legal sizes for the purposes of expansion are anything 64 bits or less.
// Operations on large integers are split into operations on smaller-sized
// integers. The low parts should always be powers of 2, but the high parts may
// not be. A subsequent pass can promote those. For now this pass only intends
// to support the uses generated by clang, which is basically just for large
// bitfields.
//
// Limitations:
// 1) It can't change function signatures or global variables.
// 3) Doesn't support mul, div/rem, switch.
// 4) Doesn't handle arrays or structs (or GEPs) with illegal types.
// 5) Doesn't handle constant expressions (it also doesn't produce them, so it
//    can run after ExpandConstantExpr).
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/NaCl.h"

using namespace llvm;

#define DEBUG_TYPE "nacl-expand-ints"

// Break instructions up into no larger than 64-bit chunks.
static const unsigned kChunkBits = 64;
static const unsigned kChunkBytes = kChunkBits / CHAR_BIT;

namespace {
class ExpandLargeIntegers : public FunctionPass {
public:
  static char ID;
  ExpandLargeIntegers() : FunctionPass(ID) {
    initializeExpandLargeIntegersPass(*PassRegistry::getPassRegistry());
  }
  bool runOnFunction(Function &F) override;
};

template <typename T> struct LoHiPair {
  T Lo, Hi;
  LoHiPair() : Lo(), Hi() {}
  LoHiPair(T Lo, T Hi) : Lo(Lo), Hi(Hi) {}
};
template <typename T> struct LoHiBitTriple {
  T Lo, Hi, Bit;
  LoHiBitTriple() : Lo(), Hi(), Bit() {}
  LoHiBitTriple(T Lo, T Hi, T Bit) : Lo(Lo), Hi(Hi), Bit(Bit) {}
};
typedef LoHiPair<IntegerType *> TypePair;
typedef LoHiPair<Value *> ValuePair;
typedef LoHiPair<unsigned> AlignPair;
typedef LoHiBitTriple<Value *> ValueTriple;

// Information needed to patch a phi node which forward-references a value.
struct ForwardPHI {
  Value *Val;
  PHINode *Lo, *Hi;
  unsigned ValueNumber;
  ForwardPHI(Value *Val, PHINode *Lo, PHINode *Hi, unsigned ValueNumber)
      : Val(Val), Lo(Lo), Hi(Hi), ValueNumber(ValueNumber) {}
};
}

char ExpandLargeIntegers::ID = 0;
INITIALIZE_PASS(ExpandLargeIntegers, "nacl-expand-ints",
                "Expand integer types that are illegal in PNaCl", false, false)

#define DIE_IF(COND, VAL, MSG)                                                 \
  do {                                                                         \
    if (COND) {                                                                \
      errs() << "Unsupported: " << *(VAL) << '\n';                             \
      report_fatal_error(                                                      \
          MSG " not yet supported for integer types larger than 64 bits");     \
    }                                                                          \
  } while (0)

static bool isLegalBitSize(unsigned Bits) {
  assert(Bits && "Can't have zero-size integers");
  return Bits <= kChunkBits;
}

static TypePair getExpandedIntTypes(Type *Ty) {
  unsigned BitWidth = Ty->getIntegerBitWidth();
  assert(!isLegalBitSize(BitWidth));
  return {IntegerType::get(Ty->getContext(), kChunkBits),
          IntegerType::get(Ty->getContext(), BitWidth - kChunkBits)};
}

// Return true if Val is an int which should be converted.
static bool shouldConvert(const Value *Val) {
  Type *Ty = Val->getType();
  if (IntegerType *ITy = dyn_cast<IntegerType>(Ty))
    return !isLegalBitSize(ITy->getBitWidth());
  return false;
}

// Return a pair of constants expanded from C.
static ValuePair expandConstant(Constant *C) {
  assert(shouldConvert(C));
  TypePair ExpandedTypes = getExpandedIntTypes(C->getType());
  if (isa<UndefValue>(C)) {
    return {UndefValue::get(ExpandedTypes.Lo),
            UndefValue::get(ExpandedTypes.Hi)};
  } else if (ConstantInt *CInt = dyn_cast<ConstantInt>(C)) {
    Constant *ShiftAmt = ConstantInt::get(
        CInt->getType(), ExpandedTypes.Lo->getBitWidth(), false);
    return {ConstantExpr::getTrunc(CInt, ExpandedTypes.Lo),
            ConstantExpr::getTrunc(ConstantExpr::getLShr(CInt, ShiftAmt),
                                   ExpandedTypes.Hi)};
  }
  DIE_IF(true, C, "Constant value");
}

template <typename T>
static AlignPair getAlign(const DataLayout &DL, T *I, Type *PrefAlignTy) {
  unsigned LoAlign = I->getAlignment();
  if (LoAlign == 0)
    LoAlign = DL.getPrefTypeAlignment(PrefAlignTy);
  unsigned HiAlign = MinAlign(LoAlign, kChunkBytes);
  return {LoAlign, HiAlign};
}

static ValuePair createBit(IRBuilder<> *IRB, const BinaryOperator *Binop,
                           const ValuePair &Lhs, const ValuePair &Rhs,
                           const TypePair &Tys, const StringRef &Name) {
  auto Op = Binop->getOpcode();
  Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo"));
  Value *Hi = IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi"));
  return {Lo, Hi};
}

static ValuePair createShl(IRBuilder<> *IRB, const BinaryOperator *Binop,
                           const ValuePair &Lhs, const ValuePair &Rhs,
                           const TypePair &Tys, const StringRef &Name) {
  ConstantInt *ShlAmount = dyn_cast<ConstantInt>(Rhs.Lo);
  // TODO(dschuff): Expansion of variable-sized shifts isn't supported
  // because the behavior depends on whether the shift amount is less than
  // the size of the low part of the expanded type, and I haven't yet
  // figured out a way to do it for variable-sized shifts without splitting
  // the basic block. I don't believe it's actually necessary for
  // bitfields. Likewise for LShr below.
  DIE_IF(!ShlAmount, Binop, "Expansion of variable-sized shifts");
  unsigned ShiftAmount = ShlAmount->getZExtValue();
  if (ShiftAmount >= Binop->getType()->getIntegerBitWidth())
    ShiftAmount = 0; // Undefined behavior.
  unsigned HiBits = Tys.Hi->getIntegerBitWidth();
  // |<------------Hi---------->|<-------Lo------>|
  // |                          |                 |
  // +--------+--------+--------+--------+--------+
  // |abcdefghijklmnopqrstuvwxyz|ABCDEFGHIJKLMNOPQ|
  // +--------+--------+--------+--------+--------+
  // Possible shifts:
  // |efghijklmnopqrstuvwxyzABCD|EFGHIJKLMNOPQ0000| Some Lo into Hi.
  // |vwxyzABCDEFGHIJKLMNOPQ0000|00000000000000000| Lo is 0, keep some Hi.
  // |DEFGHIJKLMNOPQ000000000000|00000000000000000| Lo is 0, no Hi left.
  Value *Lo, *Hi;
  if (ShiftAmount < kChunkBits) {
    Lo = IRB->CreateShl(Lhs.Lo, ShiftAmount, Twine(Name, ".lo"));
    Hi =
        IRB->CreateZExtOrTrunc(IRB->CreateLShr(Lhs.Lo, kChunkBits - ShiftAmount,
                                               Twine(Name, ".lo.shr")),
                               Tys.Hi, Twine(Name, ".lo.ext"));
  } else {
    Lo = ConstantInt::get(Tys.Lo, 0);
    Hi = IRB->CreateShl(
        IRB->CreateZExtOrTrunc(Lhs.Lo, Tys.Hi, Twine(Name, ".lo.ext")),
        ShiftAmount - kChunkBits, Twine(Name, ".lo.shl"));
  }
  if (ShiftAmount < HiBits)
    Hi = IRB->CreateOr(
        Hi, IRB->CreateShl(Lhs.Hi, ShiftAmount, Twine(Name, ".hi.shl")),
        Twine(Name, ".or"));
  return {Lo, Hi};
}

static ValuePair createShr(IRBuilder<> *IRB, const BinaryOperator *Binop,
                           const ValuePair &Lhs, const ValuePair &Rhs,
                           const TypePair &Tys, const StringRef &Name) {
  auto Op = Binop->getOpcode();
  ConstantInt *ShrAmount = dyn_cast<ConstantInt>(Rhs.Lo);
  // TODO(dschuff): Expansion of variable-sized shifts isn't supported
  // because the behavior depends on whether the shift amount is less than
  // the size of the low part of the expanded type, and I haven't yet
  // figured out a way to do it for variable-sized shifts without splitting
  // the basic block. I don't believe it's actually necessary for bitfields.
  DIE_IF(!ShrAmount, Binop, "Expansion of variable-sized shifts");
  bool IsArith = Op == Instruction::AShr;
  unsigned ShiftAmount = ShrAmount->getZExtValue();
  if (ShiftAmount >= Binop->getType()->getIntegerBitWidth())
    ShiftAmount = 0; // Undefined behavior.
  unsigned HiBitWidth = Tys.Hi->getIntegerBitWidth();
  // |<--Hi-->|<-------Lo------>|
  // |        |                 |
  // +--------+--------+--------+
  // |abcdefgh|ABCDEFGHIJKLMNOPQ|
  // +--------+--------+--------+
  // Possible shifts (0 is sign when doing AShr):
  // |0000abcd|defgABCDEFGHIJKLM| Some Hi into Lo.
  // |00000000|00abcdefgABCDEFGH| Hi is 0, keep some Lo.
  // |00000000|000000000000abcde| Hi is 0, no Lo left.
  Value *Lo, *Hi;
  if (ShiftAmount < kChunkBits) {
    Lo = IRB->CreateShl(
        IsArith
            ? IRB->CreateSExtOrTrunc(Lhs.Hi, Tys.Lo, Twine(Name, ".hi.ext"))
            : IRB->CreateZExtOrTrunc(Lhs.Hi, Tys.Lo, Twine(Name, ".hi.ext")),
        kChunkBits - ShiftAmount, Twine(Name, ".hi.shl"));
    Lo = IRB->CreateOr(
        Lo, IRB->CreateLShr(Lhs.Lo, ShiftAmount, Twine(Name, ".lo.shr")),
        Twine(Name, ".lo"));
  } else {
    Lo = IRB->CreateBinOp(Op, Lhs.Hi,
                          ConstantInt::get(Tys.Hi, ShiftAmount - kChunkBits),
                          Twine(Name, ".hi.shr"));
    Lo = IsArith ? IRB->CreateSExtOrTrunc(Lo, Tys.Lo, Twine(Name, ".lo.ext"))
                 : IRB->CreateZExtOrTrunc(Lo, Tys.Lo, Twine(Name, ".lo.ext"));
  }
  if (ShiftAmount < HiBitWidth) {
    Hi = IRB->CreateBinOp(Op, Lhs.Hi, ConstantInt::get(Tys.Hi, ShiftAmount),
                          Twine(Name, ".hi"));
  } else {
    Hi = IsArith ? IRB->CreateAShr(Lhs.Hi, HiBitWidth - 1, Twine(Name, ".hi"))
                 : ConstantInt::get(Tys.Hi, 0);
  }
  return {Lo, Hi};
}

static Value *createCarry(IRBuilder<> *IRB, Value *Lhs, Value *Rhs,
                          Value *Added, Type *Ty, const StringRef &Name) {
  return IRB->CreateZExt(
      IRB->CreateICmpULT(
          Added,
          IRB->CreateSelect(IRB->CreateICmpULT(Lhs, Rhs, Twine(Name, ".cmp")),
                            Rhs, Lhs, Twine(Name, ".limit")),
          Twine(Name, ".overflowed")),
      Ty, Twine(Name, ".carry"));
}

static ValueTriple createAdd(IRBuilder<> *IRB, const ValuePair &Lhs,
                             const ValuePair &Rhs, const TypePair &Tys,
                             const StringRef &Name, Type *HiCarryTy) {
  auto Op = Instruction::Add;
  // Don't propagate NUW/NSW to the lo operation: it can overflow.
  Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo"));
  Value *LoCarry = createCarry(IRB, Lhs.Lo, Rhs.Lo, Lo, Tys.Hi, Name);
  // TODO(jfb) The hi operation could be tagged with NUW/NSW.
  Value *HiAdd = IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi"));
  Value *Hi = IRB->CreateBinOp(Op, HiAdd, LoCarry, Twine(Name, ".carried"));
  Value *HiCarry = HiCarryTy
                       ? createCarry(IRB, Lhs.Hi, Rhs.Hi, Hi, HiCarryTy, Name)
                       : nullptr;
  return {Lo, Hi, HiCarry};
}

static ValuePair createSub(IRBuilder<> *IRB, const ValuePair &Lhs,
                           const ValuePair &Rhs, const TypePair &Tys,
                           const StringRef &Name) {
  auto Op = Instruction::Sub;
  Value *Borrowed = IRB->CreateSExt(
      IRB->CreateICmpULT(Lhs.Lo, Rhs.Lo, Twine(Name, ".borrow")), Tys.Hi,
      Twine(Name, ".borrowing"));
  Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo"));
  Value *Hi =
      IRB->CreateBinOp(Instruction::Add,
                       IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi")),
                       Borrowed, Twine(Name, ".borrowed"));
  return {Lo, Hi};
}

static Value *createICmpEquality(IRBuilder<> *IRB, CmpInst::Predicate Pred,
                                 const ValuePair &Lhs, const ValuePair &Rhs,
                                 const StringRef &Name) {
  assert(Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE);
  Value *Lo = IRB->CreateICmp(Pred, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo"));
  Value *Hi = IRB->CreateICmp(Pred, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi"));
  return IRB->CreateBinOp(
      Instruction::And, Lo, Hi,
      Twine(Name, Pred == CmpInst::ICMP_EQ ? ".eq" : ".ne"));
}

static Value *createICmp(IRBuilder<> *IRB, const ICmpInst *ICmp,
                         const ValuePair &Lhs, const ValuePair &Rhs,
                         const TypePair &Tys, const StringRef &Name) {
  auto Pred = ICmp->getPredicate();
  switch (Pred) {
  case CmpInst::ICMP_EQ:
  case CmpInst::ICMP_NE:
    return createICmpEquality(IRB, ICmp->getPredicate(), Lhs, Rhs, Name);

  case CmpInst::ICMP_UGT: // C == 1 and Z == 0
  case CmpInst::ICMP_UGE: // C == 1
  case CmpInst::ICMP_ULT: // C == 0 and Z == 0
  case CmpInst::ICMP_ULE: // C == 0
  {
    Value *Carry = createAdd(IRB, Lhs, Rhs, Tys, Name, ICmp->getType()).Bit;
    if (Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE)
      Carry = IRB->CreateNot(Carry, Name);
    if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_ULT)
      Carry = IRB->CreateBinOp(
          Instruction::And, Carry,
          createICmpEquality(IRB, CmpInst::ICMP_EQ, Lhs, Rhs, Name), Name);
    return Carry;
  }

  case CmpInst::ICMP_SGT: // N == V and Z == 0
  case CmpInst::ICMP_SGE: // N == V
  case CmpInst::ICMP_SLT: // N != V
  case CmpInst::ICMP_SLE: // N != V or Z == 1
    DIE_IF(true, ICmp, "Signed comparisons");
  default:
    llvm_unreachable("Invalid integer comparison");
  }
}

static ValuePair createLoad(IRBuilder<> *IRB, const DataLayout &DL,
                            LoadInst *Load) {
  DIE_IF(!Load->isSimple(), Load, "Volatile and atomic loads");
  Value *Op = Load->getPointerOperand();
  TypePair Tys = getExpandedIntTypes(Load->getType());
  AlignPair Align = getAlign(DL, Load, Load->getType());
  Value *Loty = IRB->CreateBitCast(Op, Tys.Lo->getPointerTo(),
                                   Twine(Op->getName(), ".loty"));
  Value *Lo =
      IRB->CreateAlignedLoad(Loty, Align.Lo, Twine(Load->getName(), ".lo"));
  Value *HiAddr =
      IRB->CreateConstGEP1_32(Loty, 1, Twine(Op->getName(), ".hi.gep"));
  Value *HiTy = IRB->CreateBitCast(HiAddr, Tys.Hi->getPointerTo(),
                                   Twine(Op->getName(), ".hity"));
  Value *Hi =
      IRB->CreateAlignedLoad(HiTy, Align.Hi, Twine(Load->getName(), ".hi"));
  return {Lo, Hi};
}

static ValuePair createStore(IRBuilder<> *IRB, const DataLayout &DL,
                             StoreInst *Store, const ValuePair &StoreVals) {
  DIE_IF(!Store->isSimple(), Store, "Volatile and atomic stores");
  Value *Ptr = Store->getPointerOperand();
  TypePair Tys = getExpandedIntTypes(Store->getValueOperand()->getType());
  AlignPair Align = getAlign(DL, Store, Store->getValueOperand()->getType());
  Value *Loty = IRB->CreateBitCast(Ptr, Tys.Lo->getPointerTo(),
                                   Twine(Ptr->getName(), ".loty"));
  Value *Lo = IRB->CreateAlignedStore(StoreVals.Lo, Loty, Align.Lo);
  Value *HiAddr =
      IRB->CreateConstGEP1_32(Loty, 1, Twine(Ptr->getName(), ".hi.gep"));
  Value *HiTy = IRB->CreateBitCast(HiAddr, Tys.Hi->getPointerTo(),
                                   Twine(Ptr->getName(), ".hity"));
  Value *Hi = IRB->CreateAlignedStore(StoreVals.Hi, HiTy, Align.Hi);
  return {Lo, Hi};
}

namespace {
// Holds the state for converting/replacing values. We visit instructions in
// reverse post-order, phis are therefore the only instructions which can be
// visited before the value they use.
class ConversionState {
public:
  // Return the expanded values for Val.
  ValuePair getConverted(Value *Val) {
    assert(shouldConvert(Val));
    // Directly convert constants.
    if (Constant *C = dyn_cast<Constant>(Val))
      return expandConstant(C);
    if (RewrittenIllegals.count(Val)) {
      ValuePair Found = RewrittenIllegals[Val];
      if (RewrittenLegals.count(Found.Lo))
        Found.Lo = RewrittenLegals[Found.Lo];
      if (RewrittenLegals.count(Found.Hi))
        Found.Hi = RewrittenLegals[Found.Hi];
      return Found;
    }
    errs() << "Value: " << *Val << "\n";
    report_fatal_error("Expanded value not found in map");
  }

  // Returns whether a converted value has been recorded. This is only useful
  // for phi instructions: they can be encountered before the incoming
  // instruction, whereas RPO order guarantees that other instructions always
  // use converted values.
  bool hasConverted(Value *Val) {
    assert(shouldConvert(Val));
    return dyn_cast<Constant>(Val) || RewrittenIllegals.count(Val);
  }

  // Record a forward phi, temporarily setting it to use Undef. This will be
  // patched up at the end of RPO.
  ValuePair recordForwardPHI(Value *Val, PHINode *Lo, PHINode *Hi,
                             unsigned ValueNumber) {
    DEBUG(dbgs() << "\tRecording as forward PHI\n");
    ForwardPHIs.push_back(ForwardPHI(Val, Lo, Hi, ValueNumber));
    return {UndefValue::get(Lo->getType()), UndefValue::get(Hi->getType())};
  }

  void recordConverted(Instruction *From, const ValuePair &To) {
    DEBUG(dbgs() << "\tTo:  " << *To.Lo << "\n");
    DEBUG(dbgs() << "\tAnd: " << *To.Hi << "\n");
    ToErase.push_back(From);
    RewrittenIllegals[From] = To;
  }

  // Replace the uses of From with To, give From's name to To, and mark To for
  // deletion.
  void recordConverted(Instruction *From, Value *To) {
    assert(!shouldConvert(From));
    DEBUG(dbgs() << "\tTo:  " << *To << "\n");
    ToErase.push_back(From);
    // From does not produce an illegal value, update its users in place.
    From->replaceAllUsesWith(To);
    To->takeName(From);
    RewrittenLegals[From] = To;
  }

  void recordToErase(Instruction *TE) {
    ToErase.push_back(TE);
  }

  void patchForwardPHIs() {
    DEBUG(if (!ForwardPHIs.empty()) dbgs() << "Patching forward PHIs:\n");
    for (ForwardPHI &F : ForwardPHIs) {
      ValuePair Ops = getConverted(F.Val);
      F.Lo->setIncomingValue(F.ValueNumber, Ops.Lo);
      F.Hi->setIncomingValue(F.ValueNumber, Ops.Hi);
      DEBUG(dbgs() << "\t" << *F.Lo << "\n\t" << *F.Hi << "\n");
    }
  }

  void eraseReplacedInstructions() {
    for (Instruction *I : ToErase)
      I->dropAllReferences();
    for (Instruction *I : ToErase)
      I->eraseFromParent();
  }

private:
  // Maps illegal values to their new converted lo/hi values.
  DenseMap<Value *, ValuePair> RewrittenIllegals;
  // Maps legal values to their new converted value.
  DenseMap<Value *, Value *> RewrittenLegals;
  // Illegal values which have already been converted, will be erased.
  SmallVector<Instruction *, 32> ToErase;
  // PHIs which were encountered but had forward references. They need to get
  // patched up after RPO traversal.
  SmallVector<ForwardPHI, 32> ForwardPHIs;
};
} // Anonymous namespace

static void convertInstruction(Instruction *Inst, ConversionState &State,
                               const DataLayout &DL) {
  DEBUG(dbgs() << "Expanding Large Integer: " << *Inst << "\n");
  // Set the insert point *after* Inst, so that any instructions inserted here
  // will be visited again. That allows iterative expansion of types > i128.
  BasicBlock::iterator InsertPos(Inst);
  IRBuilder<> IRB(&*++InsertPos);
  StringRef Name = Inst->getName();

  if (PHINode *Phi = dyn_cast<PHINode>(Inst)) {
    unsigned N = Phi->getNumIncomingValues();
    TypePair OpTys = getExpandedIntTypes(Phi->getIncomingValue(0)->getType());
    PHINode *Lo = IRB.CreatePHI(OpTys.Lo, N, Twine(Name + ".lo"));
    PHINode *Hi = IRB.CreatePHI(OpTys.Hi, N, Twine(Name + ".hi"));
    for (unsigned I = 0; I != N; ++I) {
      Value *InVal = Phi->getIncomingValue(I);
      BasicBlock *InBB = Phi->getIncomingBlock(I);
      // If the value hasn't already been converted then this is a
      // forward-reference PHI which needs to be patched up after RPO traversal.
      ValuePair Ops = State.hasConverted(InVal)
                          ? State.getConverted(InVal)
                          : State.recordForwardPHI(InVal, Lo, Hi, I);
      Lo->addIncoming(Ops.Lo, InBB);
      Hi->addIncoming(Ops.Hi, InBB);
    }
    State.recordConverted(Phi, {Lo, Hi});

  } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(Inst)) {
    Value *Operand = ZExt->getOperand(0);
    Type *OpTy = Operand->getType();
    TypePair Tys = getExpandedIntTypes(Inst->getType());
    Value *Lo, *Hi;
    if (OpTy->getIntegerBitWidth() <= kChunkBits) {
      Lo = IRB.CreateZExt(Operand, Tys.Lo, Twine(Name, ".lo"));
      Hi = ConstantInt::get(Tys.Hi, 0);
    } else {
      ValuePair Ops = State.getConverted(Operand);
      Lo = Ops.Lo;
      Hi = IRB.CreateZExt(Ops.Hi, Tys.Hi, Twine(Name, ".hi"));
    }
    State.recordConverted(ZExt, {Lo, Hi});

  } else if (TruncInst *Trunc = dyn_cast<TruncInst>(Inst)) {
    Value *Operand = Trunc->getOperand(0);
    assert(shouldConvert(Operand) && "TruncInst is expandable but not its op");
    ValuePair Ops = State.getConverted(Operand);
    if (!shouldConvert(Inst)) {
      Value *NewInst = IRB.CreateTrunc(Ops.Lo, Trunc->getType(), Name);
      State.recordConverted(Trunc, NewInst);
    } else {
      TypePair Tys = getExpandedIntTypes(Trunc->getType());
      assert(Tys.Lo == getExpandedIntTypes(Operand->getType()).Lo);
      Value *Lo = Ops.Lo;
      Value *Hi = IRB.CreateTrunc(Ops.Hi, Tys.Hi, Twine(Name, ".hi"));
      State.recordConverted(Trunc, {Lo, Hi});
    }

  } else if (BinaryOperator *Binop = dyn_cast<BinaryOperator>(Inst)) {
    ValuePair Lhs = State.getConverted(Binop->getOperand(0));
    ValuePair Rhs = State.getConverted(Binop->getOperand(1));
    TypePair Tys = getExpandedIntTypes(Binop->getType());
    ValuePair Conv;
    switch (Binop->getOpcode()) {
    case Instruction::And:
    case Instruction::Or:
    case Instruction::Xor:
      Conv = createBit(&IRB, Binop, Lhs, Rhs, Tys, Name);
      break;
    case Instruction::Shl:
      Conv = createShl(&IRB, Binop, Lhs, Rhs, Tys, Name);
      break;
    case Instruction::AShr:
    case Instruction::LShr:
      Conv = createShr(&IRB, Binop, Lhs, Rhs, Tys, Name);
      break;
    case Instruction::Add: {
      ValueTriple VT =
          createAdd(&IRB, Lhs, Rhs, Tys, Name, /*HiCarryTy=*/nullptr);
      Conv = {VT.Lo, VT.Hi}; // Ignore Hi carry.
    } break;
    case Instruction::Sub:
      Conv = createSub(&IRB, Lhs, Rhs, Tys, Name);
      break;
    default:
      DIE_IF(true, Binop, "Binary operator type");
    }
    State.recordConverted(Binop, Conv);

  } else if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Inst)) {
    ValuePair Lhs = State.getConverted(ICmp->getOperand(0));
    ValuePair Rhs = State.getConverted(ICmp->getOperand(1));
    TypePair Tys = getExpandedIntTypes(ICmp->getOperand(0)->getType());
    State.recordConverted(ICmp, createICmp(&IRB, ICmp, Lhs, Rhs, Tys, Name));

  } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
    State.recordConverted(Load, createLoad(&IRB, DL, Load));

  } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
    ValuePair StoreVals = State.getConverted(Store->getValueOperand());
    State.recordConverted(Store, createStore(&IRB, DL, Store, StoreVals));

  } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) {
    Value *Cond = Select->getCondition();
    ValuePair True = State.getConverted(Select->getTrueValue());
    ValuePair False = State.getConverted(Select->getFalseValue());
    Value *Lo = IRB.CreateSelect(Cond, True.Lo, False.Lo, Twine(Name, ".lo"));
    Value *Hi = IRB.CreateSelect(Cond, True.Hi, False.Hi, Twine(Name, ".hi"));
    State.recordConverted(Select, {Lo, Hi});

  } else if (BitCastInst *BitCast = dyn_cast<BitCastInst>(Inst)) {
    // XXX EMSCRIPTEN handle bitcast <4 x i32|float> or <2 x double> to i128
    Value *Input = BitCast->getOperand(0);
    if (!Input->getType()->isVectorTy()) {
      return; // we can't do anything for it, but see below on trivial casts to i128 and back, it might get handled there
    }
    VectorType *VT = cast<VectorType>(Input->getType());
    Type *ET = VT->getElementType();

    // handle trivial casts to i128 and immediately back
    if (BitCast->hasOneUse()) {
      User* U = *BitCast->user_begin();
      if (BitCastInst *UserBitCast = dyn_cast<BitCastInst>(U)) {
        if (UserBitCast->getType()->isVectorTy()) {
          Value* Direct = Input;
          if (VT != UserBitCast->getType()) {
            Direct = IRB.CreateBitCast(Direct, UserBitCast->getType(), Twine(Name, "dcast"));
          }
          State.recordToErase(BitCast);
          State.recordConverted(UserBitCast, Direct);
          return;
        }
      }
    }

    Type *I32 = Type::getInt32Ty(VT->getContext());

    if (VT->getNumElements() == 4) {
      assert(ET->isIntegerTy(32) || ET->isFloatTy());
      if (ET->isFloatTy()) {
        Input = IRB.CreateBitCast(Input, VectorType::get(I32, 4), Twine(Name, "toint"));
      }
    } else if (VT->getNumElements() == 2) {
      assert(ET->isDoubleTy());
      Input = IRB.CreateBitCast(Input, VectorType::get(I32, 4), Twine(Name, "toint"));
    } else {
      DIE_IF(true, Inst, "BitCast Instruction");
    }

    Value *P0 = IRB.CreateExtractElement(Input, ConstantInt::get(I32, 0), Twine(Name, ".p0"));
    Value *P1 = IRB.CreateExtractElement(Input, ConstantInt::get(I32, 1), Twine(Name, ".p1"));
    Value *P2 = IRB.CreateExtractElement(Input, ConstantInt::get(I32, 2), Twine(Name, ".p2"));
    Value *P3 = IRB.CreateExtractElement(Input, ConstantInt::get(I32, 3), Twine(Name, ".p3"));

    Type *I64 = Type::getInt64Ty(VT->getContext());
    P0 = IRB.CreateZExt(P0, I64, Twine(Name, ".p0.64"));
    P1 = IRB.CreateZExt(P1, I64, Twine(Name, ".p1.64"));
    P2 = IRB.CreateZExt(P2, I64, Twine(Name, ".p2.64"));
    P3 = IRB.CreateZExt(P3, I64, Twine(Name, ".p3.64"));

    Value *Lo = IRB.CreateBinOp(Instruction::BinaryOps::Or, P0, IRB.CreateBinOp(Instruction::BinaryOps::Shl, P1, ConstantInt::get(I64, 32), Twine(Name, ".mid.lo")), Twine(Name, ".lo"));
    Value *Hi = IRB.CreateBinOp(Instruction::BinaryOps::Or, P2, IRB.CreateBinOp(Instruction::BinaryOps::Shl, P3, ConstantInt::get(I64, 32), Twine(Name, ".mid.hi")), Twine(Name, ".hi"));
    State.recordConverted(BitCast, {Lo, Hi});

  } else {
    DIE_IF(true, Inst, "Instruction");
  }
}

bool ExpandLargeIntegers::runOnFunction(Function &F) {
  // Don't support changing the function arguments. Illegal function arguments
  // should not be generated by clang.
  for (const Argument &Arg : F.args())
    if (shouldConvert(&Arg))
      report_fatal_error("Function " + F.getName() +
                         " has illegal integer argument");

  // TODO(jfb) This should loop to handle nested forward PHIs.

  ConversionState State;
  DataLayout DL(F.getParent());
  bool Modified = false;
  ReversePostOrderTraversal<Function *> RPOT(&F);
  for (ReversePostOrderTraversal<Function *>::rpo_iterator FI = RPOT.begin(),
                                                           FE = RPOT.end();
       FI != FE; ++FI) {
    BasicBlock *BB = *FI;
    for (Instruction &I : *BB) {
      // Only attempt to convert an instruction if its result or any of its
      // operands are illegal.
      bool ShouldConvert = shouldConvert(&I);
      for (Value *Op : I.operands())
        ShouldConvert |= shouldConvert(Op);
      if (ShouldConvert) {
        convertInstruction(&I, State, DL);
        Modified = true;
      }
    }
  }
  State.patchForwardPHIs();
  State.eraseReplacedInstructions();
  return Modified;
}

FunctionPass *llvm::createExpandLargeIntegersPass() {
  return new ExpandLargeIntegers();
}