PNaCl ABI: Promote illegal integer types

lib/Transforms/NaCl/PromoteIntegers.cpp

Index: lib/Transforms/NaCl/PromoteIntegers.cpp
diff --git a/lib/Transforms/NaCl/PromoteIntegers.cpp b/lib/Transforms/NaCl/PromoteIntegers.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..529dbf88ac1938310daa89027410d83a4fb1fb7f
--- /dev/null
+++ b/lib/Transforms/NaCl/PromoteIntegers.cpp
@@ -0,0 +1,588 @@
+//===- PromoteIntegers.cpp - Promote 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 promote illegal-sized int types.

[Mark Seaborn, 2013/05/09 01:00:22]

Add //==---... spacer before this, to follow the style

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+// Legal sizes are currently 1, 8, 16, 32, 64 (and higher, see note below)
+// Operations on illegal integers and int pointers are be changed to operate
+// on the next-higher legal size.
+// It always maintains the invariant that the upper bits (above the size of the

[Mark Seaborn, 2013/05/09 01:00:22]

I don't think that's the best choice of invariant, BTW, because only a subset of
operations (div/rem, shr, cmp, switch), care about those upper bits.  The rest
don't (add, mul, sub, and, xor, shl, sext/zext, etc.).

That would mean that if you're doing a series of adds, you'd be unnecessarily
clearing the upper bits after each one.  It would be better to clear the bits
only before the operations that care.  That's what I do in
https://github.com/mseaborn/tiny-llvm-codegen.  However, it was easy to test it
comprehensively in that context. :-)

What you're doing now is valid, and erring on the side of safety.  Maybe it's
worth an explanatory comment if you don't want to change it?

[Derek Schuff, 2013/05/09 18:30:24]

I did think about doing that. For the operations that are actually generated by
clang and SROA (and/or/lshr/shl/trunc/zext), it didn't make much difference 
(I've never seen any arithmetic instructions actually generated). Instcombine
can generated signed icmp which is bad either way, but that's a probably a
pessimization even outside of pnacl, so i'll probably just leave that disabled.
Also I just realized that all the shl operations have the nuw flag which means
we can skip the clear for those.

BTW I think add et al. do actually care about the extra upper bits. If there is
no invariant in place, they could be anything, and could cause the operation in
the promoted type to overflow and change the result in the lower bits.

[Mark Seaborn, 2013/05/09 19:27:48]

FWIW, that's not true.  For addition, digit n in the input (counting from the
least significant digit) can only influence digits >=n in the result.  That
follows from the algorithm for addition, which processes the digits from right
to left.

[Derek Schuff, 2013/05/09 20:19:43]

OK, true.
In any case it doesn't matter for the instructions we actually see, so I think
we can leave it this way for now, and only change it if there becomes a good
reason to in the future.

+// original type) are zero; therefore after operations which can overwrite these
+// bits (e.g. add, shl, sext), the bits are cleared.
+//
+// Limitations:
+// 1) It can't change function signatures or global variables
+// 2) It won't promote (and can't expand) types larger than i64
+// 3) Doesn't support mul/div operators
+// 4) Doesn't handle arrays or structs (or GEPs) with illegal types
+// 5) Doesn't handle constant expressions
+//===----------------------------------------------------------------------===//

[Mark Seaborn, 2013/05/09 01:00:22]

Follow the style here and end comment with:
//
//===----...

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;

[Mark Seaborn, 2013/05/09 01:00:22]

