lib/Target/ARM/ARMCodeGenPrepare.cpp

   1 //===----- ARMCodeGenPrepare.cpp ------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// This pass inserts intrinsics to handle small types that would otherwise be
  11 /// promoted during legalization. Here we can manually promote types or insert
  12 /// intrinsics which can handle narrow types that aren't supported by the
  13 /// register classes.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "ARM.h"
  18 #include "ARMSubtarget.h"
  19 #include "ARMTargetMachine.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/TargetPassConfig.h"
  23 #include "llvm/IR/Attributes.h"
  24 #include "llvm/IR/BasicBlock.h"
  25 #include "llvm/IR/IRBuilder.h"
  26 #include "llvm/IR/Constants.h"
  27 #include "llvm/IR/InstrTypes.h"
  28 #include "llvm/IR/Instruction.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/IntrinsicInst.h"
  31 #include "llvm/IR/Intrinsics.h"
  32 #include "llvm/IR/Type.h"
  33 #include "llvm/IR/Value.h"
  34 #include "llvm/IR/Verifier.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/Support/Casting.h"
  37 #include "llvm/Support/CommandLine.h"
  38
  39 #define DEBUG_TYPE "arm-codegenprepare"
  40
  41 using namespace llvm;
  42
  43 static cl::opt<bool>
  44 DisableCGP("arm-disable-cgp", cl::Hidden, cl::init(true),
  45            cl::desc("Disable ARM specific CodeGenPrepare pass"));
  46
  47 static cl::opt<bool>
  48 EnableDSP("arm-enable-scalar-dsp", cl::Hidden, cl::init(false),
  49           cl::desc("Use DSP instructions for scalar operations"));
  50
  51 static cl::opt<bool>
  52 EnableDSPWithImms("arm-enable-scalar-dsp-imms", cl::Hidden, cl::init(false),
  53                    cl::desc("Use DSP instructions for scalar operations\
  54                             with immediate operands"));
  55
  56 // The goal of this pass is to enable more efficient code generation for
  57 // operations on narrow types (i.e. types with < 32-bits) and this is a
  58 // motivating IR code example:
  59 //
  60 //   define hidden i32 @cmp(i8 zeroext) {
  61 //     %2 = add i8 %0, -49
  62 //     %3 = icmp ult i8 %2, 3
  63 //     ..
  64 //   }
  65 //
  66 // The issue here is that i8 is type-legalized to i32 because i8 is not a
  67 // legal type. Thus, arithmetic is done in integer-precision, but then the
  68 // byte value is masked out as follows:
  69 //
  70 //   t19: i32 = add t4, Constant:i32<-49>
  71 //     t24: i32 = and t19, Constant:i32<255>
  72 //
  73 // Consequently, we generate code like this:
  74 //
  75 //   subs  r0, #49
  76 //   uxtb  r1, r0
  77 //   cmp r1, #3
  78 //
  79 // This shows that masking out the byte value results in generation of
  80 // the UXTB instruction. This is not optimal as r0 already contains the byte
  81 // value we need, and so instead we can just generate:
  82 //
  83 //   sub.w r1, r0, #49
  84 //   cmp r1, #3
  85 //
  86 // We achieve this by type promoting the IR to i32 like so for this example:
  87 //
  88 //   define i32 @cmp(i8 zeroext %c) {
  89 //     %0 = zext i8 %c to i32
  90 //     %c.off = add i32 %0, -49
  91 //     %1 = icmp ult i32 %c.off, 3
  92 //     ..
  93 //   }
  94 //
  95 // For this to be valid and legal, we need to prove that the i32 add is
  96 // producing the same value as the i8 addition, and that e.g. no overflow
  97 // happens.
  98 //
  99 // A brief sketch of the algorithm and some terminology.
 100 // We pattern match interesting IR patterns:
 101 // - which have "sources": instructions producing narrow values (i8, i16), and
 102 // - they have "sinks": instructions consuming these narrow values.
 103 //
 104 // We collect all instruction connecting sources and sinks in a worklist, so
 105 // that we can mutate these instruction and perform type promotion when it is
 106 // legal to do so.
 107
 108 namespace {
 109 class IRPromoter {
 110   SmallPtrSet<Value*, 8> NewInsts;
 111   SmallPtrSet<Instruction*, 4> InstsToRemove;
 112   DenseMap<Value*, SmallVector<Type*, 4>> TruncTysMap;
 113   SmallPtrSet<Value*, 8> Promoted;
 114   Module *M = nullptr;
 115   LLVMContext &Ctx;
 116   // The type we promote to: always i32
 117   IntegerType *ExtTy = nullptr;
 118   // The type of the value that the search began from, either i8 or i16.
 119   // This defines the max range of the values that we allow in the promoted
 120   // tree.
 121   IntegerType *OrigTy = nullptr;
 122   SetVector<Value*> *Visited;
 123   SmallPtrSetImpl<Value*> *Sources;
 124   SmallPtrSetImpl<Instruction*> *Sinks;
 125   SmallPtrSetImpl<Instruction*> *SafeToPromote;
 126   SmallPtrSetImpl<Instruction*> *SafeWrap;
 127
 128   void ReplaceAllUsersOfWith(Value *From, Value *To);
 129   void PrepareWrappingAdds(void);
 130   void ExtendSources(void);
 131   void ConvertTruncs(void);
 132   void PromoteTree(void);
 133   void TruncateSinks(void);
 134   void Cleanup(void);
 135
 136 public:
 137   IRPromoter(Module *M) : M(M), Ctx(M->getContext()),
 138                           ExtTy(Type::getInt32Ty(Ctx)) { }
 139
 140
 141   void Mutate(Type *OrigTy,
 142               SetVector<Value*> &Visited,
 143               SmallPtrSetImpl<Value*> &Sources,
 144               SmallPtrSetImpl<Instruction*> &Sinks,
 145               SmallPtrSetImpl<Instruction*> &SafeToPromote,
 146               SmallPtrSetImpl<Instruction*> &SafeWrap);
 147 };
 148
 149 class ARMCodeGenPrepare : public FunctionPass {
 150   const ARMSubtarget *ST = nullptr;
 151   IRPromoter *Promoter = nullptr;
 152   std::set<Value*> AllVisited;
 153   SmallPtrSet<Instruction*, 8> SafeToPromote;
 154   SmallPtrSet<Instruction*, 4> SafeWrap;
 155
 156   bool isSafeWrap(Instruction *I);
 157   bool isSupportedValue(Value *V);
 158   bool isLegalToPromote(Value *V);
 159   bool TryToPromote(Value *V);
 160
 161 public:
 162   static char ID;
 163   static unsigned TypeSize;
 164   Type *OrigTy = nullptr;
 165
 166   ARMCodeGenPrepare() : FunctionPass(ID) {}
 167
 168   void getAnalysisUsage(AnalysisUsage &AU) const override {
 169     AU.addRequired<TargetPassConfig>();
 170   }
 171
 172   StringRef getPassName() const override { return "ARM IR optimizations"; }
 173
 174   bool doInitialization(Module &M) override;
 175   bool runOnFunction(Function &F) override;
 176   bool doFinalization(Module &M) override;
 177 };
 178
 179 }
 180
 181 static bool GenerateSignBits(Value *V) {
 182   if (!isa<Instruction>(V))
 183     return false;
 184
 185   unsigned Opc = cast<Instruction>(V)->getOpcode();
 186   return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
 187          Opc == Instruction::SRem || Opc == Instruction::SExt;
 188 }
 189
 190 static bool EqualTypeSize(Value *V) {
 191   return V->getType()->getScalarSizeInBits() == ARMCodeGenPrepare::TypeSize;
 192 }
 193
 194 static bool LessOrEqualTypeSize(Value *V) {
 195   return V->getType()->getScalarSizeInBits() <= ARMCodeGenPrepare::TypeSize;
 196 }
 197
 198 static bool GreaterThanTypeSize(Value *V) {
 199   return V->getType()->getScalarSizeInBits() > ARMCodeGenPrepare::TypeSize;
 200 }
 201
 202 static bool LessThanTypeSize(Value *V) {
 203   return V->getType()->getScalarSizeInBits() < ARMCodeGenPrepare::TypeSize;
 204 }
 205
 206 /// Some instructions can use 8- and 16-bit operands, and we don't need to
 207 /// promote anything larger. We disallow booleans to make life easier when
 208 /// dealing with icmps but allow any other integer that is <= 16 bits. Void
 209 /// types are accepted so we can handle switches.
 210 static bool isSupportedType(Value *V) {
 211   Type *Ty = V->getType();
 212
 213   // Allow voids and pointers, these won't be promoted.
 214   if (Ty->isVoidTy() || Ty->isPointerTy())
 215     return true;
 216
 217   if (auto *Ld = dyn_cast<LoadInst>(V))
 218     Ty = cast<PointerType>(Ld->getPointerOperandType())->getElementType();
 219
 220   if (!isa<IntegerType>(Ty) ||
 221       cast<IntegerType>(V->getType())->getBitWidth() == 1)
 222     return false;
 223
 224   return LessOrEqualTypeSize(V);
 225 }
 226
 227 /// Return true if the given value is a source in the use-def chain, producing
 228 /// a narrow 'TypeSize' value. These values will be zext to start the promotion
 229 /// of the tree to i32. We guarantee that these won't populate the upper bits
 230 /// of the register. ZExt on the loads will be free, and the same for call
 231 /// return values because we only accept ones that guarantee a zeroext ret val.
 232 /// Many arguments will have the zeroext attribute too, so those would be free
 233 /// too.
 234 static bool isSource(Value *V) {
 235   if (!isa<IntegerType>(V->getType()))
 236     return false;
 237
 238   // TODO Allow zext to be sources.
 239   if (isa<Argument>(V))
 240     return true;
 241   else if (isa<LoadInst>(V))
 242     return true;
 243   else if (isa<BitCastInst>(V))
 244     return true;
 245   else if (auto *Call = dyn_cast<CallInst>(V))
 246     return Call->hasRetAttr(Attribute::AttrKind::ZExt);
 247   else if (auto *Trunc = dyn_cast<TruncInst>(V))
 248     return EqualTypeSize(Trunc);
 249   return false;
 250 }
 251
 252 /// Return true if V will require any promoted values to be truncated for the
 253 /// the IR to remain valid. We can't mutate the value type of these
 254 /// instructions.
 255 static bool isSink(Value *V) {
 256   // TODO The truncate also isn't actually necessary because we would already
 257   // proved that the data value is kept within the range of the original data
 258   // type.
 259
 260   // Sinks are:
 261   // - points where the value in the register is being observed, such as an
 262   //   icmp, switch or store.
 263   // - points where value types have to match, such as calls and returns.
 264   // - zext are included to ease the transformation and are generally removed
 265   //   later on.
 266   if (auto *Store = dyn_cast<StoreInst>(V))
 267     return LessOrEqualTypeSize(Store->getValueOperand());
 268   if (auto *Return = dyn_cast<ReturnInst>(V))
 269     return LessOrEqualTypeSize(Return->getReturnValue());
 270   if (auto *ZExt = dyn_cast<ZExtInst>(V))
 271     return GreaterThanTypeSize(ZExt);
 272   if (auto *Switch = dyn_cast<SwitchInst>(V))
 273     return LessThanTypeSize(Switch->getCondition());
 274   if (auto *ICmp = dyn_cast<ICmpInst>(V))
 275     return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
 276
 277   return isa<CallInst>(V);
 278 }
 279
 280 /// Return whether this instruction can safely wrap.
 281 bool ARMCodeGenPrepare::isSafeWrap(Instruction *I) {
 282   // We can support a, potentially, wrapping instruction (I) if:
 283   // - It is only used by an unsigned icmp.
 284   // - The icmp uses a constant.
 285   // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
 286   //   around zero to become a larger number than before.
 287   // - The wrapping instruction (I) also uses a constant.
 288   //
 289   // We can then use the two constants to calculate whether the result would
 290   // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
 291   // just underflows the range, the icmp would give the same result whether the
 292   // result has been truncated or not. We calculate this by:
 293   // - Zero extending both constants, if needed, to 32-bits.
 294   // - Take the absolute value of I's constant, adding this to the icmp const.
 295   // - Check that this value is not out of range for small type. If it is, it
 296   //   means that it has underflowed enough to wrap around the icmp constant.
 297   //
 298   // For example:
 299   //
 300   // %sub = sub i8 %a, 2
 301   // %cmp = icmp ule i8 %sub, 254
 302   //
 303   // If %a = 0, %sub = -2 == FE == 254
 304   // But if this is evalulated as a i32
 305   // %sub = -2 == FF FF FF FE == 4294967294
 306   // So the unsigned compares (i8 and i32) would not yield the same result.
 307   //
 308   // Another way to look at it is:
 309   // %a - 2 <= 254
 310   // %a + 2 <= 254 + 2
 311   // %a <= 256
 312   // And we can't represent 256 in the i8 format, so we don't support it.
 313   //
 314   // Whereas:
 315   //
 316   // %sub i8 %a, 1
 317   // %cmp = icmp ule i8 %sub, 254
 318   //
 319   // If %a = 0, %sub = -1 == FF == 255
 320   // As i32:
 321   // %sub = -1 == FF FF FF FF == 4294967295
 322   //
 323   // In this case, the unsigned compare results would be the same and this
 324   // would also be true for ult, uge and ugt:
 325   // - (255 < 254) == (0xFFFFFFFF < 254) == false
 326   // - (255 <= 254) == (0xFFFFFFFF <= 254) == false
 327   // - (255 > 254) == (0xFFFFFFFF > 254) == true
 328   // - (255 >= 254) == (0xFFFFFFFF >= 254) == true
 329   //
 330   // To demonstrate why we can't handle increasing values:
 331   //
 332   // %add = add i8 %a, 2
 333   // %cmp = icmp ult i8 %add, 127
 334   //
 335   // If %a = 254, %add = 256 == (i8 1)
 336   // As i32:
 337   // %add = 256
 338   //
 339   // (1 < 127) != (256 < 127)
 340
 341   unsigned Opc = I->getOpcode();
 342   if (Opc != Instruction::Add && Opc != Instruction::Sub)
 343     return false;
 344
 345   if (!I->hasOneUse() ||
 346       !isa<ICmpInst>(*I->user_begin()) ||
 347       !isa<ConstantInt>(I->getOperand(1)))
 348     return false;
 349
 350   ConstantInt *OverflowConst = cast<ConstantInt>(I->getOperand(1));
 351   bool NegImm = OverflowConst->isNegative();
 352   bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
 353                        ((Opc == Instruction::Add) && NegImm);
 354   if (!IsDecreasing)
 355     return false;
 356
 357   // Don't support an icmp that deals with sign bits.
 358   auto *CI = cast<ICmpInst>(*I->user_begin());
 359   if (CI->isSigned() || CI->isEquality())
 360     return false;
 361
 362   ConstantInt *ICmpConst = nullptr;
 363   if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
 364     ICmpConst = Const;
 365   else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
 366     ICmpConst = Const;
 367   else
 368     return false;
 369
 370   // Now check that the result can't wrap on itself.
 371   APInt Total = ICmpConst->getValue().getBitWidth() < 32 ?
 372     ICmpConst->getValue().zext(32) : ICmpConst->getValue();
 373
 374   Total += OverflowConst->getValue().getBitWidth() < 32 ?
 375     OverflowConst->getValue().abs().zext(32) : OverflowConst->getValue().abs();
 376
 377   APInt Max = APInt::getAllOnesValue(ARMCodeGenPrepare::TypeSize);
 378
 379   if (Total.getBitWidth() > Max.getBitWidth()) {
 380     if (Total.ugt(Max.zext(Total.getBitWidth())))
 381       return false;
 382   } else if (Max.getBitWidth() > Total.getBitWidth()) {
 383     if (Total.zext(Max.getBitWidth()).ugt(Max))
 384       return false;
 385   } else if (Total.ugt(Max))
 386     return false;
 387
 388   LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n");
 389   SafeWrap.insert(I);
 390   return true;
 391 }
 392
 393 static bool shouldPromote(Value *V) {
 394   if (!isa<IntegerType>(V->getType()) || isSink(V))
 395     return false;
 396
 397   if (isSource(V))
 398     return true;
 399
 400   auto *I = dyn_cast<Instruction>(V);
 401   if (!I)
 402     return false;
 403
 404   if (isa<ICmpInst>(I))
 405     return false;
 406
 407   return true;
 408 }
 409
 410 /// Return whether we can safely mutate V's type to ExtTy without having to be
 411 /// concerned with zero extending or truncation.
 412 static bool isPromotedResultSafe(Value *V) {
 413   if (GenerateSignBits(V))
 414     return false;
 415
 416   if (!isa<Instruction>(V))
 417     return true;
 418
 419   if (!isa<OverflowingBinaryOperator>(V))
 420     return true;
 421
 422   return cast<Instruction>(V)->hasNoUnsignedWrap();
 423 }
 424
 425 /// Return the intrinsic for the instruction that can perform the same
 426 /// operation but on a narrow type. This is using the parallel dsp intrinsics
 427 /// on scalar values.
 428 static Intrinsic::ID getNarrowIntrinsic(Instruction *I) {
 429   // Whether we use the signed or unsigned versions of these intrinsics
 430   // doesn't matter because we're not using the GE bits that they set in
 431   // the APSR.
 432   switch(I->getOpcode()) {
 433   default:
 434     break;
 435   case Instruction::Add:
 436     return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_uadd16 :
 437       Intrinsic::arm_uadd8;
 438   case Instruction::Sub:
 439     return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_usub16 :
 440       Intrinsic::arm_usub8;
 441   }
 442   llvm_unreachable("unhandled opcode for narrow intrinsic");
 443 }
 444
 445 void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
 446   SmallVector<Instruction*, 4> Users;
 447   Instruction *InstTo = dyn_cast<Instruction>(To);
 448   bool ReplacedAll = true;
 449
 450   LLVM_DEBUG(dbgs() << "ARM CGP: Replacing " << *From << " with " << *To
 451              << "\n");
 452
 453   for (Use &U : From->uses()) {
 454     auto *User = cast<Instruction>(U.getUser());
 455     if (InstTo && User->isIdenticalTo(InstTo)) {
 456       ReplacedAll = false;
 457       continue;
 458     }
 459     Users.push_back(User);
 460   }
 461
 462   for (auto *U : Users)
 463     U->replaceUsesOfWith(From, To);
 464
 465   if (ReplacedAll)
 466     if (auto *I = dyn_cast<Instruction>(From))
 467       InstsToRemove.insert(I);
 468 }
 469
 470 void IRPromoter::PrepareWrappingAdds() {
 471   LLVM_DEBUG(dbgs() << "ARM CGP: Prepare underflowing adds.\n");
 472   IRBuilder<> Builder{Ctx};
 473
 474   // For adds that safely wrap and use a negative immediate as operand 1, we
 475   // create an equivalent instruction using a positive immediate.
 476   // That positive immediate can then be zext along with all the other
 477   // immediates later.
 478   for (auto *I : *SafeWrap) {
 479     if (I->getOpcode() != Instruction::Add)
 480       continue;
 481
 482     LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n");
 483     assert((isa<ConstantInt>(I->getOperand(1)) &&
 484             cast<ConstantInt>(I->getOperand(1))->isNegative()) &&
 485            "Wrapping should have a negative immediate as the second operand");
 486
 487     auto Const = cast<ConstantInt>(I->getOperand(1));
 488     auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
 489     Builder.SetInsertPoint(I);
 490     Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst);
 491     if (auto *NewInst = dyn_cast<Instruction>(NewVal)) {
 492       NewInst->copyIRFlags(I);
 493       NewInsts.insert(NewInst);
 494     }
 495     InstsToRemove.insert(I);
 496     I->replaceAllUsesWith(NewVal);
 497     LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n");
 498   }
 499   for (auto *I : NewInsts)
 500     Visited->insert(I);
 501 }
 502
 503 void IRPromoter::ExtendSources() {
 504   IRBuilder<> Builder{Ctx};
 505
 506   auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
 507     assert(V->getType() != ExtTy && "zext already extends to i32");
 508     LLVM_DEBUG(dbgs() << "ARM CGP: Inserting ZExt for " << *V << "\n");
 509     Builder.SetInsertPoint(InsertPt);
 510     if (auto *I = dyn_cast<Instruction>(V))
 511       Builder.SetCurrentDebugLocation(I->getDebugLoc());
 512
 513     Value *ZExt = Builder.CreateZExt(V, ExtTy);
 514     if (auto *I = dyn_cast<Instruction>(ZExt)) {
 515       if (isa<Argument>(V))
 516         I->moveBefore(InsertPt);
 517       else
 518         I->moveAfter(InsertPt);
 519       NewInsts.insert(I);
 520     }
 521
 522     ReplaceAllUsersOfWith(V, ZExt);
 523   };
 524
 525   // Now, insert extending instructions between the sources and their users.
 526   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting sources:\n");
 527   for (auto V : *Sources) {
 528     LLVM_DEBUG(dbgs() << " - " << *V << "\n");
 529     if (auto *I = dyn_cast<Instruction>(V))
 530       InsertZExt(I, I);
 531     else if (auto *Arg = dyn_cast<Argument>(V)) {
 532       BasicBlock &BB = Arg->getParent()->front();
 533       InsertZExt(Arg, &*BB.getFirstInsertionPt());
 534     } else {
 535       llvm_unreachable("unhandled source that needs extending");
 536     }
 537     Promoted.insert(V);
 538   }
 539 }
 540
 541 void IRPromoter::PromoteTree() {
 542   LLVM_DEBUG(dbgs() << "ARM CGP: Mutating the tree..\n");
 543
 544   IRBuilder<> Builder{Ctx};
 545
 546   // Mutate the types of the instructions within the tree. Here we handle
 547   // constant operands.
 548   for (auto *V : *Visited) {
 549     if (Sources->count(V))
 550       continue;
 551
 552     auto *I = cast<Instruction>(V);
 553     if (Sinks->count(I))
 554       continue;
 555
 556     for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
 557       Value *Op = I->getOperand(i);
 558       if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
 559         continue;
 560
 561       if (auto *Const = dyn_cast<ConstantInt>(Op)) {
 562         Constant *NewConst = ConstantExpr::getZExt(Const, ExtTy);
 563         I->setOperand(i, NewConst);
 564       } else if (isa<UndefValue>(Op))
 565         I->setOperand(i, UndefValue::get(ExtTy));
 566     }
 567
 568     if (shouldPromote(I)) {
 569       I->mutateType(ExtTy);
 570       Promoted.insert(I);
 571     }
 572   }
 573
 574   // Finally, any instructions that should be promoted but haven't yet been,
 575   // need to be handled using intrinsics.
 576   for (auto *V : *Visited) {
 577     auto *I = dyn_cast<Instruction>(V);
 578     if (!I)
 579       continue;
 580
 581     if (Sources->count(I) || Sinks->count(I))
 582       continue;
 583
 584     if (!shouldPromote(I) || SafeToPromote->count(I) || NewInsts.count(I))
 585       continue;
 586
 587     assert(EnableDSP && "DSP intrinisc insertion not enabled!");
 588
 589     // Replace unsafe instructions with appropriate intrinsic calls.
 590     LLVM_DEBUG(dbgs() << "ARM CGP: Inserting DSP intrinsic for "
 591                << *I << "\n");
 592     Function *DSPInst =
 593       Intrinsic::getDeclaration(M, getNarrowIntrinsic(I));
 594     Builder.SetInsertPoint(I);
 595     Builder.SetCurrentDebugLocation(I->getDebugLoc());
 596     Value *Args[] = { I->getOperand(0), I->getOperand(1) };
 597     CallInst *Call = Builder.CreateCall(DSPInst, Args);
 598     NewInsts.insert(Call);
 599     ReplaceAllUsersOfWith(I, Call);
 600   }
 601 }
 602
 603 void IRPromoter::TruncateSinks() {
 604   LLVM_DEBUG(dbgs() << "ARM CGP: Fixing up the sinks:\n");
 605
 606   IRBuilder<> Builder{Ctx};
 607
 608   auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction* {
 609     if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
 610       return nullptr;
 611
 612     if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources->count(V))
 613       return nullptr;
 614
 615     LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy << " Trunc for "
 616                << *V << "\n");
 617     Builder.SetInsertPoint(cast<Instruction>(V));
 618     auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
 619     if (Trunc)
 620       NewInsts.insert(Trunc);
 621     return Trunc;
 622   };
 623
 624   // Fix up any stores or returns that use the results of the promoted
 625   // chain.
 626   for (auto I : *Sinks) {
 627     LLVM_DEBUG(dbgs() << "ARM CGP: For Sink: " << *I << "\n");
 628
 629     // Handle calls separately as we need to iterate over arg operands.
 630     if (auto *Call = dyn_cast<CallInst>(I)) {
 631       for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
 632         Value *Arg = Call->getArgOperand(i);
 633         Type *Ty = TruncTysMap[Call][i];
 634         if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
 635           Trunc->moveBefore(Call);
 636           Call->setArgOperand(i, Trunc);
 637         }
 638       }
 639       continue;
 640     }
 641
 642     // Special case switches because we need to truncate the condition.
 643     if (auto *Switch = dyn_cast<SwitchInst>(I)) {
 644       Type *Ty = TruncTysMap[Switch][0];
 645       if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
 646         Trunc->moveBefore(Switch);
 647         Switch->setCondition(Trunc);
 648       }
 649       continue;
 650     }
 651
 652     // Now handle the others.
 653     for (unsigned i = 0; i < I->getNumOperands(); ++i) {
 654       Type *Ty = TruncTysMap[I][i];
 655       if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
 656         Trunc->moveBefore(I);
 657         I->setOperand(i, Trunc);
 658       }
 659     }
 660   }
 661 }
 662
 663 void IRPromoter::Cleanup() {
 664   LLVM_DEBUG(dbgs() << "ARM CGP: Cleanup..\n");
 665   // Some zexts will now have become redundant, along with their trunc
 666   // operands, so remove them
 667   for (auto V : *Visited) {
 668     if (!isa<ZExtInst>(V))
 669       continue;
 670
 671     auto ZExt = cast<ZExtInst>(V);
 672     if (ZExt->getDestTy() != ExtTy)
 673       continue;
 674
 675     Value *Src = ZExt->getOperand(0);
 676     if (ZExt->getSrcTy() == ZExt->getDestTy()) {
 677       LLVM_DEBUG(dbgs() << "ARM CGP: Removing unnecessary cast: " << *ZExt
 678                  << "\n");
 679       ReplaceAllUsersOfWith(ZExt, Src);
 680       continue;
 681     }
 682
 683     // Unless they produce a value that is narrower than ExtTy, we can
 684     // replace the result of the zext with the input of a newly inserted
 685     // trunc.
 686     if (NewInsts.count(Src) && isa<TruncInst>(Src) &&
 687         Src->getType() == OrigTy) {
 688       auto *Trunc = cast<TruncInst>(Src);
 689       assert(Trunc->getOperand(0)->getType() == ExtTy &&
 690              "expected inserted trunc to be operating on i32");
 691       ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
 692     }
 693   }
 694
 695   for (auto *I : InstsToRemove) {
 696     LLVM_DEBUG(dbgs() << "ARM CGP: Removing " << *I << "\n");
 697     I->dropAllReferences();
 698     I->eraseFromParent();
 699   }
 700
 701   InstsToRemove.clear();
 702   NewInsts.clear();
 703   TruncTysMap.clear();
 704   Promoted.clear();
 705   SafeToPromote->clear();
 706   SafeWrap->clear();
 707 }
 708
 709 void IRPromoter::ConvertTruncs() {
 710   LLVM_DEBUG(dbgs() << "ARM CGP: Converting truncs..\n");
 711   IRBuilder<> Builder{Ctx};
 712
 713   for (auto *V : *Visited) {
 714     if (!isa<TruncInst>(V) || Sources->count(V))
 715       continue;
 716
 717     auto *Trunc = cast<TruncInst>(V);
 718     Builder.SetInsertPoint(Trunc);
 719     IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
 720     IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
 721
 722     unsigned NumBits = DestTy->getScalarSizeInBits();
 723     ConstantInt *Mask =
 724       ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());
 725     Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
 726
 727     if (auto *I = dyn_cast<Instruction>(Masked))
 728       NewInsts.insert(I);
 729
 730     ReplaceAllUsersOfWith(Trunc, Masked);
 731   }
 732 }
 733
 734 void IRPromoter::Mutate(Type *OrigTy,
 735                         SetVector<Value*> &Visited,
 736                         SmallPtrSetImpl<Value*> &Sources,
 737                         SmallPtrSetImpl<Instruction*> &Sinks,
 738                         SmallPtrSetImpl<Instruction*> &SafeToPromote,
 739                         SmallPtrSetImpl<Instruction*> &SafeWrap) {
 740   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from "
 741              << ARMCodeGenPrepare::TypeSize << " to 32-bits\n");
 742
 743   assert(isa<IntegerType>(OrigTy) && "expected integer type");
 744   this->OrigTy = cast<IntegerType>(OrigTy);
 745   assert(OrigTy->getPrimitiveSizeInBits() < ExtTy->getPrimitiveSizeInBits() &&
 746          "original type not smaller than extended type");
 747
 748   this->Visited = &Visited;
 749   this->Sources = &Sources;
 750   this->Sinks = &Sinks;
 751   this->SafeToPromote = &SafeToPromote;
 752   this->SafeWrap = &SafeWrap;
 753
 754   // Cache original types of the values that will likely need truncating
 755   for (auto *I : Sinks) {
 756     if (auto *Call = dyn_cast<CallInst>(I)) {
 757       for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
 758         Value *Arg = Call->getArgOperand(i);
 759         TruncTysMap[Call].push_back(Arg->getType());
 760       }
 761     } else if (auto *Switch = dyn_cast<SwitchInst>(I))
 762       TruncTysMap[I].push_back(Switch->getCondition()->getType());
 763     else {
 764       for (unsigned i = 0; i < I->getNumOperands(); ++i)
 765         TruncTysMap[I].push_back(I->getOperand(i)->getType());
 766     }
 767   }
 768   for (auto *V : Visited) {
 769     if (!isa<TruncInst>(V) || Sources.count(V))
 770       continue;
 771     auto *Trunc = cast<TruncInst>(V);
 772     TruncTysMap[Trunc].push_back(Trunc->getDestTy());
 773   }
 774
 775   // Convert adds using negative immediates to equivalent instructions that use
 776   // positive constants.
 777   PrepareWrappingAdds();
 778
 779   // Insert zext instructions between sources and their users.
 780   ExtendSources();
 781
 782   // Promote visited instructions, mutating their types in place. Also insert
 783   // DSP intrinsics, if enabled, for adds and subs which would be unsafe to
 784   // promote.
 785   PromoteTree();
 786
 787   // Convert any truncs, that aren't sources, into AND masks.
 788   ConvertTruncs();
 789
 790   // Insert trunc instructions for use by calls, stores etc...
 791   TruncateSinks();
 792
 793   // Finally, remove unecessary zexts and truncs, delete old instructions and
 794   // clear the data structures.
 795   Cleanup();
 796
 797   LLVM_DEBUG(dbgs() << "ARM CGP: Mutation complete\n");
 798 }
 799
 800 /// We accept most instructions, as well as Arguments and ConstantInsts. We
 801 /// Disallow casts other than zext and truncs and only allow calls if their
 802 /// return value is zeroext. We don't allow opcodes that can introduce sign
 803 /// bits.
 804 bool ARMCodeGenPrepare::isSupportedValue(Value *V) {
 805   if (auto *I = dyn_cast<Instruction>(V)) {
 806     switch (I->getOpcode()) {
 807     default:
 808       return isa<BinaryOperator>(I) && isSupportedType(I) &&
 809              !GenerateSignBits(I);
 810     case Instruction::GetElementPtr:
 811     case Instruction::Store:
 812     case Instruction::Br:
 813     case Instruction::Switch:
 814       return true;
 815     case Instruction::PHI:
 816     case Instruction::Select:
 817     case Instruction::Ret:
 818     case Instruction::Load:
 819     case Instruction::Trunc:
 820     case Instruction::BitCast:
 821       return isSupportedType(I);
 822     case Instruction::ZExt:
 823       return isSupportedType(I->getOperand(0));
 824     case Instruction::ICmp:
 825       // Now that we allow small types than TypeSize, only allow icmp of
 826       // TypeSize because they will require a trunc to be legalised.
 827       // TODO: Allow icmp of smaller types, and calculate at the end
 828       // whether the transform would be beneficial.
 829       if (isa<PointerType>(I->getOperand(0)->getType()))
 830         return true;
 831       return EqualTypeSize(I->getOperand(0));
 832     case Instruction::Call: {
 833       // Special cases for calls as we need to check for zeroext
 834       // TODO We should accept calls even if they don't have zeroext, as they
 835       // can still be sinks.
 836       auto *Call = cast<CallInst>(I);
 837       return isSupportedType(Call) &&
 838              Call->hasRetAttr(Attribute::AttrKind::ZExt);
 839     }
 840     }
 841   } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
 842     return isSupportedType(V);
 843   } else if (isa<Argument>(V))
 844     return isSupportedType(V);
 845
 846   return isa<BasicBlock>(V);
 847 }
 848
 849 /// Check that the type of V would be promoted and that the original type is
 850 /// smaller than the targeted promoted type. Check that we're not trying to
 851 /// promote something larger than our base 'TypeSize' type.
 852 bool ARMCodeGenPrepare::isLegalToPromote(Value *V) {
 853
 854   auto *I = dyn_cast<Instruction>(V);
 855   if (!I)
 856     return true;
 857
 858   if (SafeToPromote.count(I))
 859    return true;
 860
 861   if (isPromotedResultSafe(V) || isSafeWrap(I)) {
 862     SafeToPromote.insert(I);
 863     return true;
 864   }
 865
 866   if (I->getOpcode() != Instruction::Add && I->getOpcode() != Instruction::Sub)
 867     return false;
 868
 869   // If promotion is not safe, can we use a DSP instruction to natively
 870   // handle the narrow type?
 871   if (!ST->hasDSP() || !EnableDSP || !isSupportedType(I))
 872     return false;
 873
 874   if (ST->isThumb() && !ST->hasThumb2())
 875     return false;
 876
 877   // TODO
 878   // Would it be profitable? For Thumb code, these parallel DSP instructions
 879   // are only Thumb-2, so we wouldn't be able to dual issue on Cortex-M33. For
 880   // Cortex-A, specifically Cortex-A72, the latency is double and throughput is
 881   // halved. They also do not take immediates as operands.
 882   for (auto &Op : I->operands()) {
 883     if (isa<Constant>(Op)) {
 884       if (!EnableDSPWithImms)
 885         return false;
 886     }
 887   }
 888   LLVM_DEBUG(dbgs() << "ARM CGP: Will use an intrinsic for: " << *I << "\n");
 889   return true;
 890 }
 891
 892 bool ARMCodeGenPrepare::TryToPromote(Value *V) {
 893   OrigTy = V->getType();
 894   TypeSize = OrigTy->getPrimitiveSizeInBits();
 895   if (TypeSize > 16 || TypeSize < 8)
 896     return false;
 897
 898   SafeToPromote.clear();
 899   SafeWrap.clear();
 900
 901   if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
 902     return false;
 903
 904   LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << ", TypeSize = "
 905              << TypeSize << "\n");
 906
 907   SetVector<Value*> WorkList;
 908   SmallPtrSet<Value*, 8> Sources;
 909   SmallPtrSet<Instruction*, 4> Sinks;
 910   SetVector<Value*> CurrentVisited;
 911   WorkList.insert(V);
 912
 913   // Return true if V was added to the worklist as a supported instruction,
 914   // if it was already visited, or if we don't need to explore it (e.g.
 915   // pointer values and GEPs), and false otherwise.
 916   auto AddLegalInst = [&](Value *V) {
 917     if (CurrentVisited.count(V))
 918       return true;
 919
 920     // Ignore GEPs because they don't need promoting and the constant indices
 921     // will prevent the transformation.
 922     if (isa<GetElementPtrInst>(V))
 923       return true;
 924
 925     if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
 926       LLVM_DEBUG(dbgs() << "ARM CGP: Can't handle: " << *V << "\n");
 927       return false;
 928     }
 929
 930     WorkList.insert(V);
 931     return true;
 932   };
 933
 934   // Iterate through, and add to, a tree of operands and users in the use-def.
 935   while (!WorkList.empty()) {
 936     Value *V = WorkList.back();
 937     WorkList.pop_back();
 938     if (CurrentVisited.count(V))
 939       continue;
 940
 941     // Ignore non-instructions, other than arguments.
 942     if (!isa<Instruction>(V) && !isSource(V))
 943       continue;
 944
 945     // If we've already visited this value from somewhere, bail now because
 946     // the tree has already been explored.
 947     // TODO: This could limit the transform, ie if we try to promote something
 948     // from an i8 and fail first, before trying an i16.
 949     if (AllVisited.count(V))
 950       return false;
 951
 952     CurrentVisited.insert(V);
 953     AllVisited.insert(V);
 954
 955     // Calls can be both sources and sinks.
 956     if (isSink(V))
 957       Sinks.insert(cast<Instruction>(V));
 958
 959     if (isSource(V))
 960       Sources.insert(V);
 961
 962     if (!isSink(V) && !isSource(V)) {
 963       if (auto *I = dyn_cast<Instruction>(V)) {
 964         // Visit operands of any instruction visited.
 965         for (auto &U : I->operands()) {
 966           if (!AddLegalInst(U))
 967             return false;
 968         }
 969       }
 970     }
 971
 972     // Don't visit users of a node which isn't going to be mutated unless its a
 973     // source.
 974     if (isSource(V) || shouldPromote(V)) {
 975       for (Use &U : V->uses()) {
 976         if (!AddLegalInst(U.getUser()))
 977           return false;
 978       }
 979     }
 980   }
 981
 982   LLVM_DEBUG(dbgs() << "ARM CGP: Visited nodes:\n";
 983              for (auto *I : CurrentVisited)
 984                I->dump();
 985              );
 986   unsigned ToPromote = 0;
 987   for (auto *V : CurrentVisited) {
 988     if (Sources.count(V))
 989       continue;
 990     if (Sinks.count(cast<Instruction>(V)))
 991       continue;
 992     ++ToPromote;
 993   }
 994
 995   if (ToPromote < 2)
 996     return false;
 997
 998   Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote,
 999                    SafeWrap);
1000   return true;
1001 }
1002
1003 bool ARMCodeGenPrepare::doInitialization(Module &M) {
1004   Promoter = new IRPromoter(&M);
1005   return false;
1006 }
1007
1008 bool ARMCodeGenPrepare::runOnFunction(Function &F) {
1009   if (skipFunction(F) || DisableCGP)
1010     return false;
1011
1012   auto *TPC = &getAnalysis<TargetPassConfig>();
1013   if (!TPC)
1014     return false;
1015
1016   const TargetMachine &TM = TPC->getTM<TargetMachine>();
1017   ST = &TM.getSubtarget<ARMSubtarget>(F);
1018   bool MadeChange = false;
1019   LLVM_DEBUG(dbgs() << "ARM CGP: Running on " << F.getName() << "\n");
1020
1021   // Search up from icmps to try to promote their operands.
1022   for (BasicBlock &BB : F) {
1023     auto &Insts = BB.getInstList();
1024     for (auto &I : Insts) {
1025       if (AllVisited.count(&I))
1026         continue;
1027
1028       if (isa<ICmpInst>(I)) {
1029         auto &CI = cast<ICmpInst>(I);
1030
1031         // Skip signed or pointer compares
1032         if (CI.isSigned() || !isa<IntegerType>(CI.getOperand(0)->getType()))
1033           continue;
1034
1035         LLVM_DEBUG(dbgs() << "ARM CGP: Searching from: " << CI << "\n");
1036
1037         for (auto &Op : CI.operands()) {
1038           if (auto *I = dyn_cast<Instruction>(Op))
1039             MadeChange |= TryToPromote(I);
1040         }
1041       }
1042     }
1043     LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
1044                 dbgs() << F;
1045                 report_fatal_error("Broken function after type promotion");
1046                });
1047   }
1048   if (MadeChange)
1049     LLVM_DEBUG(dbgs() << "After ARMCodeGenPrepare: " << F << "\n");
1050
1051   return MadeChange;
1052 }
1053
1054 bool ARMCodeGenPrepare::doFinalization(Module &M) {
1055   delete Promoter;
1056   return false;
1057 }
1058
1059 INITIALIZE_PASS_BEGIN(ARMCodeGenPrepare, DEBUG_TYPE,
1060                       "ARM IR optimizations", false, false)
1061 INITIALIZE_PASS_END(ARMCodeGenPrepare, DEBUG_TYPE, "ARM IR optimizations",
1062                     false, false)
1063
1064 char ARMCodeGenPrepare::ID = 0;
1065 unsigned ARMCodeGenPrepare::TypeSize = 0;
1066
1067 FunctionPass *llvm::createARMCodeGenPreparePass() {
1068   return new ARMCodeGenPrepare();
1069 }