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