contrib/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp

   1 //===----- ARMCodeGenPrepare.cpp ------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file
  11 /// This pass inserts intrinsics to handle small types that would otherwise be
  12 /// promoted during legalization. Here we can manually promote types or insert
  13 /// intrinsics which can handle narrow types that aren't supported by the
  14 /// register classes.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "ARM.h"
  19 #include "ARMSubtarget.h"
  20 #include "ARMTargetMachine.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/CodeGen/Passes.h"
  23 #include "llvm/CodeGen/TargetPassConfig.h"
  24 #include "llvm/IR/Attributes.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/Constants.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/IntrinsicInst.h"
  32 #include "llvm/IR/Intrinsics.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/IR/Value.h"
  35 #include "llvm/IR/Verifier.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/Support/Casting.h"
  38 #include "llvm/Support/CommandLine.h"
  39
  40 #define DEBUG_TYPE "arm-codegenprepare"
  41
  42 using namespace llvm;
  43
  44 static cl::opt<bool>
  45 DisableCGP("arm-disable-cgp", cl::Hidden, cl::init(true),
  46            cl::desc("Disable ARM specific CodeGenPrepare pass"));
  47
  48 static cl::opt<bool>
  49 EnableDSP("arm-enable-scalar-dsp", cl::Hidden, cl::init(false),
  50           cl::desc("Use DSP instructions for scalar operations"));
  51
  52 static cl::opt<bool>
  53 EnableDSPWithImms("arm-enable-scalar-dsp-imms", cl::Hidden, cl::init(false),
  54                    cl::desc("Use DSP instructions for scalar operations\
  55                             with immediate operands"));
  56
  57 namespace {
  58
  59 class IRPromoter {
  60   SmallPtrSet<Value*, 8> NewInsts;
  61   SmallVector<Instruction*, 4> InstsToRemove;
  62   Module *M = nullptr;
  63   LLVMContext &Ctx;
  64
  65 public:
  66   IRPromoter(Module *M) : M(M), Ctx(M->getContext()) { }
  67
  68   void Cleanup() {
  69     for (auto *I : InstsToRemove) {
  70       LLVM_DEBUG(dbgs() << "ARM CGP: Removing " << *I << "\n");
  71       I->dropAllReferences();
  72       I->eraseFromParent();
  73     }
  74     InstsToRemove.clear();
  75     NewInsts.clear();
  76   }
  77
  78   void Mutate(Type *OrigTy,
  79               SmallPtrSetImpl<Value*> &Visited,
  80               SmallPtrSetImpl<Value*> &Leaves,
  81               SmallPtrSetImpl<Instruction*> &Roots);
  82 };
  83
  84 class ARMCodeGenPrepare : public FunctionPass {
  85   const ARMSubtarget *ST = nullptr;
  86   IRPromoter *Promoter = nullptr;
  87   std::set<Value*> AllVisited;
  88   Type *OrigTy = nullptr;
  89   unsigned TypeSize = 0;
  90
  91   bool isNarrowInstSupported(Instruction *I);
  92   bool isSupportedValue(Value *V);
  93   bool isLegalToPromote(Value *V);
  94   bool TryToPromote(Value *V);
  95
  96 public:
  97   static char ID;
  98
  99   ARMCodeGenPrepare() : FunctionPass(ID) {}
 100
 101   void getAnalysisUsage(AnalysisUsage &AU) const override {
 102     AU.addRequired<TargetPassConfig>();
 103   }
 104
 105   StringRef getPassName() const override { return "ARM IR optimizations"; }
 106
 107   bool doInitialization(Module &M) override;
 108   bool runOnFunction(Function &F) override;
 109   bool doFinalization(Module &M) override;
 110 };
 111
 112 }
 113
 114 /// Can the given value generate sign bits.
 115 static bool isSigned(Value *V) {
 116   if (!isa<Instruction>(V))
 117     return false;
 118
 119   unsigned Opc = cast<Instruction>(V)->getOpcode();
 120   return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
 121          Opc == Instruction::SRem;
 122 }
 123
 124 /// Some instructions can use 8- and 16-bit operands, and we don't need to
 125 /// promote anything larger. We disallow booleans to make life easier when
 126 /// dealing with icmps but allow any other integer that is <= 16 bits. Void
 127 /// types are accepted so we can handle switches.
 128 static bool isSupportedType(Value *V) {
 129   if (V->getType()->isVoidTy())
 130     return true;
 131
 132   const IntegerType *IntTy = dyn_cast<IntegerType>(V->getType());
 133   if (!IntTy)
 134     return false;
 135
 136   // Don't try to promote boolean values.
 137   if (IntTy->getBitWidth() == 1)
 138     return false;
 139
 140   if (auto *ZExt = dyn_cast<ZExtInst>(V))
 141     return isSupportedType(ZExt->getOperand(0));
 142
 143   return IntTy->getBitWidth() <= 16;
 144 }
 145
 146 /// Return true if V will require any promoted values to be truncated for the
 147 /// use to be valid.
 148 static bool isSink(Value *V) {
 149   auto UsesNarrowValue = [](Value *V) {
 150     return V->getType()->getScalarSizeInBits() <= 32;
 151   };
 152
 153   if (auto *Store = dyn_cast<StoreInst>(V))
 154     return UsesNarrowValue(Store->getValueOperand());
 155   if (auto *Return = dyn_cast<ReturnInst>(V))
 156     return UsesNarrowValue(Return->getReturnValue());
 157
 158   return isa<CallInst>(V);
 159 }
 160
 161 /// Return true if the given value is a leaf that will need to be zext'd.
 162 static bool isSource(Value *V) {
 163   if (isa<Argument>(V) && isSupportedType(V))
 164     return true;
 165   else if (isa<TruncInst>(V))
 166     return true;
 167   else if (auto *ZExt = dyn_cast<ZExtInst>(V))
 168     // ZExt can be a leaf if its the only user of a load.
 169     return isa<LoadInst>(ZExt->getOperand(0)) &&
 170                          ZExt->getOperand(0)->hasOneUse();
 171   else if (auto *Call = dyn_cast<CallInst>(V))
 172     return Call->hasRetAttr(Attribute::AttrKind::ZExt);
 173   else if (auto *Load = dyn_cast<LoadInst>(V)) {
 174     if (!isa<IntegerType>(Load->getType()))
 175       return false;
 176     // A load is a leaf, unless its already just being zext'd.
 177     if (Load->hasOneUse() && isa<ZExtInst>(*Load->use_begin()))
 178       return false;
 179
 180     return true;
 181   }
 182   return false;
 183 }
 184
 185 /// Return whether the instruction can be promoted within any modifications to
 186 /// it's operands or result.
 187 static bool isSafeOverflow(Instruction *I) {
 188   if (isa<OverflowingBinaryOperator>(I) && I->hasNoUnsignedWrap())
 189     return true;
 190
 191   unsigned Opc = I->getOpcode();
 192   if (Opc == Instruction::Add || Opc == Instruction::Sub) {
 193     // We don't care if the add or sub could wrap if the value is decreasing
 194     // and is only being used by an unsigned compare.
 195     if (!I->hasOneUse() ||
 196         !isa<ICmpInst>(*I->user_begin()) ||
 197         !isa<ConstantInt>(I->getOperand(1)))
 198       return false;
 199
 200     auto *CI = cast<ICmpInst>(*I->user_begin());
 201     if (CI->isSigned())
 202       return false;
 203
 204     bool NegImm = cast<ConstantInt>(I->getOperand(1))->isNegative();
 205     bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
 206                         ((Opc == Instruction::Add) && NegImm);
 207     if (!IsDecreasing)
 208       return false;
 209
 210     LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n");
 211     return true;
 212   }
 213
 214   // Otherwise, if an instruction is using a negative immediate we will need
 215   // to fix it up during the promotion.
 216   for (auto &Op : I->operands()) {
 217     if (auto *Const = dyn_cast<ConstantInt>(Op))
 218       if (Const->isNegative())
 219         return false;
 220   }
 221   return false;
 222 }
 223
 224 static bool shouldPromote(Value *V) {
 225   auto *I = dyn_cast<Instruction>(V);
 226   if (!I)
 227     return false;
 228
 229   if (!isa<IntegerType>(V->getType()))
 230     return false;
 231
 232   if (isa<StoreInst>(I) || isa<TerminatorInst>(I) || isa<TruncInst>(I) ||
 233       isa<ICmpInst>(I))
 234     return false;
 235
 236   if (auto *ZExt = dyn_cast<ZExtInst>(I))
 237     return !ZExt->getDestTy()->isIntegerTy(32);
 238
 239   return true;
 240 }
 241
 242 /// Return whether we can safely mutate V's type to ExtTy without having to be
 243 /// concerned with zero extending or truncation.
 244 static bool isPromotedResultSafe(Value *V) {
 245   if (!isa<Instruction>(V))
 246     return true;
 247
 248   if (isSigned(V))
 249     return false;
 250
 251   // If I is only being used by something that will require its value to be
 252   // truncated, then we don't care about the promoted result.
 253   auto *I = cast<Instruction>(V);
 254   if (I->hasOneUse() && isSink(*I->use_begin()))
 255     return true;
 256
 257   if (isa<OverflowingBinaryOperator>(I))
 258     return isSafeOverflow(I);
 259   return true;
 260 }
 261
 262 /// Return the intrinsic for the instruction that can perform the same
 263 /// operation but on a narrow type. This is using the parallel dsp intrinsics
 264 /// on scalar values.
 265 static Intrinsic::ID getNarrowIntrinsic(Instruction *I, unsigned TypeSize) {
 266   // Whether we use the signed or unsigned versions of these intrinsics
 267   // doesn't matter because we're not using the GE bits that they set in
 268   // the APSR.
 269   switch(I->getOpcode()) {
 270   default:
 271     break;
 272   case Instruction::Add:
 273     return TypeSize == 16 ? Intrinsic::arm_uadd16 :
 274       Intrinsic::arm_uadd8;
 275   case Instruction::Sub:
 276     return TypeSize == 16 ? Intrinsic::arm_usub16 :
 277       Intrinsic::arm_usub8;
 278   }
 279   llvm_unreachable("unhandled opcode for narrow intrinsic");
 280 }
 281
 282 void IRPromoter::Mutate(Type *OrigTy,
 283                         SmallPtrSetImpl<Value*> &Visited,
 284                         SmallPtrSetImpl<Value*> &Leaves,
 285                         SmallPtrSetImpl<Instruction*> &Roots) {
 286   IRBuilder<> Builder{Ctx};
 287   Type *ExtTy = Type::getInt32Ty(M->getContext());
 288   unsigned TypeSize = OrigTy->getPrimitiveSizeInBits();
 289   SmallPtrSet<Value*, 8> Promoted;
 290   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from " << TypeSize
 291         << " to 32-bits\n");
 292
 293   auto ReplaceAllUsersOfWith = [&](Value *From, Value *To) {
 294     SmallVector<Instruction*, 4> Users;
 295     Instruction *InstTo = dyn_cast<Instruction>(To);
 296     for (Use &U : From->uses()) {
 297       auto *User = cast<Instruction>(U.getUser());
 298       if (InstTo && User->isIdenticalTo(InstTo))
 299         continue;
 300       Users.push_back(User);
 301     }
 302
 303     for (auto &U : Users)
 304       U->replaceUsesOfWith(From, To);
 305   };
 306
 307   auto FixConst = [&](ConstantInt *Const, Instruction *I) {
 308     Constant *NewConst = nullptr;
 309     if (isSafeOverflow(I)) {
 310       NewConst = (Const->isNegative()) ?
 311         ConstantExpr::getSExt(Const, ExtTy) :
 312         ConstantExpr::getZExt(Const, ExtTy);
 313     } else {
 314       uint64_t NewVal = *Const->getValue().getRawData();
 315       if (Const->getType() == Type::getInt16Ty(Ctx))
 316         NewVal &= 0xFFFF;
 317       else
 318         NewVal &= 0xFF;
 319       NewConst = ConstantInt::get(ExtTy, NewVal);
 320     }
 321     I->replaceUsesOfWith(Const, NewConst);
 322   };
 323
 324   auto InsertDSPIntrinsic = [&](Instruction *I) {
 325     LLVM_DEBUG(dbgs() << "ARM CGP: Inserting DSP intrinsic for "
 326                << *I << "\n");
 327     Function *DSPInst =
 328       Intrinsic::getDeclaration(M, getNarrowIntrinsic(I, TypeSize));
 329     Builder.SetInsertPoint(I);
 330     Builder.SetCurrentDebugLocation(I->getDebugLoc());
 331     Value *Args[] = { I->getOperand(0), I->getOperand(1) };
 332     CallInst *Call = Builder.CreateCall(DSPInst, Args);
 333     ReplaceAllUsersOfWith(I, Call);
 334     InstsToRemove.push_back(I);
 335     NewInsts.insert(Call);
 336   };
 337
 338   auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
 339     LLVM_DEBUG(dbgs() << "ARM CGP: Inserting ZExt for " << *V << "\n");
 340     Builder.SetInsertPoint(InsertPt);
 341     if (auto *I = dyn_cast<Instruction>(V))
 342       Builder.SetCurrentDebugLocation(I->getDebugLoc());
 343     auto *ZExt = cast<Instruction>(Builder.CreateZExt(V, ExtTy));
 344     if (isa<Argument>(V))
 345       ZExt->moveBefore(InsertPt);
 346     else
 347       ZExt->moveAfter(InsertPt);
 348     ReplaceAllUsersOfWith(V, ZExt);
 349     NewInsts.insert(ZExt);
 350   };
 351
 352   // First, insert extending instructions between the leaves and their users.
 353   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting leaves:\n");
 354   for (auto V : Leaves) {
 355     LLVM_DEBUG(dbgs() << " - " << *V << "\n");
 356     if (auto *ZExt = dyn_cast<ZExtInst>(V))
 357       ZExt->mutateType(ExtTy);
 358     else if (auto *I = dyn_cast<Instruction>(V))
 359       InsertZExt(I, I);
 360     else if (auto *Arg = dyn_cast<Argument>(V)) {
 361       BasicBlock &BB = Arg->getParent()->front();
 362       InsertZExt(Arg, &*BB.getFirstInsertionPt());
 363     } else {
 364       llvm_unreachable("unhandled leaf that needs extending");
 365     }
 366     Promoted.insert(V);
 367   }
 368
 369   LLVM_DEBUG(dbgs() << "ARM CGP: Mutating the tree..\n");
 370   // Then mutate the types of the instructions within the tree. Here we handle
 371   // constant operands.
 372   for (auto *V : Visited) {
 373     if (Leaves.count(V))
 374       continue;
 375
 376     if (!isa<Instruction>(V))
 377       continue;
 378
 379     auto *I = cast<Instruction>(V);
 380     if (Roots.count(I))
 381       continue;
 382
 383     for (auto &U : I->operands()) {
 384       if ((U->getType() == ExtTy) || !isSupportedType(&*U))
 385         continue;
 386
 387       if (auto *Const = dyn_cast<ConstantInt>(&*U))
 388         FixConst(Const, I);
 389       else if (isa<UndefValue>(&*U))
 390         U->mutateType(ExtTy);
 391     }
 392
 393     if (shouldPromote(I)) {
 394       I->mutateType(ExtTy);
 395       Promoted.insert(I);
 396     }
 397   }
 398
 399   // Now we need to remove any zexts that have become unnecessary, as well
 400   // as insert any intrinsics.
 401   for (auto *V : Visited) {
 402     if (Leaves.count(V))
 403       continue;
 404     if (auto *ZExt = dyn_cast<ZExtInst>(V)) {
 405       if (ZExt->getDestTy() != ExtTy) {
 406         ZExt->mutateType(ExtTy);
 407         Promoted.insert(ZExt);
 408       }
 409       else if (ZExt->getSrcTy() == ExtTy) {
 410         ReplaceAllUsersOfWith(V, ZExt->getOperand(0));
 411         InstsToRemove.push_back(ZExt);
 412       }
 413       continue;
 414     }
 415
 416     if (!shouldPromote(V) || isPromotedResultSafe(V))
 417       continue;
 418
 419     // Replace unsafe instructions with appropriate intrinsic calls.
 420     InsertDSPIntrinsic(cast<Instruction>(V));
 421   }
 422
 423   LLVM_DEBUG(dbgs() << "ARM CGP: Fixing up the roots:\n");
 424   // Fix up any stores or returns that use the results of the promoted
 425   // chain.
 426   for (auto I : Roots) {
 427     LLVM_DEBUG(dbgs() << " - " << *I << "\n");
 428     Type *TruncTy = OrigTy;
 429     if (auto *Store = dyn_cast<StoreInst>(I)) {
 430       auto *PtrTy = cast<PointerType>(Store->getPointerOperandType());
 431       TruncTy = PtrTy->getElementType();
 432     } else if (isa<ReturnInst>(I)) {
 433       Function *F = I->getParent()->getParent();
 434       TruncTy = F->getFunctionType()->getReturnType();
 435     }
 436
 437     for (unsigned i = 0; i < I->getNumOperands(); ++i) {
 438       Value *V = I->getOperand(i);
 439       if (Promoted.count(V) || NewInsts.count(V)) {
 440         if (auto *Op = dyn_cast<Instruction>(V)) {
 441
 442           if (auto *Call = dyn_cast<CallInst>(I))
 443             TruncTy = Call->getFunctionType()->getParamType(i);
 444
 445           if (TruncTy == ExtTy)
 446             continue;
 447
 448           LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy
 449                      << " Trunc for " << *Op << "\n");
 450           Builder.SetInsertPoint(Op);
 451           auto *Trunc = cast<Instruction>(Builder.CreateTrunc(Op, TruncTy));
 452           Trunc->moveBefore(I);
 453           I->setOperand(i, Trunc);
 454           NewInsts.insert(Trunc);
 455         }
 456       }
 457     }
 458   }
 459   LLVM_DEBUG(dbgs() << "ARM CGP: Mutation complete.\n");
 460 }
 461
 462 bool ARMCodeGenPrepare::isNarrowInstSupported(Instruction *I) {
 463   if (!ST->hasDSP() || !EnableDSP || !isSupportedType(I))
 464     return false;
 465
 466   if (ST->isThumb() && !ST->hasThumb2())
 467     return false;
 468
 469   if (I->getOpcode() != Instruction::Add && I->getOpcode() != Instruction::Sub)
 470     return false;
 471
 472   // TODO
 473   // Would it be profitable? For Thumb code, these parallel DSP instructions
 474   // are only Thumb-2, so we wouldn't be able to dual issue on Cortex-M33. For
 475   // Cortex-A, specifically Cortex-A72, the latency is double and throughput is
 476   // halved. They also do not take immediates as operands.
 477   for (auto &Op : I->operands()) {
 478     if (isa<Constant>(Op)) {
 479       if (!EnableDSPWithImms)
 480         return false;
 481     }
 482   }
 483   return true;
 484 }
 485
 486 /// We accept most instructions, as well as Arguments and ConstantInsts. We
 487 /// Disallow casts other than zext and truncs and only allow calls if their
 488 /// return value is zeroext. We don't allow opcodes that can introduce sign
 489 /// bits.
 490 bool ARMCodeGenPrepare::isSupportedValue(Value *V) {
 491   LLVM_DEBUG(dbgs() << "ARM CGP: Is " << *V << " supported?\n");
 492
 493   // Non-instruction values that we can handle.
 494   if (isa<ConstantInt>(V) || isa<Argument>(V))
 495     return true;
 496
 497   // Memory instructions
 498   if (isa<StoreInst>(V) || isa<LoadInst>(V) || isa<GetElementPtrInst>(V))
 499     return true;
 500
 501   // Branches and targets.
 502   if (auto *ICmp = dyn_cast<ICmpInst>(V))
 503     return ICmp->isEquality() || !ICmp->isSigned();
 504
 505   if( isa<BranchInst>(V) || isa<SwitchInst>(V) || isa<BasicBlock>(V))
 506     return true;
 507
 508   if (isa<PHINode>(V) || isa<SelectInst>(V) || isa<ReturnInst>(V))
 509     return true;
 510
 511   // Special cases for calls as we need to check for zeroext
 512   // TODO We should accept calls even if they don't have zeroext, as they can
 513   // still be roots.
 514   if (auto *Call = dyn_cast<CallInst>(V))
 515     return Call->hasRetAttr(Attribute::AttrKind::ZExt);
 516   else if (auto *Cast = dyn_cast<CastInst>(V)) {
 517     if (isa<ZExtInst>(Cast))
 518       return Cast->getDestTy()->getScalarSizeInBits() <= 32;
 519     else if (auto *Trunc = dyn_cast<TruncInst>(V))
 520       return Trunc->getDestTy()->getScalarSizeInBits() <= TypeSize;
 521     else {
 522       LLVM_DEBUG(dbgs() << "ARM CGP: No, unsupported cast.\n");
 523       return false;
 524     }
 525   } else if (!isa<BinaryOperator>(V)) {
 526     LLVM_DEBUG(dbgs() << "ARM CGP: No, not a binary operator.\n");
 527     return false;
 528   }
 529
 530   bool res = !isSigned(V);
 531   if (!res)
 532     LLVM_DEBUG(dbgs() << "ARM CGP: No, it's a signed instruction.\n");
 533   return res;
 534 }
 535
 536 /// Check that the type of V would be promoted and that the original type is
 537 /// smaller than the targeted promoted type. Check that we're not trying to
 538 /// promote something larger than our base 'TypeSize' type.
 539 bool ARMCodeGenPrepare::isLegalToPromote(Value *V) {
 540   if (!isSupportedType(V))
 541     return false;
 542
 543   unsigned VSize = 0;
 544   if (auto *Ld = dyn_cast<LoadInst>(V)) {
 545     auto *PtrTy = cast<PointerType>(Ld->getPointerOperandType());
 546     VSize = PtrTy->getElementType()->getPrimitiveSizeInBits();
 547   } else if (auto *ZExt = dyn_cast<ZExtInst>(V)) {
 548     VSize = ZExt->getOperand(0)->getType()->getPrimitiveSizeInBits();
 549   } else {
 550     VSize = V->getType()->getPrimitiveSizeInBits();
 551   }
 552
 553   if (VSize > TypeSize)
 554     return false;
 555
 556   if (isPromotedResultSafe(V))
 557     return true;
 558
 559   if (auto *I = dyn_cast<Instruction>(V))
 560     return isNarrowInstSupported(I);
 561
 562   return false;
 563 }
 564
 565 bool ARMCodeGenPrepare::TryToPromote(Value *V) {
 566   OrigTy = V->getType();
 567   TypeSize = OrigTy->getPrimitiveSizeInBits();
 568
 569   if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
 570     return false;
 571
 572   LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << "\n");
 573
 574   SetVector<Value*> WorkList;
 575   SmallPtrSet<Value*, 8> Leaves;
 576   SmallPtrSet<Instruction*, 4> Roots;
 577   WorkList.insert(V);
 578   SmallPtrSet<Value*, 16> CurrentVisited;
 579   CurrentVisited.clear();
 580
 581   // Return true if the given value can, or has been, visited. Add V to the
 582   // worklist if needed.
 583   auto AddLegalInst = [&](Value *V) {
 584     if (CurrentVisited.count(V))
 585       return true;
 586
 587     if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
 588       LLVM_DEBUG(dbgs() << "ARM CGP: Can't handle: " << *V << "\n");
 589       return false;
 590     }
 591
 592     WorkList.insert(V);
 593     return true;
 594   };
 595
 596   // Iterate through, and add to, a tree of operands and users in the use-def.
 597   while (!WorkList.empty()) {
 598     Value *V = WorkList.back();
 599     WorkList.pop_back();
 600     if (CurrentVisited.count(V))
 601       continue;
 602
 603     if (!isa<Instruction>(V) && !isSource(V))
 604       continue;
 605
 606     // If we've already visited this value from somewhere, bail now because
 607     // the tree has already been explored.
 608     // TODO: This could limit the transform, ie if we try to promote something
 609     // from an i8 and fail first, before trying an i16.
 610     if (AllVisited.count(V)) {
 611       LLVM_DEBUG(dbgs() << "ARM CGP: Already visited this: " << *V << "\n");
 612       return false;
 613     }
 614
 615     CurrentVisited.insert(V);
 616     AllVisited.insert(V);
 617
 618     // Calls can be both sources and sinks.
 619     if (isSink(V))
 620       Roots.insert(cast<Instruction>(V));
 621     if (isSource(V))
 622       Leaves.insert(V);
 623     else if (auto *I = dyn_cast<Instruction>(V)) {
 624       // Visit operands of any instruction visited.
 625       for (auto &U : I->operands()) {
 626         if (!AddLegalInst(U))
 627           return false;
 628       }
 629     }
 630
 631     // Don't visit users of a node which isn't going to be mutated unless its a
 632     // source.
 633     if (isSource(V) || shouldPromote(V)) {
 634       for (Use &U : V->uses()) {
 635         if (!AddLegalInst(U.getUser()))
 636           return false;
 637       }
 638     }
 639   }
 640
 641   unsigned NumToPromote = 0;
 642   unsigned Cost = 0;
 643   for (auto *V : CurrentVisited) {
 644     // Truncs will cause a uxt and no zeroext arguments will often require
 645     // a uxt somewhere.
 646     if (isa<TruncInst>(V))
 647       ++Cost;
 648     else if (auto *Arg = dyn_cast<Argument>(V)) {
 649       if (!Arg->hasZExtAttr())
 650         ++Cost;
 651     }
 652
 653     // Mem ops can automatically be extended/truncated and non-instructions
 654     // don't need anything done.
 655     if (Leaves.count(V) || isa<StoreInst>(V) || !isa<Instruction>(V))
 656       continue;
 657
 658     // Will need to truncate calls args and returns.
 659     if (Roots.count(cast<Instruction>(V))) {
 660       ++Cost;
 661       continue;
 662     }
 663
 664     if (shouldPromote(V))
 665       ++NumToPromote;
 666   }
 667
 668   LLVM_DEBUG(dbgs() << "ARM CGP: Visited nodes:\n";
 669              for (auto *I : CurrentVisited)
 670                I->dump();
 671              );
 672   LLVM_DEBUG(dbgs() << "ARM CGP: Cost of promoting " << NumToPromote
 673              << " instructions = " << Cost << "\n");
 674   if (Cost > NumToPromote || (NumToPromote == 0))
 675     return false;
 676
 677   Promoter->Mutate(OrigTy, CurrentVisited, Leaves, Roots);
 678   return true;
 679 }
 680
 681 bool ARMCodeGenPrepare::doInitialization(Module &M) {
 682   Promoter = new IRPromoter(&M);
 683   return false;
 684 }
 685
 686 bool ARMCodeGenPrepare::runOnFunction(Function &F) {
 687   if (skipFunction(F) || DisableCGP)
 688     return false;
 689
 690   auto *TPC = &getAnalysis<TargetPassConfig>();
 691   if (!TPC)
 692     return false;
 693
 694   const TargetMachine &TM = TPC->getTM<TargetMachine>();
 695   ST = &TM.getSubtarget<ARMSubtarget>(F);
 696   bool MadeChange = false;
 697   LLVM_DEBUG(dbgs() << "ARM CGP: Running on " << F.getName() << "\n");
 698
 699   // Search up from icmps to try to promote their operands.
 700   for (BasicBlock &BB : F) {
 701     auto &Insts = BB.getInstList();
 702     for (auto &I : Insts) {
 703       if (AllVisited.count(&I))
 704         continue;
 705
 706       if (isa<ICmpInst>(I)) {
 707         auto &CI = cast<ICmpInst>(I);
 708
 709         // Skip signed or pointer compares
 710         if (CI.isSigned() || !isa<IntegerType>(CI.getOperand(0)->getType()))
 711           continue;
 712
 713         LLVM_DEBUG(dbgs() << "ARM CGP: Searching from: " << CI << "\n");
 714         for (auto &Op : CI.operands()) {
 715           if (auto *I = dyn_cast<Instruction>(Op)) {
 716             if (isa<ZExtInst>(I))
 717               MadeChange |= TryToPromote(I->getOperand(0));
 718             else
 719               MadeChange |= TryToPromote(I);
 720           }
 721         }
 722       }
 723     }
 724     Promoter->Cleanup();
 725     LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
 726                 dbgs();
 727                 report_fatal_error("Broken function after type promotion");
 728                });
 729   }
 730   if (MadeChange)
 731     LLVM_DEBUG(dbgs() << "After ARMCodeGenPrepare: " << F << "\n");
 732
 733   return MadeChange;
 734 }
 735
 736 bool ARMCodeGenPrepare::doFinalization(Module &M) {
 737   delete Promoter;
 738   return false;
 739 }
 740
 741 INITIALIZE_PASS_BEGIN(ARMCodeGenPrepare, DEBUG_TYPE,
 742                       "ARM IR optimizations", false, false)
 743 INITIALIZE_PASS_END(ARMCodeGenPrepare, DEBUG_TYPE, "ARM IR optimizations",
 744                     false, false)
 745
 746 char ARMCodeGenPrepare::ID = 0;
 747
 748 FunctionPass *llvm::createARMCodeGenPreparePass() {
 749   return new ARMCodeGenPrepare();
 750 }