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