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) {
137class TypePromotionImpl {
141 unsigned RegisterBitWidth = 0;
148 bool EqualTypeSize(
Value *V);
150 bool LessOrEqualTypeSize(
Value *V);
152 bool GreaterThanTypeSize(
Value *V);
154 bool LessThanTypeSize(
Value *V);
156 bool isSource(
Value *V);
158 bool isSink(
Value *V);
161 bool shouldPromote(
Value *V);
169 bool isSupportedValue(
Value *V);
173 bool TryToPromote(
Value *V,
unsigned PromotedWidth,
const LoopInfo &LI);
202 unsigned Opc =
I->getOpcode();
203 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
204 Opc == Instruction::SRem || Opc == Instruction::SExt;
207bool TypePromotionImpl::EqualTypeSize(
Value *V) {
208 return V->getType()->getScalarSizeInBits() ==
TypeSize;
211bool TypePromotionImpl::LessOrEqualTypeSize(
Value *V) {
212 return V->getType()->getScalarSizeInBits() <=
TypeSize;
215bool TypePromotionImpl::GreaterThanTypeSize(
Value *V) {
216 return V->getType()->getScalarSizeInBits() >
TypeSize;
219bool TypePromotionImpl::LessThanTypeSize(
Value *V) {
220 return V->getType()->getScalarSizeInBits() <
TypeSize;
230bool TypePromotionImpl::isSource(
Value *V) {
231 if (!isa<IntegerType>(
V->getType()))
235 if (isa<Argument>(V))
237 else if (isa<LoadInst>(V))
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);
249bool TypePromotionImpl::isSink(
Value *V) {
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));
271 return isa<CallInst>(V);
329 unsigned Opc =
I->getOpcode();
330 if (Opc != Instruction::Add && Opc != Instruction::Sub)
333 if (!
I->hasOneUse() || !isa<ICmpInst>(*
I->user_begin()) ||
334 !isa<ConstantInt>(
I->getOperand(1)))
338 auto *CI = cast<ICmpInst>(*
I->user_begin());
339 if (CI->isSigned() || CI->isEquality())
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;
351 APInt OverflowConst = cast<ConstantInt>(
I->getOperand(1))->getValue();
352 if (Opc == Instruction::Sub)
353 OverflowConst = -OverflowConst;
363 APInt NewConst = -((-OverflowConst).zext(64));
370 if (OverflowConst == 0 || OverflowConst.
ugt(ICmpConst)) {
372 <<
"const of " << *
I <<
"\n");
377 <<
"const of " << *
I <<
" and " << *CI <<
"\n");
382bool 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);
436void 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());
446 Value *ZExt = Builder.CreateZExt(V, ExtTy);
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)) {
474void 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)) {
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));
506 NewConst =
Const->getValue().zext(PromotedWidth);
508 NewConst =
Const->getValue().zext(PromotedWidth);
510 I->setOperand(i, ConstantInt::get(
Const->getContext(), NewConst));
511 }
else if (isa<UndefValue>(
Op))
512 I->setOperand(i, ConstantInt::get(ExtTy, 0));
516 if (!isa<ICmpInst>(
I) && !isa<SwitchInst>(
I)) {
517 I->mutateType(ExtTy);
523void IRPromoter::TruncateSinks() {
529 if (!isa<Instruction>(V) || !isa<IntegerType>(
V->getType()))
532 if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
535 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Creating " << *TruncTy <<
" Trunc for "
537 Builder.SetInsertPoint(cast<Instruction>(V));
538 auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
540 NewInsts.insert(Trunc);
546 for (
auto *
I : Sinks) {
550 if (
auto *Call = dyn_cast<CallInst>(
I)) {
551 for (
unsigned i = 0; i <
Call->arg_size(); ++i) {
555 Trunc->moveBefore(Call);
556 Call->setArgOperand(i, Trunc);
563 if (
auto *Switch = dyn_cast<SwitchInst>(
I)) {
566 Trunc->moveBefore(Switch);
567 Switch->setCondition(Trunc);
578 if (
auto ZExt = dyn_cast<ZExtInst>(
I))
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);
587 I->setOperand(i, Trunc);
593void IRPromoter::Cleanup() {
597 for (
auto *V : Visited) {
598 if (!isa<ZExtInst>(V))
601 auto ZExt = cast<ZExtInst>(V);
602 if (ZExt->getDestTy() != ExtTy)
605 Value *Src = ZExt->getOperand(0);
606 if (ZExt->getSrcTy() == ZExt->getDestTy()) {
607 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Removing unnecessary cast: " << *ZExt
609 ReplaceAllUsersOfWith(ZExt, Src);
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));
623 for (
auto *
I : InstsToRemove) {
625 I->dropAllReferences();
629void IRPromoter::ConvertTruncs() {
633 for (
auto *V : Visited) {
634 if (!isa<TruncInst>(V) || Sources.count(V))
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]);
645 Value *
Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
649 if (
auto *
I = dyn_cast<Instruction>(
Masked))
652 ReplaceAllUsersOfWith(Trunc,
Masked);
656void IRPromoter::Mutate() {
658 << PromotedWidth <<
"-bits\n");
661 for (
auto *
I : Sinks) {
662 if (
auto *Call = dyn_cast<CallInst>(
I)) {
665 }
else if (
auto *Switch = dyn_cast<SwitchInst>(
I))
666 TruncTysMap[
I].push_back(
Switch->getCondition()->getType());
668 for (
unsigned i = 0; i <
I->getNumOperands(); ++i)
669 TruncTysMap[
I].push_back(
I->getOperand(i)->getType());
672 for (
auto *V : Visited) {
673 if (!isa<TruncInst>(V) || Sources.count(V))
675 auto *Trunc = cast<TruncInst>(V);
676 TruncTysMap[Trunc].push_back(Trunc->getDestTy());
701bool TypePromotionImpl::isSupportedType(
Value *V) {
702 Type *Ty =
V->getType();
708 if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->
getBitWidth() == 1 ||
709 cast<IntegerType>(Ty)->
getBitWidth() > RegisterBitWidth)
712 return LessOrEqualTypeSize(V);
719bool TypePromotionImpl::isSupportedValue(
Value *V) {
720 if (
auto *
I = dyn_cast<Instruction>(V)) {
721 switch (
I->getOpcode()) {
725 case Instruction::GetElementPtr:
726 case Instruction::Store:
727 case Instruction::Br:
728 case Instruction::Switch:
730 case Instruction::PHI:
731 case Instruction::Select:
732 case Instruction::Ret:
733 case Instruction::Load:
734 case Instruction::Trunc:
736 case Instruction::BitCast:
737 return I->getOperand(0)->getType() ==
I->getType();
738 case Instruction::ZExt:
740 case Instruction::ICmp:
745 if (isa<PointerType>(
I->getOperand(0)->getType()))
747 return EqualTypeSize(
I->getOperand(0));
748 case Instruction::Call: {
752 auto *
Call = cast<CallInst>(
I);
754 Call->hasRetAttr(Attribute::AttrKind::ZExt);
757 }
else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
759 }
else if (isa<Argument>(V))
762 return isa<BasicBlock>(V);
768bool TypePromotionImpl::isLegalToPromote(
Value *V) {
769 auto *
I = dyn_cast<Instruction>(V);
773 if (SafeToPromote.count(
I))
777 SafeToPromote.insert(
I);
783bool TypePromotionImpl::TryToPromote(
Value *V,
unsigned PromotedWidth,
785 Type *OrigTy =
V->getType();
787 SafeToPromote.clear();
793 LLVM_DEBUG(
dbgs() <<
"IR Promotion: TryToPromote: " << *V <<
", from "
794 <<
TypeSize <<
" bits to " << PromotedWidth <<
"\n");
805 auto AddLegalInst = [&](
Value *
V) {
806 if (CurrentVisited.
count(V))
811 if (isa<GetElementPtrInst>(V))
815 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Can't handle: " << *V <<
"\n");
824 while (!WorkList.
empty()) {
826 if (CurrentVisited.
count(V))
830 if (!isa<Instruction>(V) && !isSource(V))
837 if (AllVisited.count(V))
841 AllVisited.insert(V);
845 Sinks.
insert(cast<Instruction>(V));
850 if (!isSink(V) && !isSource(V)) {
851 if (
auto *
I = dyn_cast<Instruction>(V)) {
853 for (
auto &U :
I->operands()) {
854 if (!AddLegalInst(U))
862 if (isSource(V) || shouldPromote(V)) {
863 for (
Use &U :
V->uses()) {
864 if (!AddLegalInst(
U.getUser()))
871 dbgs() <<
"IR Promotion: Visited nodes:\n";
872 for (
auto *
I : CurrentVisited)
876 unsigned ToPromote = 0;
877 unsigned NonFreeArgs = 0;
878 unsigned NonLoopSources = 0, LoopSinks = 0;
880 for (
auto *CV : CurrentVisited) {
881 if (
auto *
I = dyn_cast<Instruction>(CV))
884 if (Sources.
count(CV)) {
885 if (
auto *Arg = dyn_cast<Argument>(CV))
886 if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
888 if (!isa<Instruction>(CV) ||
894 if (isa<PHINode>(CV))
896 if (LI.
getLoopFor(cast<Instruction>(CV)->getParent()))
898 if (Sinks.
count(cast<Instruction>(CV)))
905 if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&
906 (ToPromote < 2 || (
Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))
909 IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
910 SafeWrap, InstsToRemove);
921 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Running on " <<
F.getName() <<
"\n");
924 SafeToPromote.clear();
926 bool MadeChange =
false;
932 Ctx = &
F.getContext();
937 if (!isa<IntegerType>(
I->getType()))
940 EVT SrcVT = TLI->getValueType(
DL,
I->getType());
944 if (TLI->getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger)
947 EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT);
948 if (TLI->isSExtCheaperThanZExt(SrcVT, PromotedVT))
951 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Couldn't find target register "
952 <<
"for promoted type\n");
960 auto BBIsInLoop = [&](
BasicBlock *BB) ->
bool {
969 if (AllVisited.count(&
I))
972 if (isa<ZExtInst>(&
I) && isa<PHINode>(
I.getOperand(0)) &&
973 isa<IntegerType>(
I.getType()) && BBIsInLoop(&BB)) {
975 << *
I.getOperand(0) <<
"\n");
976 EVT ZExtVT = TLI->getValueType(
DL,
I.getType());
979 if (RegisterBitWidth < PromoteWidth) {
981 <<
"register for ZExt type\n");
984 MadeChange |= TryToPromote(Phi, PromoteWidth, LI);
985 }
else if (
auto *ICmp = dyn_cast<ICmpInst>(&
I)) {
988 if (ICmp->isSigned())
991 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Searching from: " << *ICmp <<
"\n");
993 for (
auto &
Op : ICmp->operands()) {
994 if (
auto *OpI = dyn_cast<Instruction>(
Op)) {
995 if (
auto PromotedWidth = GetPromoteWidth(OpI)) {
996 MadeChange |= TryToPromote(OpI, PromotedWidth, LI);
1003 if (!InstsToRemove.empty()) {
1004 for (
auto *
I : InstsToRemove)
1005 I->eraseFromParent();
1006 InstsToRemove.clear();
1011 SafeToPromote.clear();
1023char TypePromotionLegacy::
ID = 0;
1026 if (skipFunction(
F))
1029 auto &TPC = getAnalysis<TargetPassConfig>();
1031 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1032 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1034 TypePromotionImpl TP;
1035 return TP.run(
F,
TM,
TTI, LI);
1039 return new TypePromotionLegacy();
1046 TypePromotionImpl TP;
1048 bool Changed = TP.run(
F,
TM,
TTI, LI);
static bool isSupportedType(const DataLayout &DL, const ARMTargetLowering &TLI, Type *T)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
DenseMap< Block *, BlockRelaxAux > Blocks
static bool runOnFunction(Function &F, bool PostInlining)
static const HTTPClientCleanup Cleanup
iv Induction Variable Users
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Class for arbitrary precision integers.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
int64_t getSExtValue() const
Get sign extended value.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
LLVM Basic Block Representation.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
Represents analyses that only rely on functions' control flow.
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const BasicBlock & front() const
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
A vector that has set insertion semantics.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Target-Independent Code Generator Pass Configuration Options.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetLowering * getTargetLowering() const
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
constexpr ScalarTy getFixedValue() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
bool isLegalToPromote(const CallBase &CB, Function *Callee, const char **FailureReason=nullptr)
Return true if the given indirect call site can be made to call Callee.
FunctionPass * createTypePromotionLegacyPass()
Create IR Type Promotion pass.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVMAttributeRef wrap(Attribute Attr)
bool isSimple() const
Test if the given EVT is simple (as opposed to being extended).
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
uint64_t getFixedSizeInBits() const
Return the size of the specified fixed width value type in bits.