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