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