42 #define DEBUG_TYPE "type-promotion"
43 #define PASS_NAME "Type Promotion"
49 cl::desc(
"Disable type promotion pass"));
106 unsigned PromotedWidth = 0;
118 void ExtendSources();
119 void ConvertTruncs();
121 void TruncateSinks();
129 : Ctx(
C), PromotedWidth(
Width), Visited(visited), Sources(sources),
130 Sinks(sinks), SafeWrap(
wrap), InstsToRemove(instsToRemove) {
137 class TypePromotionImpl {
140 unsigned RegisterBitWidth = 0;
147 bool EqualTypeSize(
Value *V);
149 bool LessOrEqualTypeSize(
Value *V);
151 bool GreaterThanTypeSize(
Value *V);
153 bool LessThanTypeSize(
Value *V);
155 bool isSource(
Value *V);
157 bool isSink(
Value *V);
160 bool shouldPromote(
Value *V);
168 bool isSupportedValue(
Value *V);
172 bool TryToPromote(
Value *V,
unsigned PromotedWidth,
const LoopInfo &LI);
201 unsigned Opc =
I->getOpcode();
202 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
203 Opc == Instruction::SRem || Opc == Instruction::SExt;
206 bool TypePromotionImpl::EqualTypeSize(
Value *V) {
210 bool TypePromotionImpl::LessOrEqualTypeSize(
Value *V) {
214 bool TypePromotionImpl::GreaterThanTypeSize(
Value *V) {
218 bool TypePromotionImpl::LessThanTypeSize(
Value *V) {
229 bool TypePromotionImpl::isSource(
Value *V) {
230 if (!isa<IntegerType>(V->
getType()))
234 if (isa<Argument>(V))
236 else if (isa<LoadInst>(V))
238 else if (isa<BitCastInst>(V))
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);
250 bool TypePromotionImpl::isSink(
Value *V) {
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));
272 return isa<CallInst>(V);
336 unsigned Opc =
I->getOpcode();
340 if (!
I->hasOneUse() || !isa<ICmpInst>(*
I->user_begin()) ||
341 !isa<ConstantInt>(
I->getOperand(1)))
345 auto *CI = cast<ICmpInst>(*
I->user_begin());
346 if (CI->isSigned() || CI->isEquality())
350 if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
351 ICmpConstant =
Const;
352 else if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
353 ICmpConstant =
Const;
358 APInt OverflowConst = cast<ConstantInt>(
I->getOperand(1))->getValue();
359 if (Opc == Instruction::Sub)
360 OverflowConst = -OverflowConst;
367 if (OverflowConst.
sgt(ICmpConst)) {
368 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
369 <<
"const of " << *
I <<
"\n");
373 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
374 <<
"const of " << *
I <<
" and " << *CI <<
"\n");
382 bool TypePromotionImpl::shouldPromote(
Value *V) {
383 if (!isa<IntegerType>(V->
getType()) || isSink(V))
389 auto *
I = dyn_cast<Instruction>(V);
393 if (isa<ICmpInst>(
I))
405 if (!isa<OverflowingBinaryOperator>(
I))
408 return I->hasNoUnsignedWrap();
414 bool ReplacedAll =
true;
420 auto *
User = cast<Instruction>(U.getUser());
421 if (InstTo &&
User->isIdenticalTo(InstTo)) {
428 for (
auto *U :
Users)
429 U->replaceUsesOfWith(
From, To);
432 if (
auto *
I = dyn_cast<Instruction>(
From))
433 InstsToRemove.insert(
I);
436 void IRPromoter::ExtendSources() {
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());
447 if (
auto *
I = dyn_cast<Instruction>(ZExt)) {
448 if (isa<Argument>(V))
449 I->moveBefore(InsertPt);
451 I->moveAfter(InsertPt);
455 ReplaceAllUsersOfWith(V, ZExt);
460 for (
auto *V : Sources) {
462 if (
auto *
I = dyn_cast<Instruction>(V))
464 else if (
auto *
Arg = dyn_cast<Argument>(V)) {
466 InsertZExt(
Arg, &*
BB.getFirstInsertionPt());
474 void IRPromoter::PromoteTree() {
479 for (
auto *V : Visited) {
480 if (Sources.count(V))
483 auto *
I = cast<Instruction>(V);
487 for (
unsigned i = 0,
e =
I->getNumOperands();
i <
e; ++
i) {
489 if ((
Op->getType() == ExtTy) || !isa<IntegerType>(
Op->getType()))
492 if (
auto *Const = dyn_cast<ConstantInt>(
Op)) {
497 Constant *NewConst = (SafeWrap.contains(
I) &&
498 (
I->getOpcode() == Instruction::ICmp ||
i == 1) &&
499 I->getOpcode() != Instruction::Sub)
502 I->setOperand(
i, NewConst);
503 }
else if (isa<UndefValue>(
Op))
508 if (!isa<ICmpInst>(
I) && !isa<SwitchInst>(
I)) {
509 I->mutateType(ExtTy);
515 void IRPromoter::TruncateSinks() {
521 if (!isa<Instruction>(V) || !isa<IntegerType>(V->
getType()))
524 if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
527 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Creating " << *TruncTy <<
" Trunc for "
529 Builder.SetInsertPoint(cast<Instruction>(V));
530 auto *Trunc = dyn_cast<Instruction>(
Builder.CreateTrunc(V, TruncTy));
532 NewInsts.insert(Trunc);
538 for (
auto *
I : Sinks) {
542 if (
auto *Call = dyn_cast<CallInst>(
I)) {
543 for (
unsigned i = 0;
i <
Call->arg_size(); ++
i) {
547 Trunc->moveBefore(Call);
548 Call->setArgOperand(
i, Trunc);
555 if (
auto *Switch = dyn_cast<SwitchInst>(
I)) {
558 Trunc->moveBefore(Switch);
559 Switch->setCondition(Trunc);
570 if (
auto ZExt = dyn_cast<ZExtInst>(
I))
575 for (
unsigned i = 0;
i <
I->getNumOperands(); ++
i) {
576 Type *Ty = TruncTysMap[
I][
i];
577 if (
Instruction *Trunc = InsertTrunc(
I->getOperand(
i), Ty)) {
578 Trunc->moveBefore(
I);
579 I->setOperand(
i, Trunc);
589 for (
auto *V : Visited) {
590 if (!isa<ZExtInst>(V))
593 auto ZExt = cast<ZExtInst>(V);
594 if (ZExt->getDestTy() != ExtTy)
597 Value *Src = ZExt->getOperand(0);
598 if (ZExt->getSrcTy() == ZExt->getDestTy()) {
599 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Removing unnecessary cast: " << *ZExt
601 ReplaceAllUsersOfWith(ZExt, Src);
607 if (NewInsts.count(Src) && isa<TruncInst>(Src)) {
608 auto *Trunc = cast<TruncInst>(Src);
609 assert(Trunc->getOperand(0)->getType() == ExtTy &&
610 "expected inserted trunc to be operating on i32");
611 ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
615 for (
auto *
I : InstsToRemove) {
617 I->dropAllReferences();
621 void IRPromoter::ConvertTruncs() {
625 for (
auto *V : Visited) {
626 if (!isa<TruncInst>(V) || Sources.count(V))
629 auto *Trunc = cast<TruncInst>(V);
631 IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
632 IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
639 Masked =
Builder.CreateTrunc(Masked, ExtTy);
641 if (
auto *
I = dyn_cast<Instruction>(Masked))
644 ReplaceAllUsersOfWith(Trunc, Masked);
648 void IRPromoter::Mutate() {
650 << PromotedWidth <<
"-bits\n");
653 for (
auto *
I : Sinks) {
654 if (
auto *Call = dyn_cast<CallInst>(
I)) {
656 TruncTysMap[
Call].push_back(
Arg->getType());
657 }
else if (
auto *Switch = dyn_cast<SwitchInst>(
I))
658 TruncTysMap[
I].push_back(
Switch->getCondition()->getType());
660 for (
unsigned i = 0;
i <
I->getNumOperands(); ++
i)
661 TruncTysMap[
I].push_back(
I->getOperand(
i)->getType());
664 for (
auto *V : Visited) {
665 if (!isa<TruncInst>(V) || Sources.count(V))
667 auto *Trunc = cast<TruncInst>(V);
668 TruncTysMap[Trunc].push_back(Trunc->getDestTy());
700 if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->
getBitWidth() == 1 ||
701 cast<IntegerType>(Ty)->
getBitWidth() > RegisterBitWidth)
704 return LessOrEqualTypeSize(V);
711 bool TypePromotionImpl::isSupportedValue(
Value *V) {
712 if (
auto *
I = dyn_cast<Instruction>(V)) {
713 switch (
I->getOpcode()) {
717 case Instruction::GetElementPtr:
719 case Instruction::Br:
720 case Instruction::Switch:
726 case Instruction::Trunc:
727 case Instruction::BitCast:
729 case Instruction::ZExt:
731 case Instruction::ICmp:
736 if (isa<PointerType>(
I->getOperand(0)->getType()))
738 return EqualTypeSize(
I->getOperand(0));
743 auto *
Call = cast<CallInst>(
I);
745 Call->hasRetAttr(Attribute::AttrKind::ZExt);
748 }
else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
750 }
else if (isa<Argument>(V))
753 return isa<BasicBlock>(V);
760 auto *
I = dyn_cast<Instruction>(V);
764 if (SafeToPromote.count(
I))
768 SafeToPromote.insert(
I);
774 bool TypePromotionImpl::TryToPromote(
Value *V,
unsigned PromotedWidth,
778 SafeToPromote.clear();
784 LLVM_DEBUG(
dbgs() <<
"IR Promotion: TryToPromote: " << *V <<
", from "
785 <<
TypeSize <<
" bits to " << PromotedWidth <<
"\n");
796 auto AddLegalInst = [&](
Value *V) {
797 if (CurrentVisited.
count(V))
802 if (isa<GetElementPtrInst>(V))
806 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Can't handle: " << *V <<
"\n");
815 while (!WorkList.
empty()) {
817 if (CurrentVisited.
count(V))
821 if (!isa<Instruction>(V) && !isSource(V))
828 if (AllVisited.count(V))
832 AllVisited.insert(V);
836 Sinks.
insert(cast<Instruction>(V));
841 if (!isSink(V) && !isSource(V)) {
842 if (
auto *
I = dyn_cast<Instruction>(V)) {
844 for (
auto &U :
I->operands()) {
845 if (!AddLegalInst(U))
853 if (isSource(V) || shouldPromote(V)) {
855 if (!AddLegalInst(U.getUser()))
862 dbgs() <<
"IR Promotion: Visited nodes:\n";
863 for (
auto *
I : CurrentVisited)
867 unsigned ToPromote = 0;
868 unsigned NonFreeArgs = 0;
869 unsigned NonLoopSources = 0, LoopSinks = 0;
871 for (
auto *CV : CurrentVisited) {
872 if (
auto *
I = dyn_cast<Instruction>(CV))
875 if (Sources.
count(CV)) {
876 if (
auto *
Arg = dyn_cast<Argument>(CV))
877 if (!
Arg->hasZExtAttr() && !
Arg->hasSExtAttr())
879 if (!isa<Instruction>(CV) ||
885 if (isa<PHINode>(CV))
887 if (LI.
getLoopFor(cast<Instruction>(CV)->getParent()))
889 if (Sinks.
count(cast<Instruction>(CV)))
896 if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&
897 (ToPromote < 2 || (Blocks.
size() == 1 && NonFreeArgs > SafeWrap.size())))
900 IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
901 SafeWrap, InstsToRemove);
912 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Running on " <<
F.getName() <<
"\n");
915 SafeToPromote.clear();
917 bool MadeChange =
false;
923 Ctx = &
F.getParent()->getContext();
928 if (!isa<IntegerType>(
I->getType()))
940 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Couldn't find target register "
941 <<
"for promoted type\n");
958 if (AllVisited.count(&
I))
961 if (isa<ZExtInst>(&
I) && isa<PHINode>(
I.getOperand(0)) &&
962 isa<IntegerType>(
I.getType()) && BBIsInLoop(&
BB)) {
963 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Searching from: " <<
I.getOperand(0)
968 if (RegisterBitWidth < PromoteWidth) {
970 <<
"register for ZExt type\n");
973 MadeChange |= TryToPromote(Phi, PromoteWidth, LI);
974 }
else if (
auto *ICmp = dyn_cast<ICmpInst>(&
I)) {
977 if (ICmp->isSigned())
980 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Searching from: " << *ICmp <<
"\n");
982 for (
auto &
Op : ICmp->operands()) {
983 if (
auto *OpI = dyn_cast<Instruction>(
Op)) {
984 if (
auto PromotedWidth = GetPromoteWidth(OpI)) {
985 MadeChange |= TryToPromote(OpI, PromotedWidth, LI);
992 if (!InstsToRemove.empty()) {
993 for (
auto *
I : InstsToRemove)
994 I->eraseFromParent();
995 InstsToRemove.clear();
1000 SafeToPromote.clear();
1012 char TypePromotionLegacy::
ID = 0;
1015 if (skipFunction(
F))
1018 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1023 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1024 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1026 TypePromotionImpl TP;
1027 return TP.run(
F,
TM,
TTI, LI);
1031 return new TypePromotionLegacy();
1038 TypePromotionImpl TP;
1040 bool Changed = TP.run(
F,
TM,
TTI, LI);