Add empty line after this

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+namespace {
+class PromoteIntegers : public FunctionPass {
+ public:
+  static char ID;
+  PromoteIntegers() : FunctionPass(ID) {
+    initializePromoteIntegersPass(*PassRegistry::getPassRegistry());
+  }
+  virtual bool runOnFunction(Function &F);
+};
+}
+
+char PromoteIntegers::ID = 0;
+INITIALIZE_PASS(PromoteIntegers, "nacl-promote-ints",
+                "Promote integer types which are illegal in PNaCl",
+                false, false)
+
+
+// Legal sizes are currently 1, 8, 16, 32, and 64.
+// We can't yet expand types above 64 bit, so don't try to touch them for now.
+static bool isLegalSize(unsigned Size) {
+  // TODO(dschuff): expand >64bit types or disallow >64bit packed bitfields
+  if (Size > 64) return true;
+  return Size == 1 || Size == 8 || Size == 16 || Size == 32 || Size == 64;
+}
+
+static Type *getPromotedIntType(IntegerType *Ty) {
+  unsigned Width = Ty->getBitWidth();
+  assert(Width <= 64 && "Don't know how to legalize >64 bit types yet");
+  if (isLegalSize(Width))
+    return Ty;
+  return IntegerType::get(Ty->getContext(), NextPowerOf2(Width));

[Mark Seaborn, 2013/05/09 01:00:22]

NextPowerOf2() isn't right for i3, which should be promoted to i8, not i4.  I
don't think you're testing i3...i7 at the moment?

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+}
+
+// Return a legal integer or pointer-to-integer type, promoting to a larger
+// size if necessary.
+static Type *getPromotedType(Type *Ty) {
+  assert((isa<IntegerType>(Ty) || isa<PointerType>(Ty)) &&
+         "Trying to convert a non-integer type");
+
+  if (isa<PointerType>(Ty))
+    return getPromotedIntType(
+        cast<IntegerType>(Ty->getContainedType(0)))->getPointerTo();
+
+  return getPromotedIntType(cast<IntegerType>(Ty));
+}
+
+// Return true if Val is an int or pointer-to-int which should be converted.
+static bool shouldConvert(Value *Val) {
+  Type *Ty = Val->getType();
+  if (PointerType *Pty = dyn_cast<PointerType>(Ty))
+    Ty = Pty->getContainedType(0);
+  if (IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
+    if (!isLegalSize(ITy->getBitWidth())) {
+      return true;
+    }
+  }
+  return false;
+}
+
+// Return a constant which has been promoted to a legal size.
+static Value *convertConstant(Constant *C, bool SignExt=false) {
+  assert(shouldConvert(C));
+  ConstantInt *CInt = cast<ConstantInt>(C);
+  return ConstantInt::get(
+      getPromotedType(cast<IntegerType>(CInt->getType())),
+      SignExt ? CInt->getSExtValue() : CInt->getZExtValue(),
+      /*isSigned=*/SignExt);
+}
+
+// Holds the state for converting/replacing values. Conversion is done in one
+// pass, with each value requiring conversion possibly having two stages. When
+// an instruction needs to be replaced (i.e. it has illegal operands or result)
+// a new instruction is created, and the pass calls getConverted to get its
+// operands. If the original operand has already been converted, the new value
+// is returned. Otherwise, a placeholder is created and used in the new
+// instruction. After a new instruction is created to replace an illegal one,
+// recordConverted is called to register the replacement. All users are updated,
+// and if there is a placeholder, its users are also updated.
+// recordConverted also queues the old value for deletion.
+// This strategy avoids the need for recursion or worklists for conversion.
+class ConversionState {
+ public:
+  // Return the promoted value for Val. If Val has not yet been converted,
+  // return a placeholder, which will be converted later.
+  Value *getConverted(Value *Val) {
+    if (!shouldConvert(Val))
+        return Val;
+    assert(!isa<GlobalVariable>(Val) && "Can't convert GlobalVariables");
+    if (RewrittenMap.count(Val))
+      return RewrittenMap[Val];
+    Value *P;
+    // Directly convert constants.
+    if (Constant *C = dyn_cast<Constant>(Val)) {
+      return convertConstant(C, /*SignExt=*/false);

[jvoung (off chromium), 2013/05/09 00:06:44]

Is it possible to keep constants in RewrittenMap?  I guess not because you later
find that you want a sign extended version instead?

[Derek Schuff, 2013/05/09 18:30:24]

It is possible because the clients that want sign extension get it by explicitly
calling convertConstant and not using getConverted. The first version of this
code did that, it doesn't really matter either way.

+    } else {
+      // No converted value available yet, so create a placeholder.
+      P = new Argument(getPromotedType(Val->getType()));
+    }
+    RewrittenMap[Val] = P;
+    Placeholders[Val] = P;
+    return P;
+  }
+
+  // Replace the uses of From with To, replace the uses of any
+  // placeholders for From, and optionally give From's name to To.
+  // Also mark To for deletion.
+  void recordConverted(Instruction *From, Value *To, bool TakeName=true) {
+    ToErase.push_back(cast<Instruction>(From));

[jvoung (off chromium), 2013/05/09 00:06:44]

do you still need a cast?

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+    if (!shouldConvert(From)) {

[jvoung (off chromium), 2013/05/09 00:06:44]

Haven't read through everything, yet, but it seems odd that it
!shouldConvert(...), yet it will be replaced by To.  Add comment?

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+      From->replaceAllUsesWith(To);
+    } else {
+      if (Placeholders.count(From)) {
+        // Resolve placeholder.
+        Placeholders[From]->replaceAllUsesWith(To);
+        Placeholders.erase(From);
+      }

[jvoung (off chromium), 2013/05/09 00:06:44]

should there be an else {
  From->replaceAllUsesWith(To);
}

it seems like there is still a case where From won't be replaced by To.

[Derek Schuff, 2013/05/09 18:30:24]

added comment

+      RewrittenMap[From] = To;
+    }
+    if (TakeName) {
+      To->takeName(From);
+    }
+  }
+  ~ConversionState() {

[Mark Seaborn, 2013/05/09 01:00:22]

The destructor should come before other methods.  But I'd suggest not doing this
side-effecting in a destructor.  Explicit is better than implicit (except for
classes specifically for RAII cleanup :-) ).

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+    for (SmallVectorImpl<Instruction*>::iterator I = ToErase.begin(),
+             E = ToErase.end(); I != E; ++I)
+      (*I)->dropAllReferences();
+    for (SmallVectorImpl<Instruction*>::iterator I = ToErase.begin(),
+             E = ToErase.end(); I != E; ++I)
+      (*I)->eraseFromParent();
+  }
+ private:
+  // Maps illegal values to their new converted values (or placeholders
+  // if no new value is available yet)
+  DenseMap<Value *, Value *> RewrittenMap;
+  // Maps illegal values with no conversion available yet to their placeholders
+  DenseMap<Value *, Value *> Placeholders;
+  // Illegal values which have already been converted, to erase on distruction.

