40 #define DEBUG_TYPE "type-promotion"
41 #define PASS_NAME "Type Promotion"
47 cl::desc(
"Disable type promotion pass"));
104 unsigned PromotedWidth = 0;
116 void ExtendSources();
117 void ConvertTruncs();
119 void TruncateSinks();
127 : Ctx(
C), PromotedWidth(
Width), Visited(visited),
128 Sources(sources), Sinks(sinks), SafeWrap(
wrap) {
138 unsigned RegisterBitWidth = 0;
144 bool EqualTypeSize(
Value *V);
146 bool LessOrEqualTypeSize(
Value *V);
148 bool GreaterThanTypeSize(
Value *V);
150 bool LessThanTypeSize(
Value *V);
152 bool isSource(
Value *V);
154 bool isSink(
Value *V);
157 bool shouldPromote(
Value *V);
165 bool isSupportedValue(
Value *V);
169 bool TryToPromote(
Value *V,
unsigned PromotedWidth);
190 unsigned Opc =
I->getOpcode();
191 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
192 Opc == Instruction::SRem || Opc == Instruction::SExt;
195 bool TypePromotion::EqualTypeSize(
Value *V) {
199 bool TypePromotion::LessOrEqualTypeSize(
Value *V) {
203 bool TypePromotion::GreaterThanTypeSize(
Value *V) {
207 bool TypePromotion::LessThanTypeSize(
Value *V) {
218 bool TypePromotion::isSource(
Value *V) {
219 if (!isa<IntegerType>(V->
getType()))
223 if (isa<Argument>(V))
225 else if (isa<LoadInst>(V))
227 else if (isa<BitCastInst>(V))
229 else if (
auto *Call = dyn_cast<CallInst>(V))
230 return Call->hasRetAttr(Attribute::AttrKind::ZExt);
231 else if (
auto *Trunc = dyn_cast<TruncInst>(V))
232 return EqualTypeSize(Trunc);
239 bool TypePromotion::isSink(
Value *V) {
250 if (
auto *
Store = dyn_cast<StoreInst>(V))
251 return LessOrEqualTypeSize(
Store->getValueOperand());
252 if (
auto *Return = dyn_cast<ReturnInst>(V))
253 return LessOrEqualTypeSize(
Return->getReturnValue());
254 if (
auto *ZExt = dyn_cast<ZExtInst>(V))
255 return GreaterThanTypeSize(ZExt);
256 if (
auto *Switch = dyn_cast<SwitchInst>(V))
257 return LessThanTypeSize(
Switch->getCondition());
258 if (
auto *ICmp = dyn_cast<ICmpInst>(V))
259 return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
261 return isa<CallInst>(V);
325 unsigned Opc =
I->getOpcode();
329 if (!
I->hasOneUse() || !isa<ICmpInst>(*
I->user_begin()) ||
330 !isa<ConstantInt>(
I->getOperand(1)))
334 auto *CI = cast<ICmpInst>(*
I->user_begin());
335 if (CI->isSigned() || CI->isEquality())
339 if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
340 ICmpConstant =
Const;
341 else if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
342 ICmpConstant =
Const;
347 APInt OverflowConst = cast<ConstantInt>(
I->getOperand(1))->getValue();
348 if (Opc == Instruction::Sub)
349 OverflowConst = -OverflowConst;
356 if (OverflowConst.
sgt(ICmpConst)) {
357 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
358 <<
"const of " << *
I <<
"\n");
362 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
363 <<
"const of " << *
I <<
" and " << *CI <<
"\n");
371 bool TypePromotion::shouldPromote(
Value *V) {
372 if (!isa<IntegerType>(V->
getType()) || isSink(V))
378 auto *
I = dyn_cast<Instruction>(V);
382 if (isa<ICmpInst>(
I))
394 if (!isa<OverflowingBinaryOperator>(
I))
397 return I->hasNoUnsignedWrap();
403 bool ReplacedAll =
true;
409 auto *
User = cast<Instruction>(U.getUser());
410 if (InstTo &&
User->isIdenticalTo(InstTo)) {
417 for (
auto *U :
Users)
418 U->replaceUsesOfWith(
From, To);
421 if (
auto *
I = dyn_cast<Instruction>(
From))
422 InstsToRemove.insert(
I);
425 void IRPromoter::ExtendSources() {
429 assert(V->
getType() != ExtTy &&
"zext already extends to i32");
430 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Inserting ZExt for " << *V <<
"\n");
431 Builder.SetInsertPoint(InsertPt);
432 if (
auto *
I = dyn_cast<Instruction>(V))
433 Builder.SetCurrentDebugLocation(
I->getDebugLoc());
436 if (
auto *
I = dyn_cast<Instruction>(ZExt)) {
437 if (isa<Argument>(V))
438 I->moveBefore(InsertPt);
440 I->moveAfter(InsertPt);
444 ReplaceAllUsersOfWith(V, ZExt);
449 for (
auto V : Sources) {
451 if (
auto *
I = dyn_cast<Instruction>(V))
453 else if (
auto *
Arg = dyn_cast<Argument>(V)) {
455 InsertZExt(
Arg, &*
BB.getFirstInsertionPt());
463 void IRPromoter::PromoteTree() {
468 for (
auto *V : Visited) {
469 if (Sources.count(V))
472 auto *
I = cast<Instruction>(V);
476 for (
unsigned i = 0,
e =
I->getNumOperands();
i <
e; ++
i) {
478 if ((
Op->getType() == ExtTy) || !isa<IntegerType>(
Op->getType()))
481 if (
auto *Const = dyn_cast<ConstantInt>(
Op)) {
486 Constant *NewConst = (SafeWrap.contains(
I) &&
487 (
I->getOpcode() == Instruction::ICmp ||
i == 1) &&
488 I->getOpcode() != Instruction::Sub)
491 I->setOperand(
i, NewConst);
492 }
else if (isa<UndefValue>(
Op))
497 if (!isa<ICmpInst>(
I) && !isa<SwitchInst>(
I)) {
498 I->mutateType(ExtTy);
504 void IRPromoter::TruncateSinks() {
510 if (!isa<Instruction>(V) || !isa<IntegerType>(V->
getType()))
513 if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
516 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Creating " << *TruncTy <<
" Trunc for "
518 Builder.SetInsertPoint(cast<Instruction>(V));
519 auto *Trunc = dyn_cast<Instruction>(
Builder.CreateTrunc(V, TruncTy));
521 NewInsts.insert(Trunc);
527 for (
auto I : Sinks) {
531 if (
auto *Call = dyn_cast<CallInst>(
I)) {
532 for (
unsigned i = 0;
i <
Call->arg_size(); ++
i) {
536 Trunc->moveBefore(Call);
537 Call->setArgOperand(
i, Trunc);
544 if (
auto *Switch = dyn_cast<SwitchInst>(
I)) {
547 Trunc->moveBefore(Switch);
548 Switch->setCondition(Trunc);
554 if (
auto ZExt = dyn_cast<ZExtInst>(
I))
559 for (
unsigned i = 0;
i <
I->getNumOperands(); ++
i) {
560 Type *Ty = TruncTysMap[
I][
i];
561 if (
Instruction *Trunc = InsertTrunc(
I->getOperand(
i), Ty)) {
562 Trunc->moveBefore(
I);
563 I->setOperand(
i, Trunc);
573 for (
auto V : Visited) {
574 if (!isa<ZExtInst>(V))
577 auto ZExt = cast<ZExtInst>(V);
578 if (ZExt->getDestTy() != ExtTy)
581 Value *Src = ZExt->getOperand(0);
582 if (ZExt->getSrcTy() == ZExt->getDestTy()) {
583 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Removing unnecessary cast: " << *ZExt
585 ReplaceAllUsersOfWith(ZExt, Src);
591 if (NewInsts.count(Src) && isa<TruncInst>(Src)) {
592 auto *Trunc = cast<TruncInst>(Src);
593 assert(Trunc->getOperand(0)->getType() == ExtTy &&
594 "expected inserted trunc to be operating on i32");
595 ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
599 for (
auto *
I : InstsToRemove) {
601 I->dropAllReferences();
602 I->eraseFromParent();
606 void IRPromoter::ConvertTruncs() {
610 for (
auto *V : Visited) {
611 if (!isa<TruncInst>(V) || Sources.count(V))
614 auto *Trunc = cast<TruncInst>(V);
616 IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
617 IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
624 if (
auto *
I = dyn_cast<Instruction>(Masked))
627 ReplaceAllUsersOfWith(Trunc, Masked);
631 void IRPromoter::Mutate() {
633 << PromotedWidth <<
"-bits\n");
636 for (
auto *
I : Sinks) {
637 if (
auto *Call = dyn_cast<CallInst>(
I)) {
639 TruncTysMap[
Call].push_back(
Arg->getType());
640 }
else if (
auto *Switch = dyn_cast<SwitchInst>(
I))
641 TruncTysMap[
I].push_back(
Switch->getCondition()->getType());
643 for (
unsigned i = 0;
i <
I->getNumOperands(); ++
i)
644 TruncTysMap[
I].push_back(
I->getOperand(
i)->getType());
647 for (
auto *V : Visited) {
648 if (!isa<TruncInst>(V) || Sources.count(V))
650 auto *Trunc = cast<TruncInst>(V);
651 TruncTysMap[Trunc].push_back(Trunc->getDestTy());
683 if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->
getBitWidth() == 1 ||
684 cast<IntegerType>(Ty)->
getBitWidth() > RegisterBitWidth)
687 return LessOrEqualTypeSize(V);
694 bool TypePromotion::isSupportedValue(
Value *V) {
695 if (
auto *
I = dyn_cast<Instruction>(V)) {
696 switch (
I->getOpcode()) {
700 case Instruction::GetElementPtr:
702 case Instruction::Br:
703 case Instruction::Switch:
705 case Instruction::PHI:
709 case Instruction::Trunc:
710 case Instruction::BitCast:
712 case Instruction::ZExt:
714 case Instruction::ICmp:
719 if (isa<PointerType>(
I->getOperand(0)->getType()))
721 return EqualTypeSize(
I->getOperand(0));
726 auto *
Call = cast<CallInst>(
I);
728 Call->hasRetAttr(Attribute::AttrKind::ZExt);
731 }
else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
733 }
else if (isa<Argument>(V))
736 return isa<BasicBlock>(V);
743 auto *
I = dyn_cast<Instruction>(V);
747 if (SafeToPromote.count(
I))
751 SafeToPromote.insert(
I);
757 bool TypePromotion::TryToPromote(
Value *V,
unsigned PromotedWidth) {
760 SafeToPromote.clear();
766 LLVM_DEBUG(
dbgs() <<
"IR Promotion: TryToPromote: " << *V <<
", from "
767 <<
TypeSize <<
" bits to " << PromotedWidth <<
"\n");
778 auto AddLegalInst = [&](
Value *V) {
779 if (CurrentVisited.
count(V))
784 if (isa<GetElementPtrInst>(V))
788 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Can't handle: " << *V <<
"\n");
797 while (!WorkList.
empty()) {
799 if (CurrentVisited.
count(V))
803 if (!isa<Instruction>(V) && !isSource(V))
810 if (AllVisited.count(V))
814 AllVisited.insert(V);
818 Sinks.
insert(cast<Instruction>(V));
823 if (!isSink(V) && !isSource(V)) {
824 if (
auto *
I = dyn_cast<Instruction>(V)) {
826 for (
auto &U :
I->operands()) {
827 if (!AddLegalInst(U))
835 if (isSource(V) || shouldPromote(V)) {
837 if (!AddLegalInst(U.getUser()))
844 dbgs() <<
"IR Promotion: Visited nodes:\n";
845 for (
auto *
I : CurrentVisited)
849 unsigned ToPromote = 0;
850 unsigned NonFreeArgs = 0;
852 for (
auto *V : CurrentVisited) {
853 if (
auto *
I = dyn_cast<Instruction>(V))
856 if (Sources.
count(V)) {
857 if (
auto *
Arg = dyn_cast<Argument>(V))
858 if (!
Arg->hasZExtAttr() && !
Arg->hasSExtAttr())
863 if (Sinks.
count(cast<Instruction>(V)))
870 if (ToPromote < 2 || (Blocks.
size() == 1 && (NonFreeArgs > SafeWrap.size())))
873 IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
883 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Running on " <<
F.getName() <<
"\n");
885 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
890 SafeToPromote.clear();
892 bool MadeChange =
false;
898 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
901 Ctx = &
F.getParent()->getContext();
906 if (AllVisited.count(&
I))
909 if (!isa<ICmpInst>(&
I))
912 auto *ICmp = cast<ICmpInst>(&
I);
914 if (ICmp->isSigned() || !isa<IntegerType>(ICmp->getOperand(0)->getType()))
917 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Searching from: " << *ICmp <<
"\n");
919 for (
auto &
Op : ICmp->operands()) {
920 if (
auto *
I = dyn_cast<Instruction>(
Op)) {
930 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Couldn't find target register "
931 <<
"for promoted type\n");
943 SafeToPromote.clear();
952 char TypePromotion::
ID = 0;