1056 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This is an opcode based type promotion pass for small types that would11/// otherwise be promoted during legalisation. This works around the limitations12/// of selection dag for cyclic regions. The search begins from icmp13/// instructions operands where a tree, consisting of non-wrapping or safe14/// wrapping instructions, is built, checked and promoted if possible.15///16//===----------------------------------------------------------------------===//17 18#include "llvm/CodeGen/TypePromotion.h"19#include "llvm/ADT/SetVector.h"20#include "llvm/ADT/StringRef.h"21#include "llvm/Analysis/LoopInfo.h"22#include "llvm/Analysis/TargetTransformInfo.h"23#include "llvm/CodeGen/Passes.h"24#include "llvm/CodeGen/TargetLowering.h"25#include "llvm/CodeGen/TargetPassConfig.h"26#include "llvm/CodeGen/TargetSubtargetInfo.h"27#include "llvm/IR/Attributes.h"28#include "llvm/IR/BasicBlock.h"29#include "llvm/IR/Constants.h"30#include "llvm/IR/IRBuilder.h"31#include "llvm/IR/InstrTypes.h"32#include "llvm/IR/Instruction.h"33#include "llvm/IR/Instructions.h"34#include "llvm/IR/Type.h"35#include "llvm/IR/Value.h"36#include "llvm/InitializePasses.h"37#include "llvm/Pass.h"38#include "llvm/Support/Casting.h"39#include "llvm/Support/CommandLine.h"40#include "llvm/Target/TargetMachine.h"41 42#define DEBUG_TYPE "type-promotion"43#define PASS_NAME "Type Promotion"44 45using namespace llvm;46 47static cl::opt<bool> DisablePromotion("disable-type-promotion", cl::Hidden,48 cl::init(false),49 cl::desc("Disable type promotion pass"));50 51// The goal of this pass is to enable more efficient code generation for52// operations on narrow types (i.e. types with < 32-bits) and this is a53// motivating IR code example:54//55// define hidden i32 @cmp(i8 zeroext) {56// %2 = add i8 %0, -4957// %3 = icmp ult i8 %2, 358// ..59// }60//61// The issue here is that i8 is type-legalized to i32 because i8 is not a62// legal type. Thus, arithmetic is done in integer-precision, but then the63// byte value is masked out as follows:64//65// t19: i32 = add t4, Constant:i32<-49>66// t24: i32 = and t19, Constant:i32<255>67//68// Consequently, we generate code like this:69//70// subs r0, #4971// uxtb r1, r072// cmp r1, #373//74// This shows that masking out the byte value results in generation of75// the UXTB instruction. This is not optimal as r0 already contains the byte76// value we need, and so instead we can just generate:77//78// sub.w r1, r0, #4979// cmp r1, #380//81// We achieve this by type promoting the IR to i32 like so for this example:82//83// define i32 @cmp(i8 zeroext %c) {84// %0 = zext i8 %c to i3285// %c.off = add i32 %0, -4986// %1 = icmp ult i32 %c.off, 387// ..88// }89//90// For this to be valid and legal, we need to prove that the i32 add is91// producing the same value as the i8 addition, and that e.g. no overflow92// happens.93//94// A brief sketch of the algorithm and some terminology.95// We pattern match interesting IR patterns:96// - which have "sources": instructions producing narrow values (i8, i16), and97// - they have "sinks": instructions consuming these narrow values.98//99// We collect all instruction connecting sources and sinks in a worklist, so100// that we can mutate these instruction and perform type promotion when it is101// legal to do so.102 103namespace {104class IRPromoter {105 LLVMContext &Ctx;106 unsigned PromotedWidth = 0;107 SetVector<Value *> &Visited;108 SetVector<Value *> &Sources;109 SetVector<Instruction *> &Sinks;110 SmallPtrSetImpl<Instruction *> &SafeWrap;111 SmallPtrSetImpl<Instruction *> &InstsToRemove;112 IntegerType *ExtTy = nullptr;113 SmallPtrSet<Value *, 8> NewInsts;114 DenseMap<Value *, SmallVector<Type *, 4>> TruncTysMap;115 SmallPtrSet<Value *, 8> Promoted;116 117 void ReplaceAllUsersOfWith(Value *From, Value *To);118 void ExtendSources();119 void ConvertTruncs();120 void PromoteTree();121 void TruncateSinks();122 void Cleanup();123 124public:125 IRPromoter(LLVMContext &C, unsigned Width, SetVector<Value *> &visited,126 SetVector<Value *> &sources, SetVector<Instruction *> &sinks,127 SmallPtrSetImpl<Instruction *> &wrap,128 SmallPtrSetImpl<Instruction *> &instsToRemove)129 : Ctx(C), PromotedWidth(Width), Visited(visited), Sources(sources),130 Sinks(sinks), SafeWrap(wrap), InstsToRemove(instsToRemove) {131 ExtTy = IntegerType::get(Ctx, PromotedWidth);132 }133 134 void Mutate();135};136 137class TypePromotionImpl {138 unsigned TypeSize = 0;139 const TargetLowering *TLI = nullptr;140 LLVMContext *Ctx = nullptr;141 unsigned RegisterBitWidth = 0;142 SmallPtrSet<Value *, 16> AllVisited;143 SmallPtrSet<Instruction *, 8> SafeToPromote;144 SmallPtrSet<Instruction *, 4> SafeWrap;145 SmallPtrSet<Instruction *, 4> InstsToRemove;146 147 // Does V have the same size result type as TypeSize.148 bool EqualTypeSize(Value *V);149 // Does V have the same size, or narrower, result type as TypeSize.150 bool LessOrEqualTypeSize(Value *V);151 // Does V have a result type that is wider than TypeSize.152 bool GreaterThanTypeSize(Value *V);153 // Does V have a result type that is narrower than TypeSize.154 bool LessThanTypeSize(Value *V);155 // Should V be a leaf in the promote tree?156 bool isSource(Value *V);157 // Should V be a root in the promotion tree?158 bool isSink(Value *V);159 // Should we change the result type of V? It will result in the users of V160 // being visited.161 bool shouldPromote(Value *V);162 // Is I an add or a sub, which isn't marked as nuw, but where a wrapping163 // result won't affect the computation?164 bool isSafeWrap(Instruction *I);165 // Can V have its integer type promoted, or can the type be ignored.166 bool isSupportedType(Value *V);167 // Is V an instruction with a supported opcode or another value that we can168 // handle, such as constants and basic blocks.169 bool isSupportedValue(Value *V);170 // Is V an instruction thats result can trivially promoted, or has safe171 // wrapping.172 bool isLegalToPromote(Value *V);173 bool TryToPromote(Value *V, unsigned PromotedWidth, const LoopInfo &LI);174 175public:176 bool run(Function &F, const TargetMachine *TM,177 const TargetTransformInfo &TTI, const LoopInfo &LI);178};179 180class TypePromotionLegacy : public FunctionPass {181public:182 static char ID;183 184 TypePromotionLegacy() : FunctionPass(ID) {}185 186 void getAnalysisUsage(AnalysisUsage &AU) const override {187 AU.addRequired<LoopInfoWrapperPass>();188 AU.addRequired<TargetTransformInfoWrapperPass>();189 AU.addRequired<TargetPassConfig>();190 AU.setPreservesCFG();191 AU.addPreserved<LoopInfoWrapperPass>();192 }193 194 StringRef getPassName() const override { return PASS_NAME; }195 196 bool runOnFunction(Function &F) override;197};198 199} // namespace200 201static bool GenerateSignBits(Instruction *I) {202 unsigned Opc = I->getOpcode();203 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||204 Opc == Instruction::SRem || Opc == Instruction::SExt;205}206 207bool TypePromotionImpl::EqualTypeSize(Value *V) {208 return V->getType()->getScalarSizeInBits() == TypeSize;209}210 211bool TypePromotionImpl::LessOrEqualTypeSize(Value *V) {212 return V->getType()->getScalarSizeInBits() <= TypeSize;213}214 215bool TypePromotionImpl::GreaterThanTypeSize(Value *V) {216 return V->getType()->getScalarSizeInBits() > TypeSize;217}218 219bool TypePromotionImpl::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, producing224/// a narrow 'TypeSize' value. These values will be zext to start the promotion225/// of the tree to i32. We guarantee that these won't populate the upper bits226/// of the register. ZExt on the loads will be free, and the same for call227/// 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 free229/// too.230bool TypePromotionImpl::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 (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 the247/// the IR to remain valid. We can't mutate the value type of these248/// instructions.249bool TypePromotionImpl::isSink(Value *V) {250 // TODO The truncate also isn't actually necessary because we would already251 // proved that the data value is kept within the range of the original data252 // type. We currently remove any truncs inserted for handling zext sinks.253 254 // Sinks are:255 // - points where the value in the register is being observed, such as an256 // 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 removed259 // 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.275bool TypePromotionImpl::isSafeWrap(Instruction *I) {276 // We can support a potentially wrapping Add/Sub instruction (I) if:277 // - It is only used by an unsigned icmp.278 // - The icmp uses a constant.279 // - The wrapping instruction (I) also uses a constant.280 //281 // This a common pattern emitted to check if a value is within a range.282 //283 // For example:284 //285 // %sub = sub i8 %a, C1286 // %cmp = icmp ule i8 %sub, C2287 //288 // or289 //290 // %add = add i8 %a, C1291 // %cmp = icmp ule i8 %add, C2.292 //293 // We will treat an add as though it were a subtract by -C1. To promote294 // the Add/Sub we will zero extend the LHS and the subtracted amount. For Add,295 // this means we need to negate the constant, zero extend to RegisterBitWidth,296 // and negate in the larger type.297 //298 // This will produce a value in the range [-zext(C1), zext(X)-zext(C1)] where299 // C1 is the subtracted amount. This is either a small unsigned number or a300 // large unsigned number in the promoted type.301 //302 // Now we need to correct the compare constant C2. Values >= C1 in the303 // original add result range have been remapped to large values in the304 // promoted range. If the compare constant fell into this range we need to305 // remap it as well. We can do this as -(zext(-C2)).306 //307 // For example:308 //309 // %sub = sub i8 %a, 2310 // %cmp = icmp ule i8 %sub, 254311 //312 // becomes313 //314 // %zext = zext %a to i32315 // %sub = sub i32 %zext, 2316 // %cmp = icmp ule i32 %sub, 4294967294317 //318 // Another example:319 //320 // %sub = sub i8 %a, 1321 // %cmp = icmp ule i8 %sub, 254322 //323 // becomes324 //325 // %zext = zext %a to i32326 // %sub = sub i32 %zext, 1327 // %cmp = icmp ule i32 %sub, 254328 329 unsigned Opc = I->getOpcode();330 if (Opc != Instruction::Add && Opc != Instruction::Sub)331 return false;332 333 if (!I->hasOneUse() || !isa<ICmpInst>(*I->user_begin()) ||334 !isa<ConstantInt>(I->getOperand(1)))335 return false;336 337 // Don't support an icmp that deals with sign bits.338 auto *CI = cast<ICmpInst>(*I->user_begin());339 if (CI->isSigned() || CI->isEquality())340 return false;341 342 ConstantInt *ICmpConstant = nullptr;343 if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))344 ICmpConstant = Const;345 else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))346 ICmpConstant = Const;347 else348 return false;349 350 const APInt &ICmpConst = ICmpConstant->getValue();351 APInt OverflowConst = cast<ConstantInt>(I->getOperand(1))->getValue();352 if (Opc == Instruction::Sub)353 OverflowConst = -OverflowConst;354 355 // If the constant is positive, we will end up filling the promoted bits with356 // all 1s. Make sure that results in a cheap add constant.357 if (!OverflowConst.isNonPositive()) {358 // We don't have the true promoted width, just use 64 so we can create an359 // int64_t for the isLegalAddImmediate call.360 if (OverflowConst.getBitWidth() >= 64)361 return false;362 363 APInt NewConst = -((-OverflowConst).zext(64));364 if (!TLI->isLegalAddImmediate(NewConst.getSExtValue()))365 return false;366 }367 368 SafeWrap.insert(I);369 370 if (OverflowConst == 0 || OverflowConst.ugt(ICmpConst)) {371 LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for "372 << "const of " << *I << "\n");373 return true;374 }375 376 LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for "377 << "const of " << *I << " and " << *CI << "\n");378 SafeWrap.insert(CI);379 return true;380}381 382bool TypePromotionImpl::shouldPromote(Value *V) {383 if (!isa<IntegerType>(V->getType()) || isSink(V))384 return false;385 386 if (isSource(V))387 return true;388 389 auto *I = dyn_cast<Instruction>(V);390 if (!I)391 return false;392 393 if (isa<ICmpInst>(I))394 return false;395 396 return true;397}398 399/// Return whether we can safely mutate V's type to ExtTy without having to be400/// concerned with zero extending or truncation.401static bool isPromotedResultSafe(Instruction *I) {402 if (GenerateSignBits(I))403 return false;404 405 if (!isa<OverflowingBinaryOperator>(I))406 return true;407 408 return I->hasNoUnsignedWrap();409}410 411void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {412 SmallVector<Instruction *, 4> Users;413 Instruction *InstTo = dyn_cast<Instruction>(To);414 bool ReplacedAll = true;415 416 LLVM_DEBUG(dbgs() << "IR Promotion: Replacing " << *From << " with " << *To417 << "\n");418 419 for (Use &U : From->uses()) {420 auto *User = cast<Instruction>(U.getUser());421 if (InstTo && User->isIdenticalTo(InstTo)) {422 ReplacedAll = false;423 continue;424 }425 Users.push_back(User);426 }427 428 for (auto *U : Users)429 U->replaceUsesOfWith(From, To);430 431 if (ReplacedAll)432 if (auto *I = dyn_cast<Instruction>(From))433 InstsToRemove.insert(I);434}435 436void IRPromoter::ExtendSources() {437 IRBuilder<> Builder{Ctx};438 439 auto InsertZExt = [&](Value *V, BasicBlock::iterator InsertPt) {440 assert(V->getType() != ExtTy && "zext already extends to i32");441 LLVM_DEBUG(dbgs() << "IR Promotion: Inserting ZExt for " << *V << "\n");442 Builder.SetInsertPoint(InsertPt);443 if (auto *I = dyn_cast<Instruction>(V))444 Builder.SetCurrentDebugLocation(I->getDebugLoc());445 446 Value *ZExt = Builder.CreateZExt(V, ExtTy);447 if (auto *I = dyn_cast<Instruction>(ZExt)) {448 if (isa<Argument>(V))449 I->moveBefore(InsertPt);450 else451 I->moveAfter(&*InsertPt);452 NewInsts.insert(I);453 }454 455 ReplaceAllUsersOfWith(V, ZExt);456 };457 458 // Now, insert extending instructions between the sources and their users.459 LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n");460 for (auto *V : Sources) {461 LLVM_DEBUG(dbgs() << " - " << *V << "\n");462 if (auto *I = dyn_cast<Instruction>(V))463 InsertZExt(I, I->getIterator());464 else if (auto *Arg = dyn_cast<Argument>(V)) {465 BasicBlock &BB = Arg->getParent()->front();466 InsertZExt(Arg, BB.getFirstInsertionPt());467 } else {468 llvm_unreachable("unhandled source that needs extending");469 }470 Promoted.insert(V);471 }472}473 474void IRPromoter::PromoteTree() {475 LLVM_DEBUG(dbgs() << "IR Promotion: Mutating the tree..\n");476 477 // Mutate the types of the instructions within the tree. Here we handle478 // constant operands.479 for (auto *V : Visited) {480 if (Sources.count(V))481 continue;482 483 auto *I = cast<Instruction>(V);484 if (Sinks.count(I))485 continue;486 487 for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {488 Value *Op = I->getOperand(i);489 if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))490 continue;491 492 if (auto *Const = dyn_cast<ConstantInt>(Op)) {493 // For subtract, we only need to zext the constant. We only put it in494 // SafeWrap because SafeWrap.size() is used elsewhere.495 // For Add and ICmp we need to find how far the constant is from the496 // top of its original unsigned range and place it the same distance497 // from the top of its new unsigned range. We can do this by negating498 // the constant, zero extending it, then negating in the new type.499 APInt NewConst;500 if (SafeWrap.contains(I)) {501 if (I->getOpcode() == Instruction::ICmp)502 NewConst = -((-Const->getValue()).zext(PromotedWidth));503 else if (I->getOpcode() == Instruction::Add && i == 1)504 NewConst = -((-Const->getValue()).zext(PromotedWidth));505 else506 NewConst = Const->getValue().zext(PromotedWidth);507 } else508 NewConst = Const->getValue().zext(PromotedWidth);509 510 I->setOperand(i, ConstantInt::get(Const->getContext(), NewConst));511 } else if (isa<UndefValue>(Op))512 I->setOperand(i, ConstantInt::get(ExtTy, 0));513 }514 515 // Mutate the result type, unless this is an icmp or switch.516 if (!isa<ICmpInst>(I) && !isa<SwitchInst>(I)) {517 I->mutateType(ExtTy);518 Promoted.insert(I);519 }520 }521}522 523void IRPromoter::TruncateSinks() {524 LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n");525 526 IRBuilder<> Builder{Ctx};527 528 auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction * {529 if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))530 return nullptr;531 532 if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))533 return nullptr;534 535 LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "536 << *V << "\n");537 Builder.SetInsertPoint(cast<Instruction>(V));538 auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));539 if (Trunc)540 NewInsts.insert(Trunc);541 return Trunc;542 };543 544 // Fix up any stores or returns that use the results of the promoted545 // chain.546 for (auto *I : Sinks) {547 LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");548 549 // Handle calls separately as we need to iterate over arg operands.550 if (auto *Call = dyn_cast<CallInst>(I)) {551 for (unsigned i = 0; i < Call->arg_size(); ++i) {552 Value *Arg = Call->getArgOperand(i);553 Type *Ty = TruncTysMap[Call][i];554 if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {555 Trunc->moveBefore(Call->getIterator());556 Call->setArgOperand(i, Trunc);557 }558 }559 continue;560 }561 562 // Special case switches because we need to truncate the condition.563 if (auto *Switch = dyn_cast<SwitchInst>(I)) {564 Type *Ty = TruncTysMap[Switch][0];565 if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {566 Trunc->moveBefore(Switch->getIterator());567 Switch->setCondition(Trunc);568 }569 continue;570 }571 572 // Don't insert a trunc for a zext which can still legally promote.573 // Nor insert a trunc when the input value to that trunc has the same width574 // as the zext we are inserting it for. When this happens the input operand575 // for the zext will be promoted to the same width as the zext's return type576 // rendering that zext unnecessary. This zext gets removed before the end577 // of the pass.578 if (auto ZExt = dyn_cast<ZExtInst>(I))579 if (ZExt->getType()->getScalarSizeInBits() >= PromotedWidth)580 continue;581 582 // Now handle the others.583 for (unsigned i = 0; i < I->getNumOperands(); ++i) {584 Type *Ty = TruncTysMap[I][i];585 if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {586 Trunc->moveBefore(I->getIterator());587 I->setOperand(i, Trunc);588 }589 }590 }591}592 593void IRPromoter::Cleanup() {594 LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");595 // Some zexts will now have become redundant, along with their trunc596 // operands, so remove them.597 for (auto *V : Visited) {598 if (!isa<ZExtInst>(V))599 continue;600 601 auto ZExt = cast<ZExtInst>(V);602 if (ZExt->getDestTy() != ExtTy)603 continue;604 605 Value *Src = ZExt->getOperand(0);606 if (ZExt->getSrcTy() == ZExt->getDestTy()) {607 LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt608 << "\n");609 ReplaceAllUsersOfWith(ZExt, Src);610 continue;611 }612 613 // We've inserted a trunc for a zext sink, but we already know that the614 // input is in range, negating the need for the trunc.615 if (NewInsts.count(Src) && isa<TruncInst>(Src)) {616 auto *Trunc = cast<TruncInst>(Src);617 assert(Trunc->getOperand(0)->getType() == ExtTy &&618 "expected inserted trunc to be operating on i32");619 ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));620 }621 }622 623 for (auto *I : InstsToRemove) {624 LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n");625 I->dropAllReferences();626 }627}628 629void IRPromoter::ConvertTruncs() {630 LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");631 IRBuilder<> Builder{Ctx};632 633 for (auto *V : Visited) {634 if (!isa<TruncInst>(V) || Sources.count(V))635 continue;636 637 auto *Trunc = cast<TruncInst>(V);638 Builder.SetInsertPoint(Trunc);639 IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());640 IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);641 642 unsigned NumBits = DestTy->getScalarSizeInBits();643 ConstantInt *Mask =644 ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());645 Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);646 if (SrcTy->getBitWidth() > ExtTy->getBitWidth())647 Masked = Builder.CreateTrunc(Masked, ExtTy);648 649 if (auto *I = dyn_cast<Instruction>(Masked))650 NewInsts.insert(I);651 652 ReplaceAllUsersOfWith(Trunc, Masked);653 }654}655 656void IRPromoter::Mutate() {657 LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains to "658 << PromotedWidth << "-bits\n");659 660 // Cache original types of the values that will likely need truncating661 for (auto *I : Sinks) {662 if (auto *Call = dyn_cast<CallInst>(I)) {663 for (Value *Arg : Call->args())664 TruncTysMap[Call].push_back(Arg->getType());665 } else if (auto *Switch = dyn_cast<SwitchInst>(I))666 TruncTysMap[I].push_back(Switch->getCondition()->getType());667 else {668 for (const Value *Op : I->operands())669 TruncTysMap[I].push_back(Op->getType());670 }671 }672 for (auto *V : Visited) {673 if (!isa<TruncInst>(V) || Sources.count(V))674 continue;675 auto *Trunc = cast<TruncInst>(V);676 TruncTysMap[Trunc].push_back(Trunc->getDestTy());677 }678 679 // Insert zext instructions between sources and their users.680 ExtendSources();681 682 // Promote visited instructions, mutating their types in place.683 PromoteTree();684 685 // Convert any truncs, that aren't sources, into AND masks.686 ConvertTruncs();687 688 // Insert trunc instructions for use by calls, stores etc...689 TruncateSinks();690 691 // Finally, remove unecessary zexts and truncs, delete old instructions and692 // clear the data structures.693 Cleanup();694 695 LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n");696}697 698/// We disallow booleans to make life easier when dealing with icmps but allow699/// any other integer that fits in a scalar register. Void types are accepted700/// so we can handle switches.701bool TypePromotionImpl::isSupportedType(Value *V) {702 Type *Ty = V->getType();703 704 // Allow voids and pointers, these won't be promoted.705 if (Ty->isVoidTy() || Ty->isPointerTy())706 return true;707 708 if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->getBitWidth() == 1 ||709 cast<IntegerType>(Ty)->getBitWidth() > RegisterBitWidth)710 return false;711 712 return LessOrEqualTypeSize(V);713}714 715/// We accept most instructions, as well as Arguments and ConstantInsts. We716/// Disallow casts other than zext and truncs and only allow calls if their717/// return value is zeroext. We don't allow opcodes that can introduce sign718/// bits.719bool TypePromotionImpl::isSupportedValue(Value *V) {720 if (auto *I = dyn_cast<Instruction>(V)) {721 switch (I->getOpcode()) {722 default:723 return isa<BinaryOperator>(I) && isSupportedType(I) &&724 !GenerateSignBits(I);725 case Instruction::GetElementPtr:726 case Instruction::Store:727 case Instruction::Br:728 case Instruction::Switch:729 return true;730 case Instruction::PHI:731 case Instruction::Select:732 case Instruction::Ret:733 case Instruction::Load:734 case Instruction::Trunc:735 return isSupportedType(I);736 case Instruction::BitCast:737 return I->getOperand(0)->getType() == I->getType();738 case Instruction::ZExt:739 return isSupportedType(I->getOperand(0));740 case Instruction::ICmp:741 // Now that we allow small types than TypeSize, only allow icmp of742 // TypeSize because they will require a trunc to be legalised.743 // TODO: Allow icmp of smaller types, and calculate at the end744 // whether the transform would be beneficial.745 if (isa<PointerType>(I->getOperand(0)->getType()))746 return true;747 return EqualTypeSize(I->getOperand(0));748 case Instruction::Call: {749 // Special cases for calls as we need to check for zeroext750 // TODO We should accept calls even if they don't have zeroext, as they751 // can still be sinks.752 auto *Call = cast<CallInst>(I);753 return isSupportedType(Call) &&754 Call->hasRetAttr(Attribute::AttrKind::ZExt);755 }756 }757 } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {758 return isSupportedType(V);759 } else if (isa<Argument>(V))760 return isSupportedType(V);761 762 return isa<BasicBlock>(V);763}764 765/// Check that the type of V would be promoted and that the original type is766/// smaller than the targeted promoted type. Check that we're not trying to767/// promote something larger than our base 'TypeSize' type.768bool TypePromotionImpl::isLegalToPromote(Value *V) {769 auto *I = dyn_cast<Instruction>(V);770 if (!I)771 return true;772 773 if (SafeToPromote.count(I))774 return true;775 776 if (isPromotedResultSafe(I) || isSafeWrap(I)) {777 SafeToPromote.insert(I);778 return true;779 }780 return false;781}782 783bool TypePromotionImpl::TryToPromote(Value *V, unsigned PromotedWidth,784 const LoopInfo &LI) {785 Type *OrigTy = V->getType();786 TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedValue();787 SafeToPromote.clear();788 SafeWrap.clear();789 790 if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))791 return false;792 793 LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from "794 << TypeSize << " bits to " << PromotedWidth << "\n");795 796 SetVector<Value *> WorkList;797 SetVector<Value *> Sources;798 SetVector<Instruction *> Sinks;799 SetVector<Value *> CurrentVisited;800 WorkList.insert(V);801 802 // Return true if V was added to the worklist as a supported instruction,803 // if it was already visited, or if we don't need to explore it (e.g.804 // pointer values and GEPs), and false otherwise.805 auto AddLegalInst = [&](Value *V) {806 if (CurrentVisited.count(V))807 return true;808 809 // Skip promoting GEPs as their indices should have already been810 // canonicalized to pointer width.811 if (isa<GetElementPtrInst>(V))812 return false;813 814 if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {815 LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n");816 return false;817 }818 819 WorkList.insert(V);820 return true;821 };822 823 // Iterate through, and add to, a tree of operands and users in the use-def.824 while (!WorkList.empty()) {825 Value *V = WorkList.pop_back_val();826 if (CurrentVisited.count(V))827 continue;828 829 // Ignore non-instructions, other than arguments.830 if (!isa<Instruction>(V) && !isSource(V))831 continue;832 833 // If we've already visited this value from somewhere, bail now because834 // the tree has already been explored.835 // TODO: This could limit the transform, ie if we try to promote something836 // from an i8 and fail first, before trying an i16.837 if (!AllVisited.insert(V).second)838 return false;839 840 CurrentVisited.insert(V);841 842 // Calls can be both sources and sinks.843 if (isSink(V))844 Sinks.insert(cast<Instruction>(V));845 846 if (isSource(V))847 Sources.insert(V);848 849 if (!isSink(V) && !isSource(V)) {850 if (auto *I = dyn_cast<Instruction>(V)) {851 // Visit operands of any instruction visited.852 for (auto &U : I->operands()) {853 if (!AddLegalInst(U))854 return false;855 }856 }857 }858 859 // Don't visit users of a node which isn't going to be mutated unless its a860 // source.861 if (isSource(V) || shouldPromote(V)) {862 for (Use &U : V->uses()) {863 if (!AddLegalInst(U.getUser()))864 return false;865 }866 }867 }868 869 LLVM_DEBUG({870 dbgs() << "IR Promotion: Visited nodes:\n";871 for (auto *I : CurrentVisited)872 I->dump();873 });874 875 unsigned ToPromote = 0;876 unsigned NonFreeArgs = 0;877 unsigned NonLoopSources = 0, LoopSinks = 0;878 SmallPtrSet<BasicBlock *, 4> Blocks;879 for (auto *CV : CurrentVisited) {880 if (auto *I = dyn_cast<Instruction>(CV))881 Blocks.insert(I->getParent());882 883 if (Sources.count(CV)) {884 if (auto *Arg = dyn_cast<Argument>(CV))885 if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())886 ++NonFreeArgs;887 if (!isa<Instruction>(CV) ||888 !LI.getLoopFor(cast<Instruction>(CV)->getParent()))889 ++NonLoopSources;890 continue;891 }892 893 if (isa<PHINode>(CV))894 continue;895 if (LI.getLoopFor(cast<Instruction>(CV)->getParent()))896 ++LoopSinks;897 if (Sinks.count(cast<Instruction>(CV)))898 continue;899 ++ToPromote;900 }901 902 // DAG optimizations should be able to handle these cases better, especially903 // for function arguments.904 if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&905 (ToPromote < 2 || (Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))906 return false;907 908 IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,909 SafeWrap, InstsToRemove);910 Promoter.Mutate();911 return true;912}913 914bool TypePromotionImpl::run(Function &F, const TargetMachine *TM,915 const TargetTransformInfo &TTI,916 const LoopInfo &LI) {917 if (DisablePromotion)918 return false;919 920 LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n");921 922 AllVisited.clear();923 SafeToPromote.clear();924 SafeWrap.clear();925 bool MadeChange = false;926 const DataLayout &DL = F.getDataLayout();927 const TargetSubtargetInfo *SubtargetInfo = TM->getSubtargetImpl(F);928 TLI = SubtargetInfo->getTargetLowering();929 RegisterBitWidth =930 TTI.getRegisterBitWidth(TargetTransformInfo::RGK_Scalar).getFixedValue();931 Ctx = &F.getContext();932 933 // Return the preferred integer width of the instruction, or zero if we934 // shouldn't try.935 auto GetPromoteWidth = [&](Instruction *I) -> uint32_t {936 if (!isa<IntegerType>(I->getType()))937 return 0;938 939 EVT SrcVT = TLI->getValueType(DL, I->getType());940 if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT()))941 return 0;942 943 if (TLI->getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger)944 return 0;945 946 EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT);947 if (TLI->isSExtCheaperThanZExt(SrcVT, PromotedVT))948 return 0;949 if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) {950 LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register "951 << "for promoted type\n");952 return 0;953 }954 955 // TODO: Should we prefer to use RegisterBitWidth instead?956 return PromotedVT.getFixedSizeInBits();957 };958 959 auto BBIsInLoop = [&](BasicBlock *BB) -> bool {960 for (auto *L : LI)961 if (L->contains(BB))962 return true;963 return false;964 };965 966 for (BasicBlock &BB : F) {967 for (Instruction &I : BB) {968 if (AllVisited.count(&I))969 continue;970 971 if (isa<ZExtInst>(&I) && isa<PHINode>(I.getOperand(0)) &&972 isa<IntegerType>(I.getType()) && BBIsInLoop(&BB)) {973 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: "974 << *I.getOperand(0) << "\n");975 EVT ZExtVT = TLI->getValueType(DL, I.getType());976 Instruction *Phi = static_cast<Instruction *>(I.getOperand(0));977 auto PromoteWidth = ZExtVT.getFixedSizeInBits();978 if (RegisterBitWidth < PromoteWidth) {979 LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target "980 << "register for ZExt type\n");981 continue;982 }983 MadeChange |= TryToPromote(Phi, PromoteWidth, LI);984 } else if (auto *ICmp = dyn_cast<ICmpInst>(&I)) {985 // Search up from icmps to try to promote their operands.986 // Skip signed or pointer compares987 if (ICmp->isSigned())988 continue;989 990 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");991 992 for (auto &Op : ICmp->operands()) {993 if (auto *OpI = dyn_cast<Instruction>(Op)) {994 if (auto PromotedWidth = GetPromoteWidth(OpI)) {995 MadeChange |= TryToPromote(OpI, PromotedWidth, LI);996 break;997 }998 }999 }1000 }1001 }1002 if (!InstsToRemove.empty()) {1003 for (auto *I : InstsToRemove)1004 I->eraseFromParent();1005 InstsToRemove.clear();1006 }1007 }1008 1009 AllVisited.clear();1010 SafeToPromote.clear();1011 SafeWrap.clear();1012 1013 return MadeChange;1014}1015 1016INITIALIZE_PASS_BEGIN(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)1017INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)1018INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)1019INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)1020INITIALIZE_PASS_END(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)1021 1022char TypePromotionLegacy::ID = 0;1023 1024bool TypePromotionLegacy::runOnFunction(Function &F) {1025 if (skipFunction(F))1026 return false;1027 1028 auto &TPC = getAnalysis<TargetPassConfig>();1029 auto *TM = &TPC.getTM<TargetMachine>();1030 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);1031 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();1032 1033 TypePromotionImpl TP;1034 return TP.run(F, TM, TTI, LI);1035}1036 1037FunctionPass *llvm::createTypePromotionLegacyPass() {1038 return new TypePromotionLegacy();1039}1040 1041PreservedAnalyses TypePromotionPass::run(Function &F,1042 FunctionAnalysisManager &AM) {1043 auto &TTI = AM.getResult<TargetIRAnalysis>(F);1044 auto &LI = AM.getResult<LoopAnalysis>(F);1045 TypePromotionImpl TP;1046 1047 bool Changed = TP.run(F, TM, TTI, LI);1048 if (!Changed)1049 return PreservedAnalyses::all();1050 1051 PreservedAnalyses PA;1052 PA.preserveSet<CFGAnalyses>();1053 PA.preserve<LoopAnalysis>();1054 return PA;1055}1056