[jvoung (off chromium), 2013/05/09 00:06:44]

nits:

distruction -> destruction

consistency with * spacing in "SmallVector<Instruction*, 8> ToErase", vs the
above "Value *"

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+  SmallVector<Instruction*, 8> ToErase;
+};
+
+// Split an illegal load into multiple legal loads and return the resulting
+// promoted value. The size of the load is assumed to be a multiple of 8.

[Mark Seaborn, 2013/05/09 01:00:22]

Does this mean the pass doesn't handle i2...i7?

[Derek Schuff, 2013/05/09 18:30:24]

Not for loads and stores. The rest of the ops should handle them without any
extra special casing. For e.g. loads it could round to the next 8 bits, load and
then clear the upper bits, but it didn't seem necessary to put the extra logic
in there.

+static Value *splitLoad(LoadInst *Inst, ConversionState &State) {
+  assert(!Inst->isVolatile() && !Inst->isAtomic() &&

[Mark Seaborn, 2013/05/09 01:00:22]

This can get compiled out of release builds.  Do a stricter check and use
report_fatal_error()?  assert() should be for internal consistency checks but
not for validating external inputs.

The same might apply to other asserts here.

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+         "Can't split volatile/atomic loads");
+  assert(cast<IntegerType>(Inst->getType())->getBitWidth() % 8 == 0);

[Mark Seaborn, 2013/05/09 01:00:22]

This should be a report_fatal_error() too since it's a check on the pass's
input.

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+
+  Value *OrigPtr = State.getConverted(Inst->getPointerOperand());
+  // OrigPtr is a placeholder in recursive calls, and so has no name
+  if (OrigPtr->getName().empty())
+    OrigPtr->setName(Inst->getPointerOperand()->getName());
+  unsigned Width = cast<IntegerType>(Inst->getType())->getBitWidth();
+  Type *NewType = getPromotedType(Inst->getType());
+  unsigned LoWidth = Width;
+
+  while (!isLegalSize(LoWidth)) LoWidth -= 8;
+  IntegerType *LoType = IntegerType::get(Inst->getContext(), LoWidth);
+  IntegerType *HiType = IntegerType::get(Inst->getContext(), Width - LoWidth);
+  IRBuilder<> IRB(Inst->getParent(), Inst);
+
+  Value *BCLo = IRB.CreateBitCast(
+      OrigPtr,
+      LoType->getPointerTo(),
+      OrigPtr->getName() + ".loty");
+  Value *LoadLo = IRB.CreateAlignedLoad(
+      BCLo, Inst->getAlignment(), Inst->getName() + ".lo");
+  Value *LoExt = IRB.CreateZExt(LoadLo, NewType, LoadLo->getName() + ".ext");
+  Value *GEPHi = IRB.CreateConstGEP1_32(BCLo, 1, OrigPtr->getName() + ".hi");
+  Value *BCHi = IRB.CreateBitCast(
+        GEPHi,
+        HiType->getPointerTo(),
+        OrigPtr->getName() + ".hity");
+
+  Value *LoadHi = IRB.CreateLoad(BCHi, Inst->getName() + ".hi");
+  if (!isLegalSize(Width - LoWidth)) {
+    LoadHi = splitLoad(cast<LoadInst>(LoadHi), State);
+    // BCHi was still illegal, and has been replaced with a placeholder in the
+    // recursive call. Since it is redundant with BCLo in the recursive call,
+    // just splice it out entirely.
+    State.recordConverted(cast<Instruction>(BCHi), GEPHi, /*TakeName=*/false);
+  }
+
+  Value *HiExt = IRB.CreateZExt(LoadHi, NewType, LoadHi->getName() + ".ext");
+  Value *HiShift = IRB.CreateShl(HiExt, LoWidth, HiExt->getName() + ".sh");
+  Value *Result = IRB.CreateOr(LoExt, HiShift);
+
+  State.recordConverted(Inst, Result);
+
+  return Result;
+}
+
+static Value *splitStore(StoreInst *Inst, ConversionState &State) {
+  assert(!Inst->isVolatile() && !Inst->isAtomic() &&
+         "Can't split volatile/atomic stores");
+  assert(cast<IntegerType>(Inst->getValueOperand()->getType())->getBitWidth() % 8

[Mark Seaborn, 2013/05/09 01:00:22]

Line >80 chars

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+         == 0);
+
+  Value *OrigPtr = State.getConverted(Inst->getPointerOperand());
+  // OrigPtr is now a placeholder in recursive calls, and so has no name.
+  if (OrigPtr->getName().empty())
+    OrigPtr->setName(Inst->getPointerOperand()->getName());
+  Value *OrigVal = State.getConverted(Inst->getValueOperand());
+  unsigned Width = cast<IntegerType>(
+      Inst->getValueOperand()->getType())->getBitWidth();
+  unsigned LoWidth = Width;
+
+  while (!isLegalSize(LoWidth)) LoWidth -= 8;
+  IntegerType *LoType = IntegerType::get(Inst->getContext(), LoWidth);
+  IntegerType *HiType = IntegerType::get(Inst->getContext(), Width - LoWidth);
+  IRBuilder<> IRB(Inst->getParent(), Inst);
+
+  Value *BCLo = IRB.CreateBitCast(
+      OrigPtr,
+      LoType->getPointerTo(),
+      OrigPtr->getName() + ".loty");
+  Value *LoTrunc = IRB.CreateTrunc(
+      OrigVal, LoType, OrigVal->getName() + ".lo");
+  IRB.CreateAlignedStore(LoTrunc, BCLo, Inst->getAlignment());
+
+  Value *HiLShr = IRB.CreateLShr(
+      OrigVal, LoWidth, OrigVal->getName() + ".hi.sh");
+  Value *GEPHi = IRB.CreateConstGEP1_32(BCLo, 1, OrigPtr->getName() + ".hi");
+  Value *HiTrunc = IRB.CreateTrunc(
+      HiLShr, HiType, OrigVal->getName() + ".hi");
+  Value *BCHi = IRB.CreateBitCast(
+        GEPHi,
+        HiType->getPointerTo(),
+        OrigPtr->getName() + ".hity");
+
+  Value *StoreHi = IRB.CreateStore(HiTrunc, BCHi);
+
+  if (!isLegalSize(Width - LoWidth)) {
+    // HiTrunc is still illegal, and is redundant with the truncate in the
+    // recursive call, so just get rid of it.
+    State.recordConverted(cast<Instruction>(HiTrunc), HiLShr, /*TakeName=*/false);

[Mark Seaborn, 2013/05/09 01:00:22]

Line >80 chars

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+    StoreHi = splitStore(cast<StoreInst>(StoreHi), State);
+    // BCHi was still illegal, and has been replaced with a placeholder in the
+    // recursive call. Since it is redundant with BCLo in the recursive call,
+    // just splice it out entirely.
+    State.recordConverted(cast<Instruction>(BCHi), GEPHi, /*TakeName=*/false);
+  }
+  State.recordConverted(Inst, StoreHi, /*TakeName=*/false);
+  return StoreHi;
+}
+
+// Return a value with the bits of the operand above the size of the original
+// type cleared. The operand is assumed to have been legalized already.
+static Value *getClearUpper(Value *Operand, Type *OrigType,
+                            Instruction *InsertPt) {
+  // If the operand is a constant, it will have been created by
+  // ConversionState.getConverted, which zero-extends by default.
+  if (isa<Constant>(Operand))
+    return Operand;
+  return BinaryOperator::Create(
+      Instruction::And,
+      Operand,
+      ConstantInt::get(
+          getPromotedType(OrigType),
+          APInt::getLowBitsSet(getPromotedType(OrigType)->getIntegerBitWidth(),
+                               OrigType->getIntegerBitWidth())),
+      Operand->getName() + ".clear",
+      InsertPt);
+}
+
+// Return a value with the bits of the operand above the size of the original
+// type equal to the sign bit of the original operand. The new operand is
+// assumed to have been legalized already.
+// This is done by shifting the sign bit of the smaller value up to the MSB
+// position in the larger size, and then arithmetic-shifting it back down.
+static Value *getSignExtend(Value *Operand, Value *OrigOperand,
+                            Instruction *InsertPt) {
+  // If OrigOperand was a constant, NewOperand will have been created by
+  // ConversionState.getConverted, which zero-extends by default. But that is
+  // wrong here, so replace it with a sign-extended constant.
+  if (Constant *C = dyn_cast<Constant>(OrigOperand))
+    return convertConstant(C, /*SignExt=*/true);
+  Type *OrigType = OrigOperand->getType();
+  ConstantInt *ShiftAmt = ConstantInt::getSigned(
+      cast<IntegerType>(getPromotedType(OrigType)),
+      getPromotedType(OrigType)->getIntegerBitWidth() -
+        OrigType->getIntegerBitWidth());
+  BinaryOperator *Shl = BinaryOperator::Create(
+      Instruction::Shl,
+      Operand,
+      ShiftAmt,
+      Operand->getName() + ".getsign",
+      InsertPt);
+  return BinaryOperator::Create(
+      Instruction::AShr,
+      Shl,
+      ShiftAmt,
+      Operand->getName() + ".signed",
+      InsertPt);
+}
+
+static void convertInstruction(Instruction *Inst, ConversionState &State) {
+  if (SExtInst *Sext = dyn_cast<SExtInst>(Inst)) {
+    Value *Op = Sext->getOperand(0);
+    Value *NewInst = NULL;
+    // If the operand to be extended is illegal, we first need to fill its
+    // upper bits (which are zero) with its sign bit.
+    if (shouldConvert(Op)) {
+      NewInst = getSignExtend(State.getConverted(Op), Op, Sext);
+    }
+    // If the converted type of the operand is the same as the converted
+    // type of the result, we won't actually be changing the type of the
+    // variable, just its value.
+    if (getPromotedType(Op->getType()) !=
+        getPromotedType(Sext->getType())) {
+      NewInst = new SExtInst(
+          NewInst ? NewInst : State.getConverted(Op),
+          getPromotedType(cast<IntegerType>(Sext->getType())),
+          Sext->getName() + ".sext", Sext);
+    }
+    // Now all the bits of the result are correct, but we need to restore
+    // the bits above its type to zero.
+    if (shouldConvert(Sext)) {
+      NewInst = getClearUpper(NewInst, Sext->getType(), Sext);
+    }
+    assert(NewInst && "Failed to convert sign extension");
+    State.recordConverted(Sext, NewInst);
+  } else if (ZExtInst *Zext = dyn_cast<ZExtInst>(Inst)) {
+    Value *Op = Zext->getOperand(0);
+    Value *NewInst = NULL;
+    // TODO(dschuff): Some of these zexts could be no-ops.
+    if (shouldConvert(Op)) {
+      NewInst = getClearUpper(State.getConverted(Op),
+                              Op->getType(),
+                              Zext);
+    }
+    // If the converted type of the operand is the same as the converted
+    // type of the result, we won't actually be changing the type of the
+    // variable, just its value.
+    if (getPromotedType(Op->getType()) !=
+        getPromotedType(Zext->getType())) {
+      NewInst = CastInst::CreateZExtOrBitCast(
+          NewInst ? NewInst : State.getConverted(Op),
+          getPromotedType(cast<IntegerType>(Zext->getType())),
+          "", Zext);
+    }
+    assert(NewInst);
+    State.recordConverted(Zext, NewInst);
+  } else if (TruncInst *Trunc = dyn_cast<TruncInst>(Inst)) {
+    Value *Op = Trunc->getOperand(0);
+    Value *NewInst = NULL;
+    // If the converted type of the operand is the same as the converted
+    // type of the result, we won't actually be changing the type of the
+    // variable, just its value.
+    if (getPromotedType(Op->getType()) !=
+        getPromotedType(Trunc->getType())) {
+      NewInst = new TruncInst(
+          State.getConverted(Op),
+          getPromotedType(cast<IntegerType>(Trunc->getType())),
+          State.getConverted(Op)->getName() + ".trunc",
+          Trunc);
+    }
+    // Restoring the upper-bits-are-zero invariant effectively truncates the
+    // value.
+    if (shouldConvert(Trunc)) {
+      NewInst = getClearUpper(NewInst ? NewInst : Op,
+                              Trunc->getType(),
+                              Trunc);
+    }
+    assert(NewInst);
+    State.recordConverted(Trunc, NewInst);
+  } else if (AllocaInst *Alloc = dyn_cast<AllocaInst>(Inst)) {
+    // Don't handle arrays of illegal types, but we could handle an array
+    // with size specified as an illegal type, as unlikely as that seems.
+    assert(!(shouldConvert(Alloc) && Alloc->isArrayAllocation()));
+    AllocaInst *NewInst = new AllocaInst(
+        getPromotedType(Alloc->getAllocatedType()),
+        State.getConverted(Alloc->getArraySize()),
+        "", Alloc);
+    NewInst->setAlignment(Alloc->getAlignment());
+    State.recordConverted(Alloc, NewInst);
+  } else if (BitCastInst *BCInst = dyn_cast<BitCastInst>(Inst)) {
+    // Only handle pointers. Ints can't be casted to/from other ints
+    if (shouldConvert(BCInst) || shouldConvert(BCInst->getOperand(0))) {
+      BitCastInst *NewInst = new BitCastInst(
+          State.getConverted(BCInst->getOperand(0)),
+          getPromotedType(BCInst->getDestTy()),
+          "", BCInst);
+      State.recordConverted(BCInst, NewInst);
+    }
+  } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
+    if (shouldConvert(Load)) {
+      splitLoad(Load, State);
+    }
+  } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
+    if (shouldConvert(Store->getValueOperand())) {
+      splitStore(Store, State);
+    }
+  } else if (CallInst *Call = dyn_cast<CallInst>(Inst)) {
+    llvm_unreachable("can't convert calls");
+    for (unsigned I = 0; I < Call->getNumArgOperands(); ++I) {

[Mark Seaborn, 2013/05/09 01:00:22]

Drop the dead code here since it's after llvm_unreachable()?

[Derek Schuff, 2013/05/09 18:30:24]

Done.

+      Value *Arg = Call->getArgOperand(I);
+      Call->setArgOperand(I, State.getConverted(Arg));
+    }
+  } else if (BinaryOperator *Binop = dyn_cast<BinaryOperator>(Inst)) {
+    Value *NewInst = NULL;
+    if (Binop->getOpcode() == Instruction::AShr) {
+      // The AShr operand needs to be sign-extended to the promoted size
+      // before shifting. Because the sign-extension is implemented with
+      // with AShr, it can be combined with the original operation.
+      Value *Op = Binop->getOperand(0);
+      Value *ShiftAmount = NULL;
+      APInt SignShiftAmt = APInt(
+          getPromotedType(Op->getType())->getIntegerBitWidth(),
+          getPromotedType(Op->getType())->getIntegerBitWidth() -
+          Op->getType()->getIntegerBitWidth());
+      NewInst = BinaryOperator::Create(
+          Instruction::Shl,
+          State.getConverted(Op),
+          ConstantInt::get(getPromotedType(Op->getType()), SignShiftAmt),
+          State.getConverted(Op)->getName() + ".getsign",
+          Binop);
+      if (ConstantInt *C = dyn_cast<ConstantInt>(
+              State.getConverted(Binop->getOperand(1)))) {
+        ShiftAmount = ConstantInt::get(getPromotedType(Op->getType()),
+                                       SignShiftAmt + C->getValue());
+      } else {
+        ShiftAmount = BinaryOperator::Create(
+            Instruction::Add,
+            State.getConverted(Binop->getOperand(1)),
+            ConstantInt::get(
+                getPromotedType(Binop->getOperand(1)->getType()),
+                SignShiftAmt),
+            State.getConverted(Op)->getName() + ".shamt", Binop);
+      }
+      NewInst = BinaryOperator::Create(
+          Instruction::AShr,
+          NewInst,
+          ShiftAmount,
+          Binop->getName() + ".result", Binop);
+    } else {
+      // If the original operation is not AShr, just recreate it as usual.
+      NewInst = BinaryOperator::Create(
+          Binop->getOpcode(),
+          NewInst ? NewInst : State.getConverted(Binop->getOperand(0)),
+          State.getConverted(Binop->getOperand(1)),
+          Binop->getName() + ".result", Binop);
+    }
+
+    // Now restore the invariant if necessary.
+    // This switch also sanity-checks the operation.
+    switch (Binop->getOpcode()) {
+      case Instruction::And:
+      case Instruction::Or:
+      case Instruction::Xor:
+      case Instruction::LShr:
+        // These won't change the upper bits.
+        break;
+      case Instruction::Add:
+      case Instruction::Sub:
+      case Instruction::Shl:
+      case Instruction::AShr:
+        // These can change the upper bits, so clear them now.
+        NewInst = getClearUpper(NewInst, Binop->getType(), Binop);
+        break;
+
+        // We should not see FP operators here.
+        // We don't handle mul/div.
+      case Instruction::FAdd:
+      case Instruction::FSub:
+      case Instruction::Mul:
+      case Instruction::FMul:
+      case Instruction::UDiv:
+      case Instruction::SDiv:
+      case Instruction::FDiv:
+      case Instruction::URem:
+      case Instruction::SRem:
+      case Instruction::FRem:
+      case Instruction::BinaryOpsEnd:
+        errs() << *Inst << "\n";
+        llvm_unreachable("Cannot handle binary operator");
+        break;
+    }
+
+    State.recordConverted(Binop, NewInst);
+  } else if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Inst)) {
+    Value *Op0, *Op1;
+    // For signed compares, operands are sign-extended to their
+    // promoted type. For unsigned or equality compares, the comparison
+    // is equivalent with the larger type because they are already
+    // zero-extended.
+    if (Cmp->isSigned()) {
+      Op0 = getSignExtend(State.getConverted(Cmp->getOperand(0)),
+                          Cmp->getOperand(0),
+                          Cmp);
+      Op1 = getSignExtend(State.getConverted(Cmp->getOperand(1)),
+                          Cmp->getOperand(1),
+                          Cmp);
+    } else {
+      Op0 = State.getConverted(Cmp->getOperand(0));
+      Op1 = State.getConverted(Cmp->getOperand(1));
+    }
+    ICmpInst *NewInst = new ICmpInst(
+        Cmp, Cmp->getPredicate(), Op0, Op1, "");
+    State.recordConverted(Cmp, NewInst);
+  } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) {
+    SelectInst *NewInst = SelectInst::Create(
+        Select->getCondition(),
+        State.getConverted(Select->getTrueValue()),
+        State.getConverted(Select->getFalseValue()),
+        "", Select);
+    State.recordConverted(Select, NewInst);
+  } else if (PHINode *Phi = dyn_cast<PHINode>(Inst)) {
+    PHINode *NewPhi = PHINode::Create(
+        getPromotedType(Phi->getType()),
+        Phi->getNumIncomingValues(),
+        "", Phi);
+    for (unsigned I = 0, E = Phi->getNumIncomingValues(); I < E; ++I) {
+      NewPhi->addIncoming(State.getConverted(Phi->getIncomingValue(I)),
+                          Phi->getIncomingBlock(I));
+    }
+    State.recordConverted(Phi, NewPhi);
+  } else {
+    errs() << *Inst<<"\n";
+    llvm_unreachable("unhandled instruction");
+  }
+}
+
+bool PromoteIntegers::runOnFunction(Function &F) {
+  // Don't support changing the function arguments. This should not be
+  // generated by clang.
+  for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
+    Value *Arg = I;
+    if (shouldConvert(Arg)) {
+      errs() << "Function " << F.getName() << ": " << *Arg << "\n";
+      llvm_unreachable("Function has illegal integer/pointer argument");
+    }
+  }
+
+  ConversionState State;
+  bool Modified = false;
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
+    for (BasicBlock::iterator BBI = FI->begin(), BBE = FI->end(); BBI != BBE;) {
+      Instruction *Inst = BBI++;
+      // Only attempt to convert an instruction if its result or any of its
+      // operands are illegal.
+      bool ShouldConvert = shouldConvert(Inst);
+      for (User::op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
+           OI != OE; ++OI)
+        ShouldConvert |= shouldConvert(cast<Value>(OI));
+
+      if (ShouldConvert) {
+        convertInstruction(Inst, State);
+        Modified = true;
+      }
+    }
+  }
+
+  return Modified;
+}