PNaCl: Add a vector type legalization pass.

lib/Transforms/NaCl/VectorCanonicalizationPass.cpp

+//===-- VectorCanonicalizationPass.cpp - Canonicalize vector types --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass doesn't fix vectors in constants, other than those used directly by
+// instructions.
+// We don't expand ExtractValue/InsertValue (and can't), so ExpandStructRegs
+// must be run before this one.
+//
+// The test generator can be found at
+// https://github.com/DiamondLovesYou/pnacl-vector-canonicalization-test-generator
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/InitializePasses.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include "llvm/Transforms/NaCl.h"
+
+#include <functional>
+#include <deque>
+
+template <typename T> T MinAlign(T left, T right) {
+  if (left == 0) {
+    return left;
+  } else {
+    return llvm::MinAlign(left, right);
+  }
+}
+
+using namespace llvm;
+
+struct Strategy {
+  Strategy() = default;
+
+  inline operator bool() const { return To != From; }
+
+  VectorType *To = nullptr;
+  VectorType *From = nullptr;
+
+  inline unsigned toSliceStart(const unsigned I) const {
+    assert(To);
+    return I * To->getVectorNumElements();
+  }
+  inline unsigned toSliceEnd(const unsigned I,
+                             const unsigned Max = ~0LL) const {
+    assert(To);
+    const auto Idx = (I + 1) * To->getVectorNumElements();
+    return std::min(Idx, Max);
+  }
+
+  /// Maps an element index to a split part index.
+  inline unsigned splitPart(const unsigned I) const {
+    if (!From || !To) {
+      return 0;
+    }
+
+    return I / To->getVectorNumElements();
+  }
+
+  inline unsigned fromElements() const {
+    if (!From) {
+      return 0;
+    } else {
+      return From->getVectorNumElements();
+    }
+  }
+  inline unsigned toElements() const {
+    if (!To) {
+      return 0;
+    } else {
+      return To->getVectorNumElements();
+    }
+  }
+
+  unsigned extra() const {
+    if (!*this) {
+      return 0;
+    } else {
+      assert(From);
+      assert(To);
+      return (From->getVectorNumElements() - 1) / To->getVectorNumElements();
+    }
+  }
+
+  unsigned values() const { return extra() + 1; }
+
+  bool split() const { return extra() != 0; }
+  bool expand() const { return *this && extra() == 0; }
+
+  // What number of elements is valid in the last part?
+  unsigned rem() const {
+    if (!*this) {
+      return 0;
+    }
+    if (fromElements() % toElements() == 0) {
+      return 0;
+    }
+
+    return fromElements() - extra() * toElements();
+  }
+};
+
+struct BitWidthMapper {
+  /// Bitwidths. Must be sorted ascending.
+  SmallVector<unsigned, 4> NormWidths;
+  /// Which `i1` element counts are allowed? Must be sorted ascending.
+  /// This must match `NormWidths`.
+  SmallVector<unsigned, 4> I1NumElements;
+
+  VectorType *mapType(VectorType *Ty, const DataLayout &DL) const {
+    Type *Inner = Ty->getScalarType();
+    if (Inner->isIntegerTy(1)) {
+      unsigned OldCount = Ty->getVectorNumElements();
+      unsigned NewCount = 0;
+      for (unsigned Count : I1NumElements) {
+        NewCount = Count;
+        if (OldCount == NewCount) {
+          return Ty;
+        } else if (NewCount < OldCount) {
+          continue;
+        } else {
+          break;
+        }
+      }
+
+      assert(NewCount != 0);
+      return VectorType::get(Inner, NewCount);
+    } else {
+      const unsigned BitWidth = DL.getTypeSizeInBits(Ty);
+
+      unsigned Width = 0;
+      for (unsigned I = 0; I < NormWidths.size(); ++I) {
+        Width = NormWidths[I];
+        if (Width < BitWidth) {
+          continue;
+        } else if (Width == BitWidth) {
+          return Ty;
+        } else {
+          break;
+        }
+      }
+
+      const auto InnerSize = DL.getTypeSizeInBits(Inner);
+      assert(Width != 0);
+      assert(Width % InnerSize == 0);
+      return VectorType::get(Inner, Width / InnerSize);
+    }
+  }
+
+  void getStrategy(Type *For, Strategy &Strat, const DataLayout &DL) const {
+    if (auto *VTy = dyn_cast<VectorType>(For)) {
+      auto *NewVTy = mapType(VTy, DL);
+      Strat.From = VTy;
+      Strat.To = NewVTy;
+    } else {
+      Strat.From = nullptr;
+      Strat.To = nullptr;
+    }
+  }
+};
+
+/// Helper to manage sets of allocas for use in split returns.
+/// TODO use a maximally sized buffer for all return spaces.
+struct ReturnAllocManager {
+  ReturnAllocManager(Instruction *InsertionPt) : Builder(InsertionPt) {}
+
+  const SmallVectorImpl<Value *> &get(const Strategy &S, const DataLayout &DL) {
+    assert(S);
+
+    auto I =
+        ScratchPads.insert(std::make_pair(S.To, SmallVector<Value *, 4>()));
+    auto &A = I.first->second;
+    for (unsigned I = A.size(); I < S.extra(); ++I) {
+      AllocaInst *Alloc = Builder.CreateAlloca(S.To);
+      Alloc->setAlignment(DL.getPrefTypeAlignment(S.To));
+      A.push_back(Alloc);
+    }
+
+    return A;
+  }
+
+private:
+  IRBuilder<> Builder;
+  DenseMap<VectorType *, SmallVector<Value *, 4>> ScratchPads;
+};
+
+struct InstructionStrategy;
+struct FunctionStrategy {
+  FunctionStrategy() {}
+  FunctionStrategy(const FunctionStrategy &rhs)
+      : Placeholders(rhs.Placeholders), Args(rhs.Args), Ret(rhs.Ret),
+        OldFTy(rhs.OldFTy), NewFTy(rhs.NewFTy) {}
+  FunctionStrategy(FunctionStrategy &&rhs)
+      : Placeholders(std::move(rhs.Placeholders)), Args(std::move(rhs.Args)),
+        Ret(std::move(rhs.Ret)), OldFTy(rhs.OldFTy), NewFTy(rhs.NewFTy) {}
+
+  FunctionStrategy &operator=(const FunctionStrategy &rhs) {
+    Args = rhs.Args;
+    Ret = rhs.Ret;
+
+    NewFTy = rhs.NewFTy;
+    OldFTy = rhs.OldFTy;
+
+    Placeholders = rhs.Placeholders;
+    return *this;
+  }
+  FunctionStrategy &operator=(FunctionStrategy &&rhs) {
+    Args = std::move(rhs.Args);
+    Ret = std::move(rhs.Ret);
+
+    NewFTy = rhs.NewFTy;
+    OldFTy = rhs.OldFTy;
+
+    Placeholders = std::move(rhs.Placeholders);
+    return *this;
+  }
+
+  inline operator bool() const { return OldFTy != NewFTy; }
+
+  /// Return an array of the new argument values. Some will be placeholders.
+  SmallVector<Value *, 8> mapFunction(Function::ArgumentListType &In) const;
+  void mapReturns(SmallVectorImpl<ReturnInst *> &Rets,
+                  Function::ArgumentListType &Args, const DataLayout &DL) const;
+  void mapVaArg(VAArgInst *VaArg, const Strategy &Strategy,
+                IRBuilder<> &Builder) const;
+
+  AttributeSet mapAttrs(AttributeSet Old, LLVMContext &C,
+                        const DataLayout &DL) const;
+
+  FunctionType *oldFunctionType() const { return OldFTy; }
+  FunctionType *newFunctionType() const { return NewFTy; }
+
+  void build(FunctionType *OldFTy, const BitWidthMapper &Map,
+             const DataLayout &DL);
+
+  const SmallVectorImpl<Strategy> &getArgs() const { return Args; }
+  const Strategy &getArg(const unsigned I) const { return Args[I]; }
+  const SmallVectorImpl<Argument *> &getPlaceholders() const {
+    return Placeholders;
+  }
+  const Strategy &getRet() const { return Ret; }
+
+private:
+  SmallVector<Argument *, 8> Placeholders;
+  SmallVector<Strategy, 8> Args;
+  Strategy Ret;
+
+  FunctionType *OldFTy;
+  FunctionType *NewFTy;
+};
+
+/// This pass rewrites function signatures.
+class VectorCanonicalizationFunctionPass {
+public:
+  VectorCanonicalizationFunctionPass(BitWidthMapper &Cfg) : Cfg(Cfg) {}
+
+  void runOnModule(Module &M);
+
+  FunctionStrategy &buildStrategy(FunctionType *FTy, const DataLayout &DL) {
+    assert(FTy);
+
+    auto Result = Strategies.insert(std::make_pair(FTy, nullptr));
+    auto **Strategy = &Result.first->second;
+    if (Result.second) {
+      StrategyStorage.emplace_back();
+      *Strategy = &StrategyStorage.back();
+      (*Strategy)->build(FTy, Cfg, DL);
+    }
+
+    assert(*Strategy);
+    return **Strategy;
+  }
+
+  const FunctionStrategy &getOldFunctionStrategy(Function *F) {
+    auto R = FunToStrategy.find(F);
+    assert(R != FunToStrategy.end());
+    return *R->second;
+  }
+
+  void registerNewFunction(Function *F, FunctionStrategy &FS) {
+    const auto Inserted = FunToStrategy.insert(std::make_pair(F, &FS)).second;
+    (void)Inserted;
+    assert(Inserted);
+  }
+
+  bool modified() const { return Modified; }
+
+private:
+  bool Modified = false;
+  BitWidthMapper &Cfg;
+
+  // avoids allocation on every new strategy.
+  std::deque<FunctionStrategy> StrategyStorage;
+
+  DenseMap<FunctionType *, FunctionStrategy *> Strategies;
+  DenseMap<Function *, FunctionStrategy *> FunToStrategy;
+};
+
+struct InstructionStrategy : public Strategy {
+  InstructionStrategy() = delete;
+  InstructionStrategy(Value *S) : Source(S) {}
+
+  Value *getValue(const unsigned I) const {
+    if (I > values()) {
+      return nullptr;
+    }
+    if (!*this) {
+      return Source;
+    }
+
+    return Expanded[I];
+  }
+  Value *getSource() const { return Source; }
+
+  const SmallVectorImpl<Value *> &getExpanded() const { return Expanded; }
+  SmallVectorImpl<Value *> &getExpanded() { return Expanded; }
+  void setExpanded(SmallVector<Value *, 4> Ex) {
+    assert(values() == Ex.size());
+    Expanded = std::move(Ex);
+  }
+  void setExpanded(Instruction *I) {
+    assert(values() == 1);
+    Expanded.clear();
+    Expanded.push_back(I);
+  }
+
+  void forEach(std::function<Value *()> Callback);
+  template <typename T>
+  void forEach(
+      ArrayRef<T> Elements,
+      std::function<Value *(const unsigned Count, ArrayRef<T> Slice)> Callback);
+  void forEach(std::function<Value *(const unsigned I, const unsigned Offset,
+                                     const unsigned End)> Callback);
+
+private:
+  /// A constant or an instruction.
+  Value *Source = nullptr;
+
+  SmallVector<Value *, 2> Expanded;
+};
+
+class VectorCanonicalizationInstructionPass {
+public:
+  VectorCanonicalizationInstructionPass() = delete;
+  VectorCanonicalizationInstructionPass(
+      Function *F, BitWidthMapper &Cfg,
+      VectorCanonicalizationFunctionPass &FPass)
+      : Cfg(Cfg), CallReturnAllocMgr(F->getEntryBlock().getFirstInsertionPt()),
+        FPass(FPass), FStrategy(FPass.getOldFunctionStrategy(F)),
+        DL(F->getParent()->getDataLayout()) {
+    // create instruction strategies for the placeholder values.
+    const auto &Placeholders = FStrategy.getPlaceholders();
+    auto NewArgsIt = F->arg_begin();
+    if (FStrategy.getRet()) {
+      // skip extra return arguments.
+      for (unsigned I = 0; I < FStrategy.getRet().extra(); ++I, ++NewArgsIt) {
+      }
+    }
+
+    for (unsigned I = 0; I < FStrategy.getArgs().size(); ++I) {
+      const auto &ArgStrategy = FStrategy.getArg(I);
+      if (!ArgStrategy) {
+        ++NewArgsIt;
+        continue;
+      }
+
+      auto *Placeholder = Placeholders[I];
+      assert(Placeholder);
+
+      auto &IStrategy =
+          Mapping.insert(std::make_pair(Placeholder,
+                                        InstructionStrategy(Placeholder)))
+              .first->second;
+      *static_cast<Strategy *>(&IStrategy) = FStrategy.getArg(I);
+      auto Callback = [&NewArgsIt]() mutable { return NewArgsIt++; };
+      IStrategy.forEach(std::move(Callback));
+    }
+  }
+
+  void runOnFunction(Function &F);
+
+  bool modified() const { return Modified; }
+
+private:
+  bool Modified = false;
+
+  /// Breath-first.
+  void runOnBasicBlock(BasicBlock *BB, SmallPtrSetImpl<BasicBlock *> &Visited);
+  void runOnBasicBlockSuccessors(BasicBlock *BB,
+                                 SmallPtrSetImpl<BasicBlock *> &Visited);
+
+  const InstructionStrategy &findStrategyFor(Value *Source,
+                                             Instruction *InsertionPt) {
+    auto Result =
+        Mapping.insert(std::make_pair(Source, InstructionStrategy(Source)));
+    auto &IS = Result.first->second;
+    if (Result.second) {
+      buildStrategy(IS, InsertionPt);
+    }
+
+    return IS;
+  }
+  void fixStoreInstruction(StoreInst *OldStore);
+  void fixBitcastInstruction(BitCastInst *BC);
+  void fixExtractElementInstruction(ExtractElementInst *Extract);
+  void fixCallInstruction(CallInst *Call);
+  void fixShuffleInstruction(ShuffleVectorInst *Shuffle);
+  void fixCastInstruction(CastInst *Cast);
+  bool fixCmpInstruction(InstructionStrategy &Strategy, CmpInst *Cmp,
+                         IRBuilder<> &Builder);
+
+  void fixPhiNodes();
+
+  void getShuffleValues(
+      const InstructionStrategy &LeftStrategy,
+      const InstructionStrategy &RightStrategy,
+      const SmallVectorImpl<int> &Mask,
+      SmallVectorImpl<std::tuple<Value *, Value *, unsigned>> &Values) const;
+  Value *shuffleRebuildHelper(
+      ShuffleVectorInst *Shuffle, IRBuilder<> &Builder,
+      SmallVectorImpl<std::tuple<Value *, Value *, unsigned>> &Values,
+      const unsigned Start, const unsigned End);
+
+  void buildStrategy(InstructionStrategy &Strategy, Instruction *InsertionPt);
+  void buildConstantStrategy(InstructionStrategy &Strategy, Constant *C,
+                             IRBuilder<> &Builder);
+  void buildInstructionStrategy(InstructionStrategy &Strategy, Instruction *I,
+                                IRBuilder<> &Builder);
+  void buildCastStrategy(InstructionStrategy &Strategy, CastInst *Cast,
+                         IRBuilder<> &Builder);
+  void buildScalarCastStrategy(InstructionStrategy &Strategy, CastInst *Cast,
+                               IRBuilder<> &Builder);
+  void buildVectorCastStrategy(InstructionStrategy &Strategy, CastInst *Cast,
+                               IRBuilder<> &Builder);
+
+  BitWidthMapper &Cfg;
+  DenseMap<Value *, InstructionStrategy> Mapping;
+
+  ReturnAllocManager CallReturnAllocMgr;
+
+  SmallVector<InstructionStrategy, 32> PhiNodes;
+
+  SmallVector<Instruction *, 32> ToDelete;
+
+  VectorCanonicalizationFunctionPass &FPass;
+  const FunctionStrategy &FStrategy;
+
+  const DataLayout &DL;
+};
+
+void VectorCanonicalizationFunctionPass::runOnModule(Module &M) {
+  Modified = true;
+  SmallVector<Function *, 32> ToDelete;
+  auto &C = M.getContext();
+  const auto &DL = M.getDataLayout();
+
+  auto DISubprogramMap = makeSubprogramMap(M);
+
+  for (Module::iterator I = M.begin(); I != M.end(); ++I) {
+    Function *OldF = I;
+    auto &FStrategy = buildStrategy(OldF->getFunctionType(), DL);
+    if (!FStrategy) {
+      registerNewFunction(OldF, FStrategy);
+      continue;
+    }
+
+    Function *NewF =
+        Function::Create(FStrategy.newFunctionType(), OldF->getLinkage(), "");
+    registerNewFunction(NewF, FStrategy);
+    M.getFunctionList().insert(I, NewF);
+
+    auto OldAttrs = OldF->getAttributes();
+    auto NewAttrs = FStrategy.mapAttrs(OldAttrs, C, DL);
+    NewF->setAttributes(NewAttrs);
+
+    auto ParamMap = FStrategy.mapFunction(NewF->getArgumentList());
+
+    assert(ParamMap.size() == OldF->arg_size());
+
+    ValueToValueMapTy VMap;
+    {
+      auto OldArgIt = OldF->arg_begin();
+      for (unsigned J = 0; J < ParamMap.size(); ++J, ++OldArgIt) {
+        VMap[OldArgIt] = ParamMap[J];
+      }
+    }
+
+    SmallVector<ReturnInst *, 32> Returns;
+    CloneFunctionInto(NewF, OldF, VMap, false, Returns);
+
+    FStrategy.mapReturns(Returns, NewF->getArgumentList(), DL);
+    Returns.clear();
+
+    if (NewF->isVarArg()) {
+      for (auto &BB : NewF->getBasicBlockList()) {
+        for (auto &I : BB.getInstList()) {
+          if (auto *VAArg = dyn_cast<VAArgInst>(&I)) {
+            Strategy S;
+            Cfg.getStrategy(VAArg->getType(), S, DL);
+            IRBuilder<> Builder(VAArg);
+            FStrategy.mapVaArg(VAArg, S, Builder);
+          }
+        }
+      }
+    }
+
+    auto Found = DISubprogramMap.find(OldF);
+    if (Found != DISubprogramMap.end())
+      Found->second->replaceFunction(NewF);
+
+    OldF->replaceAllUsesWith(
+        ConstantExpr::getPointerCast(NewF, OldF->getType()));
+    ToDelete.push_back(OldF);
+
+    // This should be last:
+    NewF->takeName(OldF);
+  }
+
+  for (Function *F : ToDelete) {
+    F->dropAllReferences();
+  }
+  for (Function *F : ToDelete) {
+    F->eraseFromParent();
+  }
+}
+
+AttributeSet FunctionStrategy::mapAttrs(AttributeSet Old, LLVMContext &C,
+                                        const DataLayout &DL) const {
+  AttributeSet New;
+  New = New.addAttributes(C, AttributeSet::ReturnIndex, Old.getRetAttributes());
+  for (unsigned I = 0; I < Ret.extra(); ++I) {
+    New = New.addAttribute(C, 1 + I, Attribute::NonNull);
+    New = New.addAttribute(C, 1 + I, Attribute::NoCapture);
+    New = New.addDereferenceableAttr(C, I + 1, DL.getTypeAllocSize(Ret.To));
+  }
+  unsigned Offset = Ret.extra();
+
+  for (unsigned I = 0; I < Args.size(); ++I) {
+    const auto &Arg = Args[I];
+
+    const unsigned OldIndex = I + 1;
+    auto OldAttrs = Old.getParamAttributes(OldIndex);
+    if (OldAttrs.getNumSlots() == 0) {
+      Offset += Arg.extra();
+      continue;
+    }
+
+    unsigned OldSlot = 0;
+    for (; OldSlot < OldAttrs.getNumSlots(); ++OldSlot) {
+      if (OldAttrs.getSlotIndex(OldSlot) == OldIndex) {
+        break;
+      }
+    }
+    assert(OldSlot != OldAttrs.getNumSlots());
+
+    if (Arg) {
+      for (unsigned J = 0; J < Arg.values(); ++J) {
+        const auto NewIndex = 1 + I + J + Offset;
+        AttrBuilder B(AttributeSet(), NewIndex);
+        for (auto II = OldAttrs.begin(OldSlot), IE = OldAttrs.end(OldSlot);
+             II != IE; ++II) {
+          B.addAttribute(*II);
+        }
+        auto Attrs = AttributeSet::get(C, NewIndex, B);
+        New = New.addAttributes(C, NewIndex, Attrs);
+      }
+      Offset += Arg.extra();
+    } else {
+      const auto NewIndex = 1 + I + Offset;
+      AttrBuilder B(AttributeSet(), NewIndex);
+      for (auto II = OldAttrs.begin(OldSlot), IE = OldAttrs.end(OldSlot);
+           II != IE; ++II) {
+        B.addAttribute(*II);
+      }
+      auto Attrs = AttributeSet::get(C, NewIndex, B);
+      New = New.addAttributes(C, NewIndex, Attrs);
+    }
+  }
+
+  auto FnAttrs = Old.getFnAttributes();
+  if (Ret) {
+    FnAttrs = FnAttrs.removeAttribute(C, AttributeSet::FunctionIndex,
+                                      Attribute::ReadOnly);
+  }
+  New = New.addAttributes(C, AttributeSet::FunctionIndex, FnAttrs);
+
+  return New;
+}
+
+SmallVector<Value *, 8>
+FunctionStrategy::mapFunction(Function::ArgumentListType &In) const {
+  SmallVector<Value *, 8> Out;
+
+  auto InArg = In.begin();
+
+  if (Ret) {
+    for (unsigned I = 0; I < Ret.extra(); ++I, ++InArg) {
+    }
+  }
+
+  for (unsigned I = 0; I < Args.size(); ++I) {
+    const auto &Result = Args[I];
+
+    if (!Result) {
+      Out.push_back(InArg);
+    } else {
+      Out.push_back(Placeholders[I]);
+    }
+
+    for (unsigned J = 0; J < Result.values(); ++J, ++InArg) {
+    }
+  }
+
+  return std::move(Out);
+}
+void FunctionStrategy::mapReturns(SmallVectorImpl<ReturnInst *> &Rets,
+                                  Function::ArgumentListType &Args,
+                                  const DataLayout &DL) const {
+  if (!Ret) {
+    return;
+  }
+
+  const unsigned NewCount = Ret.toElements();
+
+  SmallVector<int, 16> ShuffleIndices;
+  ShuffleIndices.resize(Ret.values() * NewCount);
+  for (unsigned I = 0; I < ShuffleIndices.size(); ++I) {
+    if (I < Ret.fromElements()) {
+      ShuffleIndices[I] = I;
+    } else {
+      ShuffleIndices[I] = Ret.fromElements() - 1;
+    }
+  }
+
+  Value *RightSide = UndefValue::get(Ret.From);
+  SmallVector<int, 16> NewMask;
+  for (ReturnInst *RetInst : Rets) {
+
+    Value *RetValue = RetInst->getReturnValue();
+
+    IRBuilder<> Builder(RetInst);
+
+    Value *NewRetValue = nullptr;
+    auto ArgIt = Args.begin();
+    for (unsigned I = 0; I < Ret.values(); ++I) {
+      ArrayRef<int> ShuffleIndicesRef = ShuffleIndices;
+      auto Slice = ShuffleIndicesRef.slice(I * NewCount, NewCount);
+      Value *Shuffle = Builder.CreateShuffleVector(RetValue, RightSide, Slice);
+      if (I == 0) {
+        NewRetValue = Shuffle;
+        continue;
+      } else {
+        Value *DestArg = &*ArgIt;
+        const unsigned Alignment = DL.getPrefTypeAlignment(Ret.To);
+        Builder.CreateAlignedStore(Shuffle, DestArg, Alignment);
+      }
+
+      ++ArgIt;
+    }
+
+    assert(NewRetValue);
+    Builder.CreateRet(NewRetValue);
+
+    RetInst->eraseFromParent();
+  }
+}
+void FunctionStrategy::mapVaArg(VAArgInst *VaArg, const Strategy &Strategy,
+                                IRBuilder<> &Builder) const {
+  if (!Strategy) {
+    return;
+  }
+
+  // TODO
+  VaArg->dump();
+  llvm_unreachable("TODO mapVaArg");
+}
+
+void FunctionStrategy::build(FunctionType *OldFTy, const BitWidthMapper &Map,
+                             const DataLayout &DL) {
+  this->OldFTy = OldFTy;
+  SmallVector<Type *, 8> NewArgs;
+
+  Type *RetTy = OldFTy->getReturnType();
+  Map.getStrategy(RetTy, Ret, DL);
+  for (unsigned I = 0; I < Ret.extra(); ++I) {
+    NewArgs.push_back(Ret.To->getPointerTo());
+  }
+  Type *NewRet = RetTy;
+  if (Ret) {
+    NewRet = Ret.To;
+  }
+
+  for (Type *ArgTy : OldFTy->params()) {
+    Strategy S;
+    Map.getStrategy(ArgTy, S, DL);
+    Args.push_back(S);
+    if (S) {
+      Argument *Placeholder = new Argument(S.From);
+      Placeholders.push_back(Placeholder);
+
+      for (unsigned I = 0; I < S.values(); ++I) {
+        NewArgs.push_back(S.To);
+      }
+    } else {
+      Placeholders.push_back(nullptr);
+      NewArgs.push_back(ArgTy);
+    }
+  }
+
+  this->NewFTy = FunctionType::get(NewRet, NewArgs, OldFTy->isVarArg());
+}
+void InstructionStrategy::forEach(std::function<Value *()> Callback) {
+  Expanded.clear();
+  Expanded.reserve(values());
+  for (unsigned I = 0; I < values(); ++I) {
+    Value *V = Callback();
+    assert(V);
+    Expanded.push_back(V);
+  }
+}
+template <typename T>
+void InstructionStrategy::forEach(
+    ArrayRef<T> Elements,
+    std::function<Value *(const unsigned Count, ArrayRef<T> Slice)> Callback) {
+  Expanded.clear();
+  Expanded.reserve(values());
+
+  const auto Per = To->getVectorNumElements();
+  for (unsigned I = 0; I < values(); ++I) {
+    const auto Start = Per * I;
+    const auto End = Per * (I + 1);
+
+    auto Slice = Elements.slice(Start, std::min((size_t)End, Elements.size()));
+
+    Value *V;
+    if (End > Elements.size()) {
+      // We must copy from the last element because otherwise we could introduce
+      // div by zero etc.
+      SmallVector<T, 8> NewSlice(Slice.begin(), Slice.end());
+      for (unsigned I = Slice.size(); I < End; ++I) {
+        NewSlice.push_back(Slice.back());
+      }
+      V = Callback(Per, NewSlice);
+    } else {
+      V = Callback(Per, Slice);
+    }
+    assert(V);
+    Expanded.push_back(V);
+  }
+}
+void InstructionStrategy::forEach(std::function<Value *(
+    const unsigned I, const unsigned Offset, const unsigned End)> Callback) {
+  Expanded.clear();
+  Expanded.reserve(values());
+
+  const auto Per = To->getVectorNumElements();
+  for (unsigned I = 0; I < values(); ++I) {
+    const auto Start = Per * I;
+    const auto End = Per * (I + 1);
+
+    Value *V = Callback(I, Start, End);
+    assert(V);
+    Expanded.push_back(V);
+  }
+}
+void VectorCanonicalizationInstructionPass::runOnFunction(Function &F) {
+  SmallPtrSet<BasicBlock *, 64> Visited;
+  BasicBlock *Entry = &F.getEntryBlock();
+
+  runOnBasicBlock(Entry, Visited);
+  runOnBasicBlockSuccessors(Entry, Visited);
+
+  fixPhiNodes();
+
+  for (auto *I : ToDelete) {
+    I->dropAllReferences();
+  }
+  for (auto *I : ToDelete) {
+    I->eraseFromParent();
+  }
+  ToDelete.clear();
+}
+
+void VectorCanonicalizationInstructionPass::runOnBasicBlock(
+    BasicBlock *BB, SmallPtrSetImpl<BasicBlock *> &Visited) {
+  for (auto II = BB->begin(); II != BB->end();) {
+    auto I = II++;
+    const auto &Strategy = findStrategyFor(&*I, &*I);
+    /// We still need to fix cases where the instruction doesn't itself require
+    /// promotion, but one of its operands does (or was).
+    if (Strategy) {
+      // We don't need to do this for things already fixed.
+      continue;
+    }
+
+    const auto Opcode = I->getOpcode();
+    if (Opcode == Instruction::BitCast &&
+        findStrategyFor(I->getOperand(0), &*I)) {
+      /// ie: `bitcast <8 x i32> to i256`
+      fixBitcastInstruction(cast<BitCastInst>(&*I));
+    } else if (Opcode == Instruction::Call) {
+      fixCallInstruction(cast<CallInst>(&*I));
+    } else if (Opcode == Instruction::ShuffleVector) {
+      fixShuffleInstruction(cast<ShuffleVectorInst>(&*I));
+    } else if (Opcode == Instruction::ExtractElement) {
+      fixExtractElementInstruction(cast<ExtractElementInst>(&*I));
+    } else if (Opcode == Instruction::Store) {
+      fixStoreInstruction(cast<StoreInst>(&*I));
+    } else if (auto *Cast = dyn_cast<CastInst>(&*I)) {
+      fixCastInstruction(Cast);
+    } else if (auto *Cmp = dyn_cast<CmpInst>(&*I)) {
+      IRBuilder<> Builder(Cmp);
+      if (fixCmpInstruction(Mapping.find(I)->second, Cmp, Builder)) {
+        ToDelete.push_back(Cmp);
+      }
+    }
+  }
+}
+void VectorCanonicalizationInstructionPass::runOnBasicBlockSuccessors(
+    BasicBlock *BB, SmallPtrSetImpl<BasicBlock *> &Visited) {
+  if (!Visited.insert(BB).second) {
+    return;
+  }
+
+  for (BasicBlock *Successor : successors(BB)) {
+    runOnBasicBlock(Successor, Visited);
+  }
+
+  for (BasicBlock *Successor : successors(BB)) {
+    runOnBasicBlockSuccessors(Successor, Visited);
+  }
+}
+void VectorCanonicalizationInstructionPass::buildStrategy(
+    InstructionStrategy &Strategy, Instruction *InsertionPt) {
+
+  auto *S = Strategy.getSource();
+  Cfg.getStrategy(S->getType(), Strategy, DL);
+
+  if (!Strategy) {
+    return;
+  }
+
+  Modified = true;
+
+  IRBuilder<> Builder(InsertionPt);
+
+  if (auto *C = dyn_cast<Constant>(S)) {
+    buildConstantStrategy(Strategy, C, Builder);
+  } else if (auto *I = dyn_cast<Instruction>(S)) {
+    buildInstructionStrategy(Strategy, I, Builder);
+    ToDelete.push_back(I);
+  } else {
+    S->dump();
+    llvm_unreachable("woa");
+  }
+}
+
+template <typename T, bool Valid = std::is_floating_point<T>::value ||
+                                   std::is_integral<T>::value>
+struct GetData;
+
+template <typename T> struct GetData<T, true> {
+  LLVMContext &C;
+  SmallVector<T, 8> Data;
+
+  GetData(ConstantDataSequential *SeqData) : C(SeqData->getContext()) {
+    Data.clear();
+    const auto NumElements = SeqData->getNumElements();
+
+    Data.reserve(NumElements);
+
+    for (unsigned I = 0; I < NumElements; ++I) {
+      if (std::is_integral<T>::value) {
+        const uint64_t Value = SeqData->getElementAsInteger(I);
+        Data.push_back(static_cast<T>(Value));
+      } else if (std::is_same<T, float>::value) {
+        const auto Float = SeqData->getElementAsFloat(I);
+        Data.push_back(Float);
+      } else if (std::is_same<T, double>::value) {
+        const auto Double = SeqData->getElementAsDouble(I);
+        Data.push_back(Double);
+      }
+    }
+  }
+
+  void forEach(InstructionStrategy &Strategy) const {
+    std::function<Value *(const unsigned, ArrayRef<T>)> Callback =
+        [this](const unsigned Count, ArrayRef<T> Slice) {
+          return ConstantDataVector::get(this->C, Slice);
+        };
+    Strategy.forEach(ArrayRef<T>(Data), std::move(Callback));
+  }
+};
+
+void VectorCanonicalizationInstructionPass::buildConstantStrategy(
+    InstructionStrategy &Strategy, Constant *C, IRBuilder<> &Builder) {
+  /// Expand these first four directly.
+  if (isa<ConstantAggregateZero>(C)) {
+    auto *VTy = Strategy.To;
+    auto Callback = [VTy]() { return ConstantAggregateZero::get(VTy); };
+    Strategy.forEach(std::move(Callback));
+  } else if (isa<UndefValue>(C)) {
+    auto *VTy = Strategy.To;
+    auto Callback = [VTy]() { return UndefValue::get(VTy); };
+    Strategy.forEach(std::move(Callback));
+  } else if (auto *Data = dyn_cast<ConstantDataVector>(C)) {
+    /// Well this is awful.
+    Type *ElementType = Data->getElementType();
+    std::function<void()> Run;
+    if (ElementType->isIntegerTy(8)) {
+      auto GD = GetData<uint8_t>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else if (ElementType->isIntegerTy(16)) {
+      auto GD = GetData<uint16_t>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else if (ElementType->isIntegerTy(32)) {
+      auto GD = GetData<uint32_t>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else if (ElementType->isIntegerTy(64)) {
+      auto GD = GetData<uint64_t>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else if (ElementType->isFloatTy()) {
+      auto GD = GetData<float>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else if (ElementType->isDoubleTy()) {
+      auto GD = GetData<double>(Data);
+      Run = [GD, &Strategy]() { GD.forEach(Strategy); };
+    } else {
+      Data->dump();
+      llvm_unreachable("unknown sequential type");
+    }
+
+    assert(Run);
+    Run();
+  } else if (auto *Data = dyn_cast<ConstantVector>(C)) {
+    SmallVector<Constant *, 8> Operands;
+    Operands.reserve(Data->getType()->getNumElements());
+    for (auto *Element : Data->operand_values()) {
+      Operands.push_back(cast<Constant>(Element));
+    }
+    std::function<Value *(const unsigned, ArrayRef<Constant *>)> Callback =
+        [](const unsigned, ArrayRef<Constant *> Slice) {
+          return ConstantVector::get(Slice);
+        };
+    Strategy.forEach(ArrayRef<Constant *>(Operands), std::move(Callback));
+  } else if (auto *Expr = dyn_cast<ConstantExpr>(C)) {
+    /// Use shuffle to split these.
+    const unsigned NumElements = Expr->getType()->getVectorNumElements();
+    Constant *Undef = UndefValue::get(Expr->getType());
+    IntegerType *I32Ty = Type::getInt32Ty(Expr->getContext());
+    auto Callback = [Expr, NumElements, Undef, I32Ty, &Strategy](
+        const unsigned, const unsigned Offset, const unsigned End) mutable {
+      SmallVector<Constant *, 8> MaskValues;
+      MaskValues.resize(End - Offset);
+      for (unsigned I = 0; I < MaskValues.size(); ++I) {
+        unsigned V;
+        if (I > NumElements) {
+          V = NumElements;
+        } else {
+          V = Offset + I;
+        }
+
+        MaskValues[I] = ConstantInt::get(I32Ty, V);
+      }
+
+      auto *Mask = ConstantVector::get(MaskValues);
+      Constant *C =
+          ConstantExpr::getShuffleVector(Expr, Undef, Mask, Strategy.To);
+      assert(C);
+      return C;
+    };
+    Strategy.forEach(std::move(Callback));
+  } else {
+    C->dump();
+    llvm_unreachable("constant not handled");
+  }
+}
+void VectorCanonicalizationInstructionPass::buildInstructionStrategy(
+    InstructionStrategy &Strategy, Instruction *I, IRBuilder<> &Builder) {
+  if (auto *Load = dyn_cast<LoadInst>(I)) {
+    /// Split up the load.
+    assert(!Load->isAtomic() && "Atomic loading vectors isn't supported" &&
+           "TODO?");
+
+    const auto &Source = findStrategyFor(Load->getPointerOperand(), Load);
+    assert(Source.values() == 1);
+
+    const unsigned FromLen = Load->getType()->getVectorNumElements();
+    const unsigned OriginalAlignment = Load->getAlignment();
+    const unsigned ElementByteWidth =
+        DL.getTypeSizeInBits(Load->getType()->getVectorElementType()) / 8;
+    auto *I32Ty = IntegerType::get(I->getContext(), 32);
+    auto Callback = [Load, &Source, &Builder, FromLen, ElementByteWidth,
+                     OriginalAlignment, &Strategy, I32Ty](
+        const unsigned Part, const unsigned Offset, const unsigned End) {
+      Value *Expanded = nullptr;
+      if (FromLen < End) {
+        Value *Chain = UndefValue::get(Strategy.To);
+        // Don't load past the end of the vector.
+        for (unsigned I = 0; I + Offset < std::min(End, FromLen); ++I) {
+          // gep -> scalar load -> insert element
+          ArrayRef<uint64_t> Indices = {0, I + Offset};
+          Type *IndexedType = GetElementPtrInst::getIndexedType(
+              Source.getSource()->getType(), Indices);
+          auto *GEP = Builder.CreateConstGEP2_32(
+              IndexedType, Source.getValue(0), 0, I + Offset);
+          const unsigned Alignment =
+              MinAlign(OriginalAlignment, ElementByteWidth * (Offset + I));
+          auto *NewLoad =
+              Builder.CreateAlignedLoad(GEP, Alignment, Load->isVolatile());
+          Chain = Builder.CreateInsertElement(Chain, NewLoad,
+                                              ConstantInt::get(I32Ty, I));
+        }
+
+        Expanded = Chain;
+      } else {
+        // gep -> bitcast to vector type -> load
+        ArrayRef<uint64_t> Indices = {0, Offset};
+        Type *IndexedType = GetElementPtrInst::getIndexedType(
+            Source.getSource()->getType(), Indices);
+        auto *GEP = Builder.CreateConstGEP2_32(IndexedType, Source.getValue(0),
+                                               0, Offset);
+        auto *BC = Builder.CreatePointerCast(GEP, Strategy.To->getPointerTo());
+        const unsigned Alignment =
+            MinAlign(OriginalAlignment, ElementByteWidth * Offset);
+        Expanded = Builder.CreateAlignedLoad(BC, Alignment, Load->isVolatile());
+      }
+      return Expanded;
+    };
+    Strategy.forEach(std::move(Callback));
+  } else if (auto *Insert = dyn_cast<InsertElementInst>(I)) {
+    // No need to lookup the inserted value's strategy; it must be a scalar
+    // anyway.
+    auto *InsertedValue = Insert->getOperand(1);
+    const auto &SourceStrategy = findStrategyFor(Insert->getOperand(0), Insert);
+    auto *OriginalIdx = Insert->getOperand(2);
+    auto *I32Ty = IntegerType::get(I->getContext(), 32);
+
+    if (isa<ConstantInt>(OriginalIdx) || SourceStrategy.extra() == 0) {
+      auto *CIdx = dyn_cast<ConstantInt>(OriginalIdx);
+      auto Callback =
+          [InsertedValue, &SourceStrategy, CIdx, &Builder, I32Ty, OriginalIdx](
+              const unsigned I, const unsigned Start, const unsigned End) {
+            Value *NewIdx = nullptr;
+            auto *Source = SourceStrategy.getValue(I);
+            if (CIdx) {
+              const auto Idx = CIdx->getZExtValue();
+              if (Start <= Idx &&
+                  Idx < std::min(End, SourceStrategy.fromElements())) {
+                NewIdx = ConstantInt::get(I32Ty, Idx - Start);
+              } else {
+                return Source;
+              }
+            } else {
+              assert(I == 0);
+              NewIdx = OriginalIdx;
+            }
+            assert(NewIdx);
+            return Builder.CreateInsertElement(Source, InsertedValue, NewIdx);
+          };
+      Strategy.forEach(std::move(Callback));
+    } else {
+      /// Create a chain of selects on integer cmps on each index
+      /// Each chain iteration will insert the new value into a temp and then
+      /// select on an ICmp with the uninserted value.
+      /// TODO create a pass the recreate the original variable
+      /// InsertElementInst on the llc side.
+
+      auto Callback =
+          [OriginalIdx, &Builder, InsertedValue, &SourceStrategy, I32Ty](
+              const unsigned I, const unsigned Start, const unsigned End) {
+            Value *Source = SourceStrategy.getValue(I);
+            Value *Last = Source;
+            for (unsigned PartIdx = Start;
+                 PartIdx < std::min(End, SourceStrategy.fromElements());
+                 ++PartIdx) {
+
+              Value *CPartIdx = ConstantInt::get(I32Ty, PartIdx - Start);
+              Value *Inserted =
+                  Builder.CreateInsertElement(Last, InsertedValue, CPartIdx);
+              Value *OriginalIdxConst =
+                  ConstantInt::get(OriginalIdx->getType(), PartIdx);
+              Value *ICmp = Builder.CreateICmp(CmpInst::ICMP_EQ,
+                                               OriginalIdxConst, OriginalIdx);
+              Value *Select = Builder.CreateSelect(ICmp, Inserted, Last);
+              Last = Select;
+            }
+            return Last;
+          };
+      Strategy.forEach(std::move(Callback));
+    }
+  } else if (isa<PHINode>(I)) {
+    /// Generate placeholder phis. After we've finished going over the function,
+    /// we go over all the phis and insert the predecessor block and values.
+    auto *VTy = Strategy.To;
+    auto Callback = [&Builder, VTy]() { return Builder.CreatePHI(VTy, 0); };
+    Strategy.forEach(std::move(Callback));
+    PhiNodes.push_back(Strategy);
+  } else if (auto *Cast = dyn_cast<CastInst>(I)) {
+    buildCastStrategy(Strategy, Cast, Builder);
+  } else if (auto *Shuffle = dyn_cast<ShuffleVectorInst>(I)) {
+    SmallVector<std::tuple<Value *, Value *, unsigned>, 16> Values;
+
+    const auto Mask = Shuffle->getShuffleMask();
+    const auto &LeftStrategy = findStrategyFor(Shuffle->getOperand(0), Shuffle);
+    const auto &RightStrategy =
+        findStrategyFor(Shuffle->getOperand(1), Shuffle);
+    assert(LeftStrategy.To == RightStrategy.To);
+
+    getShuffleValues(LeftStrategy, RightStrategy, Mask, Values);
+
+    auto Callback = [&Values, this, Shuffle, &Builder](
+        const unsigned, const unsigned Start, const unsigned End) {
+      return this->shuffleRebuildHelper(Shuffle, Builder, Values, Start, End);
+    };
+    Strategy.forEach(std::move(Callback));
+  } else if (auto *Call = dyn_cast<CallInst>(I)) {
+    // Fix the return and arguments.
+    auto &C = I->getContext();
+    const DataLayout &DL = I->getParent()->getModule()->getDataLayout();
+
+    Value *Called = Call->getCalledValue();
+    auto *FTy = cast<FunctionType>(Called->getType()->getContainedType(0));
+    const auto &FStrategy = FPass.buildStrategy(FTy, DL);
+
+    SmallVector<Value *, 8> NewArgs;
+    ArrayRef<Value *> RetSpace;
+    assert(FStrategy.getRet());
+    assert(FStrategy.getRet().extra() == Strategy.extra());
+    RetSpace = CallReturnAllocMgr.get(FStrategy.getRet(), DL);
+    for (unsigned I = 0; I < FStrategy.getRet().extra(); ++I) {
+      NewArgs.push_back(RetSpace[I]);
+    }
+
+    unsigned ArgIt = 0;
+    for (const auto &ArgS : FStrategy.getArgs()) {
+      Value *Arg = Call->getArgOperand(ArgIt++);
+      if (!ArgS) {
+        NewArgs.push_back(Arg);
+        continue;
+      }
+
+      const auto &Strategy = findStrategyFor(Arg, Call);
+      for (unsigned I = 0; I < Strategy.values(); ++I) {
+        NewArgs.push_back(Strategy.getValue(I));
+      }
+    }
+
+    Called = Builder.CreatePointerCast(
+        Called, FStrategy.newFunctionType()->getPointerTo());
+
+    auto Callback = [&FStrategy, &Builder, &NewArgs, RetSpace, Called, &C, &DL,
+                     Call, &Strategy](const unsigned Part, const unsigned,
+                                      const unsigned) -> Value *{
+      if (Part == 0) {
+        CallInst *NewCall = Builder.CreateCall(Called, NewArgs);
+        NewCall->setAttributes(
+            FStrategy.mapAttrs(Call->getAttributes(), C, DL));
+        return NewCall;
+      } else {
+        const unsigned Alignment = DL.getPrefTypeAlignment(Strategy.To);
+        return Builder.CreateAlignedLoad(RetSpace[Part - 1], Alignment);
+      }
+    };
+    Strategy.forEach(std::move(Callback));
+  } else if (auto *Bin = dyn_cast<BinaryOperator>(I)) {
+    const auto Opcode = Bin->getOpcode();
+    const auto &Left = findStrategyFor(Bin->getOperand(0), Bin);
+    const auto &Right = findStrategyFor(Bin->getOperand(1), Bin);
+
+    auto Callback = [Opcode, &Left, &Right, &Builder, Bin](
+        const unsigned Part, const unsigned, const unsigned) {
+      Value *NewPart = Builder.CreateBinOp(Opcode, Left.getValue(Part),
+                                           Right.getValue(Part));
+      if (auto *NewBin = dyn_cast<BinaryOperator>(NewPart)) {
+        NewBin->copyIRFlags(Bin);
+      }
+      return NewPart;
+    };
+    Strategy.forEach(std::move(Callback));
+  } else if (auto *Cmp = dyn_cast<CmpInst>(I)) {
+    const auto Fixed = fixCmpInstruction(Strategy, Cmp, Builder);
+    (void)Fixed;
+    assert(Fixed);
+  } else if (auto *Select = dyn_cast<SelectInst>(I)) {
+    const auto &Cmp = findStrategyFor(Select->getOperand(0), Select);
+    const auto &Left = findStrategyFor(Select->getOperand(1), Select);
+    const auto &Right = findStrategyFor(Select->getOperand(2), Select);
+
+    auto Callback = [&Builder, &Cmp, &Left, &Right](
+        const unsigned Part, const unsigned, const unsigned) {
+      return Builder.CreateSelect(Cmp.getValue(Part), Left.getValue(Part),
+                                  Right.getValue(Part));
+    };
+    Strategy.forEach(std::move(Callback));
+  } else {
+    I->dump();
+    llvm_unreachable("unhandled instruction");
+  }
+}
+
+void VectorCanonicalizationInstructionPass::buildCastStrategy(
+    InstructionStrategy &Strategy, CastInst *Cast, IRBuilder<> &Builder) {
+  /// Excluding bitcasts and casts that keep the overall vector size constant,
+  /// we have to perform the cast on each element of the vector, and then
+  /// recreate the result vector.
+  /// TODO when the expanded type is still legal, but not the same size.
+  /// I've omitted ^ because PNaCl doesn't support more than one vector width
+  /// anyway.
+  auto *FromTy = Cast->getOperand(0)->getType();
+  const auto Opcode = Cast->getOpcode();
+  switch (Opcode) {
+  default:
+    Cast->dump();
+    llvm_unreachable("unhandled cast instruction");
+  case Instruction::BitCast: {
+    if (FromTy->isVectorTy()) {
+      buildVectorCastStrategy(Strategy, Cast, Builder);
+    } else {
+      Cast->dump();
+      llvm_unreachable("unhandled bitcast (non vector -> vector). TODO?");
+    }
+    break;
+  }
+  case Instruction::IntToPtr:
+  case Instruction::PtrToInt:
+  case Instruction::FPToUI:
+  case Instruction::FPToSI:
+  case Instruction::UIToFP:
+  case Instruction::SIToFP: {
+    const auto SourceSize = DL.getTypeSizeInBits(FromTy);
+    const auto DestSize = DL.getTypeSizeInBits(Cast->getType());
+    if (SourceSize == DestSize) {
+      buildVectorCastStrategy(Strategy, Cast, Builder);
+    } else {
+      buildScalarCastStrategy(Strategy, Cast, Builder);
+    }
+
+    break;
+  }
+  case Instruction::Trunc:
+  case Instruction::ZExt:
+  case Instruction::SExt: {
+    buildScalarCastStrategy(Strategy, Cast, Builder);
+    break;
+  }
+  }
+}
+void VectorCanonicalizationInstructionPass::buildScalarCastStrategy(
+    InstructionStrategy &Strategy, CastInst *Cast, IRBuilder<> &Builder) {
+  const auto &SourceStrategy = findStrategyFor(Cast->getOperand(0), Cast);
+  const auto Opcode = Cast->getOpcode();
+  auto *ToVTy = Strategy.To;
+  auto *ToElementTy = ToVTy->getElementType();
+  auto *I32Ty = IntegerType::get(Cast->getContext(), 32);
+  auto Callback =
+      [Opcode, &SourceStrategy, &Strategy, &Builder, ToVTy, ToElementTy, I32Ty](
+          const unsigned Part, const unsigned Start, const unsigned End) {
+        Value *Inserted = UndefValue::get(ToVTy);
+        for (unsigned I = Start; I < std::min(End, Strategy.fromElements());
+             ++I) {
+          const auto SourcePart = SourceStrategy.splitPart(I);
+          Value *Source = SourceStrategy.getValue(SourcePart);
+          auto *ExtractIdx = ConstantInt::get(
+              I32Ty, I - SourceStrategy.toSliceStart(SourcePart));
+          Value *Extracted = Builder.CreateExtractElement(Source, ExtractIdx);
+          Value *Casted = Builder.CreateCast(Opcode, Extracted, ToElementTy);
+          Inserted = Builder.CreateInsertElement(
+              Inserted, Casted, ConstantInt::get(I32Ty, I - Start));
+        }
+
+        return Inserted;
+      };
+  Strategy.forEach(std::move(Callback));
+}
+void VectorCanonicalizationInstructionPass::buildVectorCastStrategy(
+    InstructionStrategy &Strategy, CastInst *Cast, IRBuilder<> &Builder) {
+  const auto &SourceStrategy = findStrategyFor(Cast->getOperand(0), Cast);
+  const auto Opcode = Cast->getOpcode();
+  auto *ToVTy = Strategy.To;
+
+  auto Callback = [Opcode, &SourceStrategy, &Builder, ToVTy](
+      const unsigned Part, const unsigned, const unsigned) {
+    Value *Source = SourceStrategy.getValue(Part);
+    return Builder.CreateCast(Opcode, Source, ToVTy);
+  };
+  Strategy.forEach(std::move(Callback));
+}
+void VectorCanonicalizationInstructionPass::fixStoreInstruction(
+    StoreInst *OldStore) {
+
+  Value *Src = OldStore->getValueOperand();
+  const auto &ValueStrategy = findStrategyFor(Src, OldStore);
+  if (!ValueStrategy) {
+    return;
+  }
+
+  /// Split up the store.
+  assert(!OldStore->isAtomic() && "Atomic vectors aren't supported" && "TODO?");
+
+  IRBuilder<> Builder(OldStore);
+
+  Value *Dest = OldStore->getPointerOperand();
+
+  const unsigned OriginalAlignment = OldStore->getAlignment();
+
+  auto *I32Ty = IntegerType::get(OldStore->getContext(), 32);
+  const unsigned ElementByteWidth =
+      DL.getTypeSizeInBits(Src->getType()->getVectorElementType()) / 8;
+
+  const auto Rem = ValueStrategy.rem();
+
+  unsigned Parts;
+  if (Rem == 0) {
+    Parts = ValueStrategy.values();
+  } else {
+    Parts = ValueStrategy.extra();
+  }
+  for (unsigned Part = 0; Part < Parts; ++Part) {
+    const uint64_t Start = ValueStrategy.toSliceStart(Part);
+    Value *PartValue = ValueStrategy.getValue(Part);
+
+    // gep -> bitcast to vector type -> store
+    ArrayRef<uint64_t> Indices = {0, Start};
+    Type *IndexedType =
+        GetElementPtrInst::getIndexedType(Dest->getType(), Indices);
+    auto *GEP = Builder.CreateConstGEP2_32(IndexedType, Dest, 0, Start);
+    auto *BC = Builder.CreatePointerCast(GEP, ValueStrategy.To->getPointerTo());
+
+    const unsigned Alignment =
+        MinAlign(OriginalAlignment, ElementByteWidth * Start);
+    Builder.CreateAlignedStore(PartValue, BC, Alignment,
+                               OldStore->isVolatile());
+  }
+
+  if (Rem != 0) {
+    const auto Part = ValueStrategy.extra();
+    Value *PartValue = ValueStrategy.getValue(Part);
+    const uint64_t Start = ValueStrategy.toSliceStart(Part);
+    for (unsigned PartIdx = 0; PartIdx < Rem; ++PartIdx) {
+      // Don't store past the end of the vector.
+      // gep -> scalar store
+      ArrayRef<uint64_t> Indices = {0, PartIdx + Start};
+      Type *IndexedType =
+          GetElementPtrInst::getIndexedType(Dest->getType(), Indices);
+      auto *GEP =
+          Builder.CreateConstGEP2_32(IndexedType, Dest, 0, PartIdx + Start);
+      auto *CPartIdx = ConstantInt::get(I32Ty, PartIdx);
+      Value *Extracted = Builder.CreateExtractElement(PartValue, CPartIdx);
+
+      const unsigned Alignment =
+          MinAlign(OriginalAlignment, ElementByteWidth * (PartIdx + Start));
+      Builder.CreateAlignedStore(Extracted, GEP, Alignment,
+                                 OldStore->isVolatile());
+    }
+  }
+
+  ToDelete.push_back(OldStore);
+}
+void VectorCanonicalizationInstructionPass::fixBitcastInstruction(
+    BitCastInst *BC) {
+  // ie: `bitcast <6 x i32> to i196` or some such awkwardness.
+
+  BC->dump();
+  llvm_unreachable("unhandled vector bitcast. TODO");
+}
+void VectorCanonicalizationInstructionPass::fixExtractElementInstruction(
+    ExtractElementInst *Extract) {
+  Value *Extracted = nullptr;
+  const auto &SourceStrategy = findStrategyFor(Extract->getOperand(0), Extract);
+  if (!SourceStrategy) {
+    return;
+  }
+
+  IRBuilder<> Builder(Extract);
+  auto *I32Ty = IntegerType::get(Extract->getContext(), 32);
+
+  auto *OriginalIdx = Extract->getOperand(1);
+
+  if (isa<ConstantInt>(OriginalIdx) || SourceStrategy.extra() == 0) {
+    Value *NewIdx = nullptr;
+    Value *Source = nullptr;
+    if (auto *CIdx = dyn_cast<ConstantInt>(OriginalIdx)) {
+      auto Idx = CIdx->getZExtValue();
+      const auto SplitIdx = SourceStrategy.splitPart(Idx);
+      const auto ValueIdx =
+          std::min(SplitIdx, (unsigned)SourceStrategy.getExpanded().size() - 1);
+      Source = SourceStrategy.getValue(ValueIdx);
+
+      const auto EIdx = Idx -
+                        SourceStrategy.toSliceStart(
+                            std::min(SourceStrategy.extra(), SplitIdx));
+      NewIdx = ConstantInt::get(I32Ty, EIdx);
+    } else {
+      assert(SourceStrategy.extra() == 0);
+      Source = SourceStrategy.getValue(0);
+      NewIdx = OriginalIdx;
+    }
+    assert(Source && NewIdx);
+    Extracted = Builder.CreateExtractElement(Source, NewIdx);
+  } else {
+    /// Similar to InsertElementInst, chain ICmp + select to find the right
+    /// index.
+    Extracted = UndefValue::get(Extract->getType());
+    for (unsigned Part = 0; Part < SourceStrategy.values(); ++Part) {
+      const unsigned Start = SourceStrategy.toSliceStart(Part);
+      const unsigned End =
+          SourceStrategy.toSliceEnd(Part, SourceStrategy.fromElements());
+      auto *Source = SourceStrategy.getValue(Part);
+      for (unsigned PartIdx = 0; PartIdx + Start < End; ++PartIdx) {
+        auto *NewIdx = ConstantInt::get(I32Ty, PartIdx);
+        Value *ExtractedTemp = Builder.CreateExtractElement(Source, NewIdx);
+
+        Value *COriginalIdx =
+            ConstantInt::get(OriginalIdx->getType(), PartIdx + Start);
+
+        Value *Cmp =
+            Builder.CreateICmp(CmpInst::ICMP_EQ, COriginalIdx, OriginalIdx);
+        Extracted = Builder.CreateSelect(Cmp, ExtractedTemp, Extracted);
+      }
+    }
+  }
+
+  assert(Extracted);
+  Extract->replaceAllUsesWith(Extracted);
+  ToDelete.push_back(Extract);
+}
+void VectorCanonicalizationInstructionPass::fixCallInstruction(CallInst *Call) {
+  auto *Called = Call->getCalledValue();
+  auto *FTy = cast<FunctionType>(Called->getType()->getContainedType(0));
+  auto &FStrategy = FPass.buildStrategy(FTy, DL);
+  if (!FStrategy) {
+    return;
+  }
+
+  assert(!FStrategy.getRet());
+
+  SmallVector<Value *, 8> NewArgs;
+  IRBuilder<> Builder(Call);
+
+  const auto &ArgStrategies = FStrategy.getArgs();
+  assert(ArgStrategies.size() == Call->getNumArgOperands());
+  for (unsigned I = 0; I < ArgStrategies.size(); ++I) {
+    const auto &ArgStrategy = ArgStrategies[I];
+    auto *Param = Call->getArgOperand(I);
+    if (!ArgStrategy) {
+      NewArgs.push_back(Param);
+      continue;
+    }
+
+    const auto &ParamStrategy = findStrategyFor(Param, Call);
+    assert(ParamStrategy);
+    for (Value *Expanded : ParamStrategy.getExpanded()) {
+      NewArgs.push_back(Expanded);
+    }
+  }
+
+  auto *NewFTyPtr = FStrategy.newFunctionType()->getPointerTo();
+  Value *CastedCalled = Builder.CreatePointerCast(Called, NewFTyPtr);
+  CallInst *NewCall = Builder.CreateCall(CastedCalled, NewArgs);
+
+  auto NewAttrs =
+      FStrategy.mapAttrs(Call->getAttributes(), Call->getContext(),
+                         Call->getParent()->getModule()->getDataLayout());
+  NewCall->setAttributes(NewAttrs);
+
+  ToDelete.push_back(Call);
+}
+void VectorCanonicalizationInstructionPass::fixShuffleInstruction(
+    ShuffleVectorInst *Shuffle) {
+  SmallVector<std::tuple<Value *, Value *, unsigned>, 16> Values;
+
+  const auto Mask = Shuffle->getShuffleMask();
+  const auto &LeftStrategy = findStrategyFor(Shuffle->getOperand(0), Shuffle);
+  const auto &RightStrategy = findStrategyFor(Shuffle->getOperand(1), Shuffle);
+
+  if (!LeftStrategy && !RightStrategy) {
+    return;
+  }
+
+  getShuffleValues(LeftStrategy, RightStrategy, Mask, Values);
+
+  const unsigned Start = 0;
+  const unsigned End = Shuffle->getType()->getVectorNumElements();
+
+  IRBuilder<> Builder(Shuffle);
+
+  Value *NewShuffle =
+      shuffleRebuildHelper(Shuffle, Builder, Values, Start, End);
+  Shuffle->replaceAllUsesWith(NewShuffle);
+  ToDelete.push_back(Shuffle);
+}
+void VectorCanonicalizationInstructionPass::fixCastInstruction(CastInst *Cast) {
+  if (!findStrategyFor(Cast->getOperand(0), Cast)) {
+    return;
+  }
+
+  // If we make it here, it means we have a vector size changing cast.
+
+  IRBuilder<> Builder(Cast);
+
+  const auto &SourceStrategy = findStrategyFor(Cast->getOperand(0), Cast);
+  const auto Opcode = Cast->getOpcode();
+  auto *ToVTy = cast<VectorType>(Cast->getType());
+  auto *ToElementTy = ToVTy->getElementType();
+  auto *I32Ty = IntegerType::get(Cast->getContext(), 32);
+
+  Value *Inserted = UndefValue::get(ToVTy);
+  for (unsigned I = 0; I < Cast->getType()->getVectorNumElements(); ++I) {
+    const auto SourcePart = SourceStrategy.splitPart(I);
+    Value *Source = SourceStrategy.getValue(SourcePart);
+    auto *ExtractIdx =
+        ConstantInt::get(I32Ty, I - SourceStrategy.toSliceStart(SourcePart));
+    Value *Extracted = Builder.CreateExtractElement(Source, ExtractIdx);
+    Value *Casted = Builder.CreateCast(Opcode, Extracted, ToElementTy);
+    Inserted = Builder.CreateInsertElement(Inserted, Casted,
+                                           ConstantInt::get(I32Ty, I));
+  }
+
+  Cast->replaceAllUsesWith(Inserted);
+  ToDelete.push_back(Cast);
+}
+
+bool VectorCanonicalizationInstructionPass::fixCmpInstruction(
+    InstructionStrategy &Strategy, CmpInst *Cmp, IRBuilder<> &Builder) {
+  const auto &Left = findStrategyFor(Cmp->getOperand(0), Cmp);
+
+  if (Left.toElements() != Strategy.toElements()) {
+    // The operands were promoted but the cmp's type might be a technically
+    // legal i1 vector.
+    // Force the promotion here.
+    Strategy.To =
+        VectorType::get(Type::getInt1Ty(Cmp->getContext()), Left.toElements());
+  } else if (!Left) {
+    return false;
+  }
+
+  const auto Opcode = Cmp->getOpcode();
+  const auto Predicate = Cmp->getPredicate();
+  const auto &Right = findStrategyFor(Cmp->getOperand(1), Cmp);
+
+  auto Callback = [Opcode, Predicate, &Left, &Right, Cmp, &Builder](
+      const unsigned Part, const unsigned, const unsigned) {
+    switch (Opcode) {
+    default:
+      Cmp->dump();
+      llvm_unreachable("unhandled cmp instruction?");
+    case Instruction::ICmp:
+      return Builder.CreateICmp(Predicate, Left.getValue(Part),
+                                Right.getValue(Part));
+    case Instruction::FCmp:
+      return Builder.CreateFCmp(Predicate, Left.getValue(Part),
+                                Right.getValue(Part));
+    };
+  };
+  Strategy.forEach(std::move(Callback));
+
+  return true;
+}
+
+void VectorCanonicalizationInstructionPass::fixPhiNodes() {
+  /// Now that we've gone over the whole function, fix up the phi nodes.
+  for (const auto &Strategy : PhiNodes) {
+    PHINode *Phi = cast<PHINode>(Strategy.getSource());
+
+    const auto &Expanded = Strategy.getExpanded();
+
+    const unsigned Count = Phi->getNumIncomingValues();
+    for (unsigned I = 0; I < Count; ++I) {
+      Value *Val = Phi->getIncomingValue(I);
+      BasicBlock *BB = Phi->getIncomingBlock(I);
+
+      const auto &ValStrategy = findStrategyFor(Val, BB->getTerminator());
+      assert(ValStrategy.values() == Strategy.values());
+      for (unsigned J = 0; J < Expanded.size(); ++J) {
+        PHINode *ExpandedPhi = cast<PHINode>(Expanded[J]);
+        ExpandedPhi->addIncoming(ValStrategy.getValue(J), BB);
+      }
+    }
+  }
+
+  PhiNodes.clear();
+}
+
+void VectorCanonicalizationInstructionPass::getShuffleValues(
+    const InstructionStrategy &LeftStrategy,
+    const InstructionStrategy &RightStrategy, const SmallVectorImpl<int> &Mask,
+    SmallVectorImpl<std::tuple<Value *, Value *, unsigned>> &Values) const {
+  /// TODO keep the negative indices instead of rewriting them to a shuffle on
+  /// an UndefValue.
+  const auto FirstHalf = LeftStrategy.fromElements();
+
+  for (auto Idx : Mask) {
+    if (Idx < 0) {
+      /// Negative index indicating an undefined value.
+      Value *Val = UndefValue::get(LeftStrategy.To);
+      auto Pair = std::make_tuple(Val, UndefValue::get(LeftStrategy.From), 0);
+      Values.push_back(Pair);
+    } else if ((unsigned)Idx >= FirstHalf) {
+      /// second half
+      const auto RelIdx = Idx - FirstHalf;
+      const auto Part = RightStrategy.splitPart(RelIdx);
+      Value *Value = RightStrategy.getValue(Part);
+      auto Pair = std::make_tuple(Value, RightStrategy.getSource(),
+                                  RelIdx - RightStrategy.toSliceStart(Part));
+      Values.push_back(Pair);
+    } else {
+      /// first half
+      const auto Part = LeftStrategy.splitPart(Idx);
+      Value *Value = LeftStrategy.getValue(Part);
+      auto Pair = std::make_tuple(Value, LeftStrategy.getSource(),
+                                  Idx - LeftStrategy.toSliceStart(Part));
+      Values.push_back(Pair);
+    }
+  }
+}
+Value *VectorCanonicalizationInstructionPass::shuffleRebuildHelper(
+    ShuffleVectorInst *Shuffle, IRBuilder<> &Builder,
+    SmallVectorImpl<std::tuple<Value *, Value *, unsigned>> &Values,
+    const unsigned Start, const unsigned End) {
+
+  bool Identity = true;
+  /// Map identities straight through.
+  Value *Prev = std::get<0>(Values[Start]);
+  for (unsigned I = Start; Identity && I < std::min((size_t)End, Values.size());
+       ++I) {
+    Identity =
+        Prev == std::get<0>(Values[I]) && std::get<2>(Values[I]) == I - Start;
+    if (!Identity) {
+      break;
+    }
+  }
+  if (Identity) {
+    return Prev;
+  }
+
+  SmallVector<std::tuple<Value *, Value *>, 2> Operands;
+
+  auto IsNewOperand = [&Operands](Value *V) {
+    for (auto &Op : Operands) {
+      if (std::get<0>(Op) == V) {
+        return false;
+      }
+    }
+
+    return true;
+  };
+  auto GetOperandOffset = [&Operands](Value *V) {
+    unsigned I = 0;
+    for (auto &Op : Operands) {
+      if (std::get<0>(Op) == V) {
+        break;
+      }
+      ++I;
+    }
+    assert(I < Operands.size());
+
+    return I * std::get<0>(Operands.front())->getType()->getVectorNumElements();
+  };
+
+  SmallVector<int, 8> NewMask;
+
+  auto FillNewMask = [&NewMask, End, Start]() {
+    assert(NewMask.size() != 0);
+    for (unsigned J = NewMask.size(); J < End - Start; ++J) {
+      NewMask.push_back(NewMask.back());
+    }
+  };
+  for (unsigned I = Start; I < std::min((size_t)End, Values.size()); ++I) {
+    const bool IsNew = IsNewOperand(std::get<0>(Values[I]));
+    if (IsNew && Operands.size() < 2) {
+      Operands.push_back(
+          std::make_tuple(std::get<0>(Values[I]), std::get<1>(Values[I])));
+    } else if (IsNew && Operands.size() == 2) {
+      /// We have to chain this shuffle because this part uses more than
+      /// two source parts.
+      const auto Size = NewMask.size();
+      FillNewMask();
+
+      Value *Shuffle = Builder.CreateShuffleVector(
+          std::get<0>(Operands[0]), std::get<0>(Operands[1]), NewMask);
+      NewMask.clear();
+      for (unsigned J = 0; J < Size; ++J) {
+        NewMask.push_back(J);
+      }
+
+      Operands.clear();
+      Operands.push_back(std::make_tuple(Shuffle, nullptr));
+      Operands.push_back(
+          std::make_tuple(std::get<0>(Values[I]), std::get<1>(Values[I])));
+    }
+
+    assert(Operands.size() >= 1 && Operands.size() <= 2);
+    const unsigned Offset = GetOperandOffset(std::get<0>(Values[I]));
+    NewMask.push_back(std::get<2>(Values[I]) + Offset);
+  }
+
+  FillNewMask();
+
+  if (Operands.size() == 1) {
+    // Check for and bypass shuffles the function pass inserted for returns.
+    // This can only happen when the return is expanded.
+    // Not only does this make our generated IR cleaner, it also keeps the test
+    // generator I built for this pass simple.
+    const auto &OperandStrategy =
+        findStrategyFor(std::get<1>(Operands.front()), Shuffle);
+    bool ByPass = OperandStrategy.getValue(OperandStrategy.extra()) ==
+                  std::get<0>(Operands.front());
+    const auto Rem = OperandStrategy.rem();
+    for (unsigned I = 0; ByPass && I < NewMask.size(); ++I) {
+      int ExpectedVal = 0;
+      if (Rem != 0 && I > Rem - 1) {
+        ExpectedVal = Rem - 1;
+      } else {
+        ExpectedVal = I;
+      }
+
+      ByPass = ExpectedVal == NewMask[I];
+    }
+    if (ByPass) {
+      Value *Front = std::get<0>(Operands.front());
+      return Front;
+    }
+
+    auto Push = std::make_tuple(
+        UndefValue::get(std::get<0>(Operands[0])->getType()), nullptr);
+    Operands.push_back(Push);
+  }
+
+  Value *NewShuffle = Builder.CreateShuffleVector(
+      std::get<0>(Operands[0]), std::get<0>(Operands[1]), NewMask);
+  return NewShuffle;
+}
+
+namespace {
+class PNaClVectorCanonicalization : public ModulePass {
+  BitWidthMapper Cfg;
+
+public:
+  static char ID;
+  PNaClVectorCanonicalization() : ModulePass(ID), Cfg() {
+    initializePNaClVectorCanonicalizationPass(*PassRegistry::getPassRegistry());
+    Cfg.NormWidths.push_back(128);
+    Cfg.I1NumElements.push_back(2);
+    Cfg.I1NumElements.push_back(4);
+    Cfg.I1NumElements.push_back(8);
+    Cfg.I1NumElements.push_back(16);
+  }
+
+  bool runOnModule(Module &M);
+};
+char PNaClVectorCanonicalization::ID = 0;
+}
+INITIALIZE_PASS(PNaClVectorCanonicalization, "pnacl-vector-canonicalization",
+                "Convert improper vector types into proper ones", false, false)
+
+ModulePass *llvm::createPNaClVectorCanonicalizationPass() {
+  return new PNaClVectorCanonicalization();
+}
+
+bool PNaClVectorCanonicalization::runOnModule(Module &M) {
+  VectorCanonicalizationFunctionPass FPass(Cfg);
+  FPass.runOnModule(M);
+
+  bool Modified = FPass.modified();
+
+  for (auto FI = M.begin(); FI != M.end(); ++FI) {
+    if (FI->size() == 0) {
+      continue;
+    }
+
+    VectorCanonicalizationInstructionPass IPass(&*FI, Cfg, FPass);
+    IPass.runOnFunction(*FI);
+
+    Modified |= IPass.modified();
+  }
+
+  return Modified;
+}