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