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