vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085

1 files changed, 0 insertions, 1069 deletions

diff --git a/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp b/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp
deleted file mode 100644
index 1c2c8aef55bb..000000000000
--- a/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp
+++ /dev/null
@@ -1,1069 +0,0 @@
-//===----- ARMCodeGenPrepare.cpp ------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-/// \file
-/// This pass inserts intrinsics to handle small types that would otherwise be
-/// promoted during legalization. Here we can manually promote types or insert
-/// intrinsics which can handle narrow types that aren't supported by the
-/// register classes.
-//
-//===----------------------------------------------------------------------===//
-
-#include "ARM.h"
-#include "ARMSubtarget.h"
-#include "ARMTargetMachine.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/TargetPassConfig.h"
-#include "llvm/IR/Attributes.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/IRBuilder.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/InstrTypes.h"
-#include "llvm/IR/Instruction.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Intrinsics.h"
-#include "llvm/IR/Type.h"
-#include "llvm/IR/Value.h"
-#include "llvm/IR/Verifier.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/CommandLine.h"
-
-#define DEBUG_TYPE "arm-codegenprepare"
-
-using namespace llvm;
-
-static cl::opt<bool>
-DisableCGP("arm-disable-cgp", cl::Hidden, cl::init(true),
-           cl::desc("Disable ARM specific CodeGenPrepare pass"));
-
-static cl::opt<bool>
-EnableDSP("arm-enable-scalar-dsp", cl::Hidden, cl::init(false),
-          cl::desc("Use DSP instructions for scalar operations"));
-
-static cl::opt<bool>
-EnableDSPWithImms("arm-enable-scalar-dsp-imms", cl::Hidden, cl::init(false),
-                   cl::desc("Use DSP instructions for scalar operations\
-                            with immediate operands"));
-
-// The goal of this pass is to enable more efficient code generation for
-// operations on narrow types (i.e. types with < 32-bits) and this is a
-// motivating IR code example:
-//
-//   define hidden i32 @cmp(i8 zeroext) {
-//     %2 = add i8 %0, -49
-//     %3 = icmp ult i8 %2, 3
-//     ..
-//   }
-//
-// The issue here is that i8 is type-legalized to i32 because i8 is not a
-// legal type. Thus, arithmetic is done in integer-precision, but then the
-// byte value is masked out as follows:
-//
-//   t19: i32 = add t4, Constant:i32<-49>
-//     t24: i32 = and t19, Constant:i32<255>
-//
-// Consequently, we generate code like this:
-//
-//   subs  r0, #49
-//   uxtb  r1, r0
-//   cmp r1, #3
-//
-// This shows that masking out the byte value results in generation of
-// the UXTB instruction. This is not optimal as r0 already contains the byte
-// value we need, and so instead we can just generate:
-//
-//   sub.w r1, r0, #49
-//   cmp r1, #3
-//
-// We achieve this by type promoting the IR to i32 like so for this example:
-//
-//   define i32 @cmp(i8 zeroext %c) {
-//     %0 = zext i8 %c to i32
-//     %c.off = add i32 %0, -49
-//     %1 = icmp ult i32 %c.off, 3
-//     ..
-//   }
-//
-// For this to be valid and legal, we need to prove that the i32 add is
-// producing the same value as the i8 addition, and that e.g. no overflow
-// happens.
-//
-// A brief sketch of the algorithm and some terminology.
-// We pattern match interesting IR patterns:
-// - which have "sources": instructions producing narrow values (i8, i16), and
-// - they have "sinks": instructions consuming these narrow values.
-//
-// We collect all instruction connecting sources and sinks in a worklist, so
-// that we can mutate these instruction and perform type promotion when it is
-// legal to do so.
-
-namespace {
-class IRPromoter {
-  SmallPtrSet<Value*, 8> NewInsts;
-  SmallPtrSet<Instruction*, 4> InstsToRemove;
-  DenseMap<Value*, SmallVector<Type*, 4>> TruncTysMap;
-  SmallPtrSet<Value*, 8> Promoted;
-  Module *M = nullptr;
-  LLVMContext &Ctx;
-  // The type we promote to: always i32
-  IntegerType *ExtTy = nullptr;
-  // The type of the value that the search began from, either i8 or i16.
-  // This defines the max range of the values that we allow in the promoted
-  // tree.
-  IntegerType *OrigTy = nullptr;
-  SetVector<Value*> *Visited;
-  SmallPtrSetImpl<Value*> *Sources;
-  SmallPtrSetImpl<Instruction*> *Sinks;
-  SmallPtrSetImpl<Instruction*> *SafeToPromote;
-  SmallPtrSetImpl<Instruction*> *SafeWrap;
-
-  void ReplaceAllUsersOfWith(Value *From, Value *To);
-  void PrepareWrappingAdds(void);
-  void ExtendSources(void);
-  void ConvertTruncs(void);
-  void PromoteTree(void);
-  void TruncateSinks(void);
-  void Cleanup(void);
-
-public:
-  IRPromoter(Module *M) : M(M), Ctx(M->getContext()),
-                          ExtTy(Type::getInt32Ty(Ctx)) { }
-
-
-  void Mutate(Type *OrigTy,
-              SetVector<Value*> &Visited,
-              SmallPtrSetImpl<Value*> &Sources,
-              SmallPtrSetImpl<Instruction*> &Sinks,
-              SmallPtrSetImpl<Instruction*> &SafeToPromote,
-              SmallPtrSetImpl<Instruction*> &SafeWrap);
-};
-
-class ARMCodeGenPrepare : public FunctionPass {
-  const ARMSubtarget *ST = nullptr;
-  IRPromoter *Promoter = nullptr;
-  std::set<Value*> AllVisited;
-  SmallPtrSet<Instruction*, 8> SafeToPromote;
-  SmallPtrSet<Instruction*, 4> SafeWrap;
-
-  bool isSafeWrap(Instruction *I);
-  bool isSupportedValue(Value *V);
-  bool isLegalToPromote(Value *V);
-  bool TryToPromote(Value *V);
-
-public:
-  static char ID;
-  static unsigned TypeSize;
-  Type *OrigTy = nullptr;
-
-  ARMCodeGenPrepare() : FunctionPass(ID) {}
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<TargetPassConfig>();
-  }
-
-  StringRef getPassName() const override { return "ARM IR optimizations"; }
-
-  bool doInitialization(Module &M) override;
-  bool runOnFunction(Function &F) override;
-  bool doFinalization(Module &M) override;
-};
-
-}
-
-static bool GenerateSignBits(Value *V) {
-  if (!isa<Instruction>(V))
-    return false;
-
-  unsigned Opc = cast<Instruction>(V)->getOpcode();
-  return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
-         Opc == Instruction::SRem || Opc == Instruction::SExt;
-}
-
-static bool EqualTypeSize(Value *V) {
-  return V->getType()->getScalarSizeInBits() == ARMCodeGenPrepare::TypeSize;
-}
-
-static bool LessOrEqualTypeSize(Value *V) {
-  return V->getType()->getScalarSizeInBits() <= ARMCodeGenPrepare::TypeSize;
-}
-
-static bool GreaterThanTypeSize(Value *V) {
-  return V->getType()->getScalarSizeInBits() > ARMCodeGenPrepare::TypeSize;
-}
-
-static bool LessThanTypeSize(Value *V) {
-  return V->getType()->getScalarSizeInBits() < ARMCodeGenPrepare::TypeSize;
-}
-
-/// Some instructions can use 8- and 16-bit operands, and we don't need to
-/// promote anything larger. We disallow booleans to make life easier when
-/// dealing with icmps but allow any other integer that is <= 16 bits. Void
-/// types are accepted so we can handle switches.
-static bool isSupportedType(Value *V) {
-  Type *Ty = V->getType();
-
-  // Allow voids and pointers, these won't be promoted.
-  if (Ty->isVoidTy() || Ty->isPointerTy())
-    return true;
-
-  if (auto *Ld = dyn_cast<LoadInst>(V))
-    Ty = cast<PointerType>(Ld->getPointerOperandType())->getElementType();
-
-  if (!isa<IntegerType>(Ty) ||
-      cast<IntegerType>(V->getType())->getBitWidth() == 1)
-    return false;
-
-  return LessOrEqualTypeSize(V);
-}
-
-/// Return true if the given value is a source in the use-def chain, producing
-/// a narrow 'TypeSize' value. These values will be zext to start the promotion
-/// of the tree to i32. We guarantee that these won't populate the upper bits
-/// of the register. ZExt on the loads will be free, and the same for call
-/// return values because we only accept ones that guarantee a zeroext ret val.
-/// Many arguments will have the zeroext attribute too, so those would be free
-/// too.
-static bool isSource(Value *V) {
-  if (!isa<IntegerType>(V->getType()))
-    return false;
-
-  // TODO Allow zext to be sources.
-  if (isa<Argument>(V))
-    return true;
-  else if (isa<LoadInst>(V))
-    return true;
-  else if (isa<BitCastInst>(V))
-    return true;
-  else if (auto *Call = dyn_cast<CallInst>(V))
-    return Call->hasRetAttr(Attribute::AttrKind::ZExt);
-  else if (auto *Trunc = dyn_cast<TruncInst>(V))
-    return EqualTypeSize(Trunc);
-  return false;
-}
-
-/// Return true if V will require any promoted values to be truncated for the
-/// the IR to remain valid. We can't mutate the value type of these
-/// instructions.
-static bool isSink(Value *V) {
-  // TODO The truncate also isn't actually necessary because we would already
-  // proved that the data value is kept within the range of the original data
-  // type.
-
-  // Sinks are:
-  // - points where the value in the register is being observed, such as an
-  //   icmp, switch or store.
-  // - points where value types have to match, such as calls and returns.
-  // - zext are included to ease the transformation and are generally removed
-  //   later on.
-  if (auto *Store = dyn_cast<StoreInst>(V))
-    return LessOrEqualTypeSize(Store->getValueOperand());
-  if (auto *Return = dyn_cast<ReturnInst>(V))
-    return LessOrEqualTypeSize(Return->getReturnValue());
-  if (auto *ZExt = dyn_cast<ZExtInst>(V))
-    return GreaterThanTypeSize(ZExt);
-  if (auto *Switch = dyn_cast<SwitchInst>(V))
-    return LessThanTypeSize(Switch->getCondition());
-  if (auto *ICmp = dyn_cast<ICmpInst>(V))
-    return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
-
-  return isa<CallInst>(V);
-}
-
-/// Return whether this instruction can safely wrap.
-bool ARMCodeGenPrepare::isSafeWrap(Instruction *I) {
-  // We can support a, potentially, wrapping instruction (I) if:
-  // - It is only used by an unsigned icmp.
-  // - The icmp uses a constant.
-  // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
-  //   around zero to become a larger number than before.
-  // - The wrapping instruction (I) also uses a constant.
-  //
-  // We can then use the two constants to calculate whether the result would
-  // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
-  // just underflows the range, the icmp would give the same result whether the
-  // result has been truncated or not. We calculate this by:
-  // - Zero extending both constants, if needed, to 32-bits.
-  // - Take the absolute value of I's constant, adding this to the icmp const.
-  // - Check that this value is not out of range for small type. If it is, it
-  //   means that it has underflowed enough to wrap around the icmp constant.
-  //
-  // For example:
-  //
-  // %sub = sub i8 %a, 2
-  // %cmp = icmp ule i8 %sub, 254
-  //
-  // If %a = 0, %sub = -2 == FE == 254
-  // But if this is evalulated as a i32
-  // %sub = -2 == FF FF FF FE == 4294967294
-  // So the unsigned compares (i8 and i32) would not yield the same result.
-  //
-  // Another way to look at it is:
-  // %a - 2 <= 254
-  // %a + 2 <= 254 + 2
-  // %a <= 256
-  // And we can't represent 256 in the i8 format, so we don't support it.
-  //
-  // Whereas:
-  //
-  // %sub i8 %a, 1
-  // %cmp = icmp ule i8 %sub, 254
-  //
-  // If %a = 0, %sub = -1 == FF == 255
-  // As i32:
-  // %sub = -1 == FF FF FF FF == 4294967295
-  //
-  // In this case, the unsigned compare results would be the same and this
-  // would also be true for ult, uge and ugt:
-  // - (255 < 254) == (0xFFFFFFFF < 254) == false
-  // - (255 <= 254) == (0xFFFFFFFF <= 254) == false
-  // - (255 > 254) == (0xFFFFFFFF > 254) == true
-  // - (255 >= 254) == (0xFFFFFFFF >= 254) == true
-  //
-  // To demonstrate why we can't handle increasing values:
-  //
-  // %add = add i8 %a, 2
-  // %cmp = icmp ult i8 %add, 127
-  //
-  // If %a = 254, %add = 256 == (i8 1)
-  // As i32:
-  // %add = 256
-  //
-  // (1 < 127) != (256 < 127)
-
-  unsigned Opc = I->getOpcode();
-  if (Opc != Instruction::Add && Opc != Instruction::Sub)
-    return false;
-
-  if (!I->hasOneUse() ||
-      !isa<ICmpInst>(*I->user_begin()) ||
-      !isa<ConstantInt>(I->getOperand(1)))
-    return false;
-
-  ConstantInt *OverflowConst = cast<ConstantInt>(I->getOperand(1));
-  bool NegImm = OverflowConst->isNegative();
-  bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
-                       ((Opc == Instruction::Add) && NegImm);
-  if (!IsDecreasing)
-    return false;
-
-  // Don't support an icmp that deals with sign bits.
-  auto *CI = cast<ICmpInst>(*I->user_begin());
-  if (CI->isSigned() || CI->isEquality())
-    return false;
-
-  ConstantInt *ICmpConst = nullptr;
-  if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
-    ICmpConst = Const;
-  else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
-    ICmpConst = Const;
-  else
-    return false;
-
-  // Now check that the result can't wrap on itself.
-  APInt Total = ICmpConst->getValue().getBitWidth() < 32 ?
-    ICmpConst->getValue().zext(32) : ICmpConst->getValue();
-
-  Total += OverflowConst->getValue().getBitWidth() < 32 ?
-    OverflowConst->getValue().abs().zext(32) : OverflowConst->getValue().abs();
-
-  APInt Max = APInt::getAllOnesValue(ARMCodeGenPrepare::TypeSize);
-
-  if (Total.getBitWidth() > Max.getBitWidth()) {
-    if (Total.ugt(Max.zext(Total.getBitWidth())))
-      return false;
-  } else if (Max.getBitWidth() > Total.getBitWidth()) {
-    if (Total.zext(Max.getBitWidth()).ugt(Max))
-      return false;
-  } else if (Total.ugt(Max))
-    return false;
-
-  LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n");
-  SafeWrap.insert(I);
-  return true;
-}
-
-static bool shouldPromote(Value *V) {
-  if (!isa<IntegerType>(V->getType()) || isSink(V))
-    return false;
-
-  if (isSource(V))
-    return true;
-
-  auto *I = dyn_cast<Instruction>(V);
-  if (!I)
-    return false;
-
-  if (isa<ICmpInst>(I))
-    return false;
-
-  return true;
-}
-
-/// Return whether we can safely mutate V's type to ExtTy without having to be
-/// concerned with zero extending or truncation.
-static bool isPromotedResultSafe(Value *V) {
-  if (GenerateSignBits(V))
-    return false;
-
-  if (!isa<Instruction>(V))
-    return true;
-
-  if (!isa<OverflowingBinaryOperator>(V))
-    return true;
-
-  return cast<Instruction>(V)->hasNoUnsignedWrap();
-}
-
-/// Return the intrinsic for the instruction that can perform the same
-/// operation but on a narrow type. This is using the parallel dsp intrinsics
-/// on scalar values.
-static Intrinsic::ID getNarrowIntrinsic(Instruction *I) {
-  // Whether we use the signed or unsigned versions of these intrinsics
-  // doesn't matter because we're not using the GE bits that they set in
-  // the APSR.
-  switch(I->getOpcode()) {
-  default:
-    break;
-  case Instruction::Add:
-    return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_uadd16 :
-      Intrinsic::arm_uadd8;
-  case Instruction::Sub:
-    return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_usub16 :
-      Intrinsic::arm_usub8;
-  }
-  llvm_unreachable("unhandled opcode for narrow intrinsic");
-}
-
-void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
-  SmallVector<Instruction*, 4> Users;
-  Instruction *InstTo = dyn_cast<Instruction>(To);
-  bool ReplacedAll = true;
-
-  LLVM_DEBUG(dbgs() << "ARM CGP: Replacing " << *From << " with " << *To
-             << "\n");
-
-  for (Use &U : From->uses()) {
-    auto *User = cast<Instruction>(U.getUser());
-    if (InstTo && User->isIdenticalTo(InstTo)) {
-      ReplacedAll = false;
-      continue;
-    }
-    Users.push_back(User);
-  }
-
-  for (auto *U : Users)
-    U->replaceUsesOfWith(From, To);
-
-  if (ReplacedAll)
-    if (auto *I = dyn_cast<Instruction>(From))
-      InstsToRemove.insert(I);
-}
-
-void IRPromoter::PrepareWrappingAdds() {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Prepare underflowing adds.\n");
-  IRBuilder<> Builder{Ctx};
-
-  // For adds that safely wrap and use a negative immediate as operand 1, we
-  // create an equivalent instruction using a positive immediate.
-  // That positive immediate can then be zext along with all the other
-  // immediates later.
-  for (auto *I : *SafeWrap) {
-    if (I->getOpcode() != Instruction::Add)
-      continue;
-
-    LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n");
-    assert((isa<ConstantInt>(I->getOperand(1)) &&
-            cast<ConstantInt>(I->getOperand(1))->isNegative()) &&
-           "Wrapping should have a negative immediate as the second operand");
-
-    auto Const = cast<ConstantInt>(I->getOperand(1));
-    auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
-    Builder.SetInsertPoint(I);
-    Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst);
-    if (auto *NewInst = dyn_cast<Instruction>(NewVal)) {
-      NewInst->copyIRFlags(I);
-      NewInsts.insert(NewInst);
-    }
-    InstsToRemove.insert(I);
-    I->replaceAllUsesWith(NewVal);
-    LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n");
-  }
-  for (auto *I : NewInsts)
-    Visited->insert(I);
-}
-
-void IRPromoter::ExtendSources() {
-  IRBuilder<> Builder{Ctx};
-
-  auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
-    assert(V->getType() != ExtTy && "zext already extends to i32");
-    LLVM_DEBUG(dbgs() << "ARM CGP: Inserting ZExt for " << *V << "\n");
-    Builder.SetInsertPoint(InsertPt);
-    if (auto *I = dyn_cast<Instruction>(V))
-      Builder.SetCurrentDebugLocation(I->getDebugLoc());
-
-    Value *ZExt = Builder.CreateZExt(V, ExtTy);
-    if (auto *I = dyn_cast<Instruction>(ZExt)) {
-      if (isa<Argument>(V))
-        I->moveBefore(InsertPt);
-      else
-        I->moveAfter(InsertPt);
-      NewInsts.insert(I);
-    }
-
-    ReplaceAllUsersOfWith(V, ZExt);
-  };
-
-  // Now, insert extending instructions between the sources and their users.
-  LLVM_DEBUG(dbgs() << "ARM CGP: Promoting sources:\n");
-  for (auto V : *Sources) {
-    LLVM_DEBUG(dbgs() << " - " << *V << "\n");
-    if (auto *I = dyn_cast<Instruction>(V))
-      InsertZExt(I, I);
-    else if (auto *Arg = dyn_cast<Argument>(V)) {
-      BasicBlock &BB = Arg->getParent()->front();
-      InsertZExt(Arg, &*BB.getFirstInsertionPt());
-    } else {
-      llvm_unreachable("unhandled source that needs extending");
-    }
-    Promoted.insert(V);
-  }
-}
-
-void IRPromoter::PromoteTree() {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Mutating the tree..\n");
-
-  IRBuilder<> Builder{Ctx};
-
-  // Mutate the types of the instructions within the tree. Here we handle
-  // constant operands.
-  for (auto *V : *Visited) {
-    if (Sources->count(V))
-      continue;
-
-    auto *I = cast<Instruction>(V);
-    if (Sinks->count(I))
-      continue;
-
-    for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
-      Value *Op = I->getOperand(i);
-      if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
-        continue;
-
-      if (auto *Const = dyn_cast<ConstantInt>(Op)) {
-        Constant *NewConst = ConstantExpr::getZExt(Const, ExtTy);
-        I->setOperand(i, NewConst);
-      } else if (isa<UndefValue>(Op))
-        I->setOperand(i, UndefValue::get(ExtTy));
-    }
-
-    if (shouldPromote(I)) {
-      I->mutateType(ExtTy);
-      Promoted.insert(I);
-    }
-  }
-
-  // Finally, any instructions that should be promoted but haven't yet been,
-  // need to be handled using intrinsics.
-  for (auto *V : *Visited) {
-    auto *I = dyn_cast<Instruction>(V);
-    if (!I)
-      continue;
-
-    if (Sources->count(I) || Sinks->count(I))
-      continue;
-
-    if (!shouldPromote(I) || SafeToPromote->count(I) || NewInsts.count(I))
-      continue;
-
-    assert(EnableDSP && "DSP intrinisc insertion not enabled!");
-
-    // Replace unsafe instructions with appropriate intrinsic calls.
-    LLVM_DEBUG(dbgs() << "ARM CGP: Inserting DSP intrinsic for "
-               << *I << "\n");
-    Function *DSPInst =
-      Intrinsic::getDeclaration(M, getNarrowIntrinsic(I));
-    Builder.SetInsertPoint(I);
-    Builder.SetCurrentDebugLocation(I->getDebugLoc());
-    Value *Args[] = { I->getOperand(0), I->getOperand(1) };
-    CallInst *Call = Builder.CreateCall(DSPInst, Args);
-    NewInsts.insert(Call);
-    ReplaceAllUsersOfWith(I, Call);
-  }
-}
-
-void IRPromoter::TruncateSinks() {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Fixing up the sinks:\n");
-
-  IRBuilder<> Builder{Ctx};
-
-  auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction* {
-    if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
-      return nullptr;
-
-    if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources->count(V))
-      return nullptr;
-
-    LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy << " Trunc for "
-               << *V << "\n");
-    Builder.SetInsertPoint(cast<Instruction>(V));
-    auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
-    if (Trunc)
-      NewInsts.insert(Trunc);
-    return Trunc;
-  };
-
-  // Fix up any stores or returns that use the results of the promoted
-  // chain.
-  for (auto I : *Sinks) {
-    LLVM_DEBUG(dbgs() << "ARM CGP: For Sink: " << *I << "\n");
-
-    // Handle calls separately as we need to iterate over arg operands.
-    if (auto *Call = dyn_cast<CallInst>(I)) {
-      for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
-        Value *Arg = Call->getArgOperand(i);
-        Type *Ty = TruncTysMap[Call][i];
-        if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
-          Trunc->moveBefore(Call);
-          Call->setArgOperand(i, Trunc);
-        }
-      }
-      continue;
-    }
-
-    // Special case switches because we need to truncate the condition.
-    if (auto *Switch = dyn_cast<SwitchInst>(I)) {
-      Type *Ty = TruncTysMap[Switch][0];
-      if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
-        Trunc->moveBefore(Switch);
-        Switch->setCondition(Trunc);
-      }
-      continue;
-    }
-
-    // Now handle the others.
-    for (unsigned i = 0; i < I->getNumOperands(); ++i) {
-      Type *Ty = TruncTysMap[I][i];
-      if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
-        Trunc->moveBefore(I);
-        I->setOperand(i, Trunc);
-      }
-    }
-  }
-}
-
-void IRPromoter::Cleanup() {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Cleanup..\n");
-  // Some zexts will now have become redundant, along with their trunc
-  // operands, so remove them
-  for (auto V : *Visited) {
-    if (!isa<ZExtInst>(V))
-      continue;
-
-    auto ZExt = cast<ZExtInst>(V);
-    if (ZExt->getDestTy() != ExtTy)
-      continue;
-
-    Value *Src = ZExt->getOperand(0);
-    if (ZExt->getSrcTy() == ZExt->getDestTy()) {
-      LLVM_DEBUG(dbgs() << "ARM CGP: Removing unnecessary cast: " << *ZExt
-                 << "\n");
-      ReplaceAllUsersOfWith(ZExt, Src);
-      continue;
-    }
-
-    // Unless they produce a value that is narrower than ExtTy, we can
-    // replace the result of the zext with the input of a newly inserted
-    // trunc.
-    if (NewInsts.count(Src) && isa<TruncInst>(Src) &&
-        Src->getType() == OrigTy) {
-      auto *Trunc = cast<TruncInst>(Src);
-      assert(Trunc->getOperand(0)->getType() == ExtTy &&
-             "expected inserted trunc to be operating on i32");
-      ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
-    }
-  }
-
-  for (auto *I : InstsToRemove) {
-    LLVM_DEBUG(dbgs() << "ARM CGP: Removing " << *I << "\n");
-    I->dropAllReferences();
-    I->eraseFromParent();
-  }
-
-  InstsToRemove.clear();
-  NewInsts.clear();
-  TruncTysMap.clear();
-  Promoted.clear();
-  SafeToPromote->clear();
-  SafeWrap->clear();
-}
-
-void IRPromoter::ConvertTruncs() {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Converting truncs..\n");
-  IRBuilder<> Builder{Ctx};
-
-  for (auto *V : *Visited) {
-    if (!isa<TruncInst>(V) || Sources->count(V))
-      continue;
-
-    auto *Trunc = cast<TruncInst>(V);
-    Builder.SetInsertPoint(Trunc);
-    IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
-    IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
-
-    unsigned NumBits = DestTy->getScalarSizeInBits();
-    ConstantInt *Mask =
-      ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());
-    Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
-
-    if (auto *I = dyn_cast<Instruction>(Masked))
-      NewInsts.insert(I);
-
-    ReplaceAllUsersOfWith(Trunc, Masked);
-  }
-}
-
-void IRPromoter::Mutate(Type *OrigTy,
-                        SetVector<Value*> &Visited,
-                        SmallPtrSetImpl<Value*> &Sources,
-                        SmallPtrSetImpl<Instruction*> &Sinks,
-                        SmallPtrSetImpl<Instruction*> &SafeToPromote,
-                        SmallPtrSetImpl<Instruction*> &SafeWrap) {
-  LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from "
-             << ARMCodeGenPrepare::TypeSize << " to 32-bits\n");
-
-  assert(isa<IntegerType>(OrigTy) && "expected integer type");
-  this->OrigTy = cast<IntegerType>(OrigTy);
-  assert(OrigTy->getPrimitiveSizeInBits() < ExtTy->getPrimitiveSizeInBits() &&
-         "original type not smaller than extended type");
-
-  this->Visited = &Visited;
-  this->Sources = &Sources;
-  this->Sinks = &Sinks;
-  this->SafeToPromote = &SafeToPromote;
-  this->SafeWrap = &SafeWrap;
-
-  // Cache original types of the values that will likely need truncating
-  for (auto *I : Sinks) {
-    if (auto *Call = dyn_cast<CallInst>(I)) {
-      for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
-        Value *Arg = Call->getArgOperand(i);
-        TruncTysMap[Call].push_back(Arg->getType());
-      }
-    } else if (auto *Switch = dyn_cast<SwitchInst>(I))
-      TruncTysMap[I].push_back(Switch->getCondition()->getType());
-    else {
-      for (unsigned i = 0; i < I->getNumOperands(); ++i)
-        TruncTysMap[I].push_back(I->getOperand(i)->getType());
-    }
-  }
-  for (auto *V : Visited) {
-    if (!isa<TruncInst>(V) || Sources.count(V))
-      continue;
-    auto *Trunc = cast<TruncInst>(V);
-    TruncTysMap[Trunc].push_back(Trunc->getDestTy());
-  }
-
-  // Convert adds using negative immediates to equivalent instructions that use
-  // positive constants.
-  PrepareWrappingAdds();
-
-  // Insert zext instructions between sources and their users.
-  ExtendSources();
-
-  // Promote visited instructions, mutating their types in place. Also insert
-  // DSP intrinsics, if enabled, for adds and subs which would be unsafe to
-  // promote.
-  PromoteTree();
-
-  // Convert any truncs, that aren't sources, into AND masks.
-  ConvertTruncs();
-
-  // Insert trunc instructions for use by calls, stores etc...
-  TruncateSinks();
-
-  // Finally, remove unecessary zexts and truncs, delete old instructions and
-  // clear the data structures.
-  Cleanup();
-
-  LLVM_DEBUG(dbgs() << "ARM CGP: Mutation complete\n");
-}
-
-/// We accept most instructions, as well as Arguments and ConstantInsts. We
-/// Disallow casts other than zext and truncs and only allow calls if their
-/// return value is zeroext. We don't allow opcodes that can introduce sign
-/// bits.
-bool ARMCodeGenPrepare::isSupportedValue(Value *V) {
-  if (auto *I = dyn_cast<Instruction>(V)) {
-    switch (I->getOpcode()) {
-    default:
-      return isa<BinaryOperator>(I) && isSupportedType(I) &&
-             !GenerateSignBits(I);
-    case Instruction::GetElementPtr:
-    case Instruction::Store:
-    case Instruction::Br:
-    case Instruction::Switch:
-      return true;
-    case Instruction::PHI:
-    case Instruction::Select:
-    case Instruction::Ret:
-    case Instruction::Load:
-    case Instruction::Trunc:
-    case Instruction::BitCast:
-      return isSupportedType(I);
-    case Instruction::ZExt:
-      return isSupportedType(I->getOperand(0));
-    case Instruction::ICmp:
-      // Now that we allow small types than TypeSize, only allow icmp of
-      // TypeSize because they will require a trunc to be legalised.
-      // TODO: Allow icmp of smaller types, and calculate at the end
-      // whether the transform would be beneficial.
-      if (isa<PointerType>(I->getOperand(0)->getType()))
-        return true;
-      return EqualTypeSize(I->getOperand(0));
-    case Instruction::Call: {
-      // Special cases for calls as we need to check for zeroext
-      // TODO We should accept calls even if they don't have zeroext, as they
-      // can still be sinks.
-      auto *Call = cast<CallInst>(I);
-      return isSupportedType(Call) &&
-             Call->hasRetAttr(Attribute::AttrKind::ZExt);
-    }
-    }
-  } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
-    return isSupportedType(V);
-  } else if (isa<Argument>(V))
-    return isSupportedType(V);
-
-  return isa<BasicBlock>(V);
-}
-
-/// Check that the type of V would be promoted and that the original type is
-/// smaller than the targeted promoted type. Check that we're not trying to
-/// promote something larger than our base 'TypeSize' type.
-bool ARMCodeGenPrepare::isLegalToPromote(Value *V) {
-
-  auto *I = dyn_cast<Instruction>(V);
-  if (!I)
-    return true;
-
-  if (SafeToPromote.count(I))
-   return true;
-
-  if (isPromotedResultSafe(V) || isSafeWrap(I)) {
-    SafeToPromote.insert(I);
-    return true;
-  }
-
-  if (I->getOpcode() != Instruction::Add && I->getOpcode() != Instruction::Sub)
-    return false;
-
-  // If promotion is not safe, can we use a DSP instruction to natively
-  // handle the narrow type?
-  if (!ST->hasDSP() || !EnableDSP || !isSupportedType(I))
-    return false;
-
-  if (ST->isThumb() && !ST->hasThumb2())
-    return false;
-
-  // TODO
-  // Would it be profitable? For Thumb code, these parallel DSP instructions
-  // are only Thumb-2, so we wouldn't be able to dual issue on Cortex-M33. For
-  // Cortex-A, specifically Cortex-A72, the latency is double and throughput is
-  // halved. They also do not take immediates as operands.
-  for (auto &Op : I->operands()) {
-    if (isa<Constant>(Op)) {
-      if (!EnableDSPWithImms)
-        return false;
-    }
-  }
-  LLVM_DEBUG(dbgs() << "ARM CGP: Will use an intrinsic for: " << *I << "\n");
-  return true;
-}
-
-bool ARMCodeGenPrepare::TryToPromote(Value *V) {
-  OrigTy = V->getType();
-  TypeSize = OrigTy->getPrimitiveSizeInBits();
-  if (TypeSize > 16 || TypeSize < 8)
-    return false;
-
-  SafeToPromote.clear();
-  SafeWrap.clear();
-
-  if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
-    return false;
-
-  LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << ", TypeSize = "
-             << TypeSize << "\n");
-
-  SetVector<Value*> WorkList;
-  SmallPtrSet<Value*, 8> Sources;
-  SmallPtrSet<Instruction*, 4> Sinks;
-  SetVector<Value*> CurrentVisited;
-  WorkList.insert(V);
-
-  // Return true if V was added to the worklist as a supported instruction,
-  // if it was already visited, or if we don't need to explore it (e.g.
-  // pointer values and GEPs), and false otherwise.
-  auto AddLegalInst = [&](Value *V) {
-    if (CurrentVisited.count(V))
-      return true;
-
-    // Ignore GEPs because they don't need promoting and the constant indices
-    // will prevent the transformation.
-    if (isa<GetElementPtrInst>(V))
-      return true;
-
-    if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
-      LLVM_DEBUG(dbgs() << "ARM CGP: Can't handle: " << *V << "\n");
-      return false;
-    }
-
-    WorkList.insert(V);
-    return true;
-  };
-
-  // Iterate through, and add to, a tree of operands and users in the use-def.
-  while (!WorkList.empty()) {
-    Value *V = WorkList.back();
-    WorkList.pop_back();
-    if (CurrentVisited.count(V))
-      continue;
-
-    // Ignore non-instructions, other than arguments.
-    if (!isa<Instruction>(V) && !isSource(V))
-      continue;
-
-    // If we've already visited this value from somewhere, bail now because
-    // the tree has already been explored.
-    // TODO: This could limit the transform, ie if we try to promote something
-    // from an i8 and fail first, before trying an i16.
-    if (AllVisited.count(V))
-      return false;
-
-    CurrentVisited.insert(V);
-    AllVisited.insert(V);
-
-    // Calls can be both sources and sinks.
-    if (isSink(V))
-      Sinks.insert(cast<Instruction>(V));
-
-    if (isSource(V))
-      Sources.insert(V);
-
-    if (!isSink(V) && !isSource(V)) {
-      if (auto *I = dyn_cast<Instruction>(V)) {
-        // Visit operands of any instruction visited.
-        for (auto &U : I->operands()) {
-          if (!AddLegalInst(U))
-            return false;
-        }
-      }
-    }
-
-    // Don't visit users of a node which isn't going to be mutated unless its a
-    // source.
-    if (isSource(V) || shouldPromote(V)) {
-      for (Use &U : V->uses()) {
-        if (!AddLegalInst(U.getUser()))
-          return false;
-      }
-    }
-  }
-
-  LLVM_DEBUG(dbgs() << "ARM CGP: Visited nodes:\n";
-             for (auto *I : CurrentVisited)
-               I->dump();
-             );
-  unsigned ToPromote = 0;
-  for (auto *V : CurrentVisited) {
-    if (Sources.count(V))
-      continue;
-    if (Sinks.count(cast<Instruction>(V)))
-      continue;
-    ++ToPromote;
-  }
-
-  if (ToPromote < 2)
-    return false;
-
-  Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote,
-                   SafeWrap);
-  return true;
-}
-
-bool ARMCodeGenPrepare::doInitialization(Module &M) {
-  Promoter = new IRPromoter(&M);
-  return false;
-}
-
-bool ARMCodeGenPrepare::runOnFunction(Function &F) {
-  if (skipFunction(F) || DisableCGP)
-    return false;
-
-  auto *TPC = &getAnalysis<TargetPassConfig>();
-  if (!TPC)
-    return false;
-
-  const TargetMachine &TM = TPC->getTM<TargetMachine>();
-  ST = &TM.getSubtarget<ARMSubtarget>(F);
-  bool MadeChange = false;
-  LLVM_DEBUG(dbgs() << "ARM CGP: Running on " << F.getName() << "\n");
-
-  // Search up from icmps to try to promote their operands.
-  for (BasicBlock &BB : F) {
-    auto &Insts = BB.getInstList();
-    for (auto &I : Insts) {
-      if (AllVisited.count(&I))
-        continue;
-
-      if (isa<ICmpInst>(I)) {
-        auto &CI = cast<ICmpInst>(I);
-
-        // Skip signed or pointer compares
-        if (CI.isSigned() || !isa<IntegerType>(CI.getOperand(0)->getType()))
-          continue;
-
-        LLVM_DEBUG(dbgs() << "ARM CGP: Searching from: " << CI << "\n");
-
-        for (auto &Op : CI.operands()) {
-          if (auto *I = dyn_cast<Instruction>(Op))
-            MadeChange |= TryToPromote(I);
-        }
-      }
-    }
-    LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
-                dbgs() << F;
-                report_fatal_error("Broken function after type promotion");
-               });
-  }
-  if (MadeChange)
-    LLVM_DEBUG(dbgs() << "After ARMCodeGenPrepare: " << F << "\n");
-
-  return MadeChange;
-}
-
-bool ARMCodeGenPrepare::doFinalization(Module &M) {
-  delete Promoter;
-  return false;
-}
-
-INITIALIZE_PASS_BEGIN(ARMCodeGenPrepare, DEBUG_TYPE,
-                      "ARM IR optimizations", false, false)
-INITIALIZE_PASS_END(ARMCodeGenPrepare, DEBUG_TYPE, "ARM IR optimizations",
-                    false, false)
-
-char ARMCodeGenPrepare::ID = 0;
-unsigned ARMCodeGenPrepare::TypeSize = 0;
-
-FunctionPass *llvm::createARMCodeGenPreparePass() {
-  return new ARMCodeGenPrepare();
-}