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