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