llvm/lib/CodeGen/TypePromotion.cpp

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