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