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