Rebased PNaCl localmods in LLVM to 223109

lib/Transforms/NaCl/ExpandLargeIntegers.cpp

Index: lib/Transforms/NaCl/ExpandLargeIntegers.cpp
diff --git a/lib/Transforms/NaCl/ExpandLargeIntegers.cpp b/lib/Transforms/NaCl/ExpandLargeIntegers.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..9fb3a13d28016845f3774b689701ac94eb1252ba
--- /dev/null
+++ b/lib/Transforms/NaCl/ExpandLargeIntegers.cpp
@@ -0,0 +1,616 @@
+//===- 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 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 {
+    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();
+}