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 {
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;
206bool TypePromotionImpl::EqualTypeSize(
Value *V) {
207 return V->getType()->getScalarSizeInBits() ==
TypeSize;
210bool TypePromotionImpl::LessOrEqualTypeSize(
Value *V) {
211 return V->getType()->getScalarSizeInBits() <=
TypeSize;
214bool TypePromotionImpl::GreaterThanTypeSize(
Value *V) {
215 return V->getType()->getScalarSizeInBits() >
TypeSize;
218bool TypePromotionImpl::LessThanTypeSize(
Value *V) {
219 return V->getType()->getScalarSizeInBits() <
TypeSize;
229bool 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);
250bool 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();
337 if (Opc != Instruction::Add && Opc != Instruction::Sub)
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");
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());
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)) {
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);
515void 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);
585void IRPromoter::Cleanup() {
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();
621void 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]);
637 Value *Masked =
Builder.CreateAnd(Trunc->getOperand(0), Mask);
639 Masked =
Builder.CreateTrunc(Masked, ExtTy);
641 if (
auto *
I = dyn_cast<Instruction>(Masked))
644 ReplaceAllUsersOfWith(Trunc, Masked);
648void 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());
693bool TypePromotionImpl::isSupportedType(
Value *V) {
694 Type *Ty =
V->getType();
700 if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->
getBitWidth() == 1 ||
701 cast<IntegerType>(Ty)->
getBitWidth() > RegisterBitWidth)
704 return LessOrEqualTypeSize(V);
711bool TypePromotionImpl::isSupportedValue(
Value *V) {
712 if (
auto *
I = dyn_cast<Instruction>(V)) {
713 switch (
I->getOpcode()) {
717 case Instruction::GetElementPtr:
718 case Instruction::Store:
719 case Instruction::Br:
720 case Instruction::Switch:
722 case Instruction::PHI:
723 case Instruction::Select:
724 case Instruction::Ret:
725 case Instruction::Load:
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));
739 case Instruction::Call: {
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);
759bool TypePromotionImpl::isLegalToPromote(
Value *V) {
760 auto *
I = dyn_cast<Instruction>(V);
764 if (SafeToPromote.count(
I))
768 SafeToPromote.insert(
I);
774bool TypePromotionImpl::TryToPromote(
Value *V,
unsigned PromotedWidth,
776 Type *OrigTy =
V->getType();
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)) {
854 for (
Use &U :
V->uses()) {
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()))
935 if (TLI->
getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger)
940 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Couldn't find target register "
941 <<
"for promoted type\n");
949 auto BBIsInLoop = [&](
BasicBlock *BB) ->
bool {
958 if (AllVisited.count(&
I))
961 if (isa<ZExtInst>(&
I) && isa<PHINode>(
I.getOperand(0)) &&
962 isa<IntegerType>(
I.getType()) && BBIsInLoop(&BB)) {
964 << *
I.getOperand(0) <<
"\n");
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();
1012char 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);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static bool isSupportedType(const DataLayout &DL, const ARMTargetLowering &TLI, Type *T)
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 sgt(const APInt &RHS) const
Signed greater than comparison.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
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...
Represents analyses that only rely on functions' control flow.
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
const APInt & getValue() const
Return the constant as an APInt value reference.
This is an important base class in LLVM.
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.
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.
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 insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
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.
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
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.
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.