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 (
auto *Call = dyn_cast<CallInst>(V))
239 return Call->hasRetAttr(Attribute::AttrKind::ZExt);
240 else if (
auto *Trunc = dyn_cast<TruncInst>(V))
241 return EqualTypeSize(Trunc);
248bool TypePromotionImpl::isSink(
Value *V) {
259 if (
auto *Store = dyn_cast<StoreInst>(V))
260 return LessOrEqualTypeSize(
Store->getValueOperand());
261 if (
auto *Return = dyn_cast<ReturnInst>(V))
262 return LessOrEqualTypeSize(
Return->getReturnValue());
263 if (
auto *ZExt = dyn_cast<ZExtInst>(V))
264 return GreaterThanTypeSize(ZExt);
265 if (
auto *Switch = dyn_cast<SwitchInst>(V))
266 return LessThanTypeSize(
Switch->getCondition());
267 if (
auto *ICmp = dyn_cast<ICmpInst>(V))
268 return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
270 return isa<CallInst>(V);
334 unsigned Opc =
I->getOpcode();
335 if (Opc != Instruction::Add && Opc != Instruction::Sub)
338 if (!
I->hasOneUse() || !isa<ICmpInst>(*
I->user_begin()) ||
339 !isa<ConstantInt>(
I->getOperand(1)))
343 auto *CI = cast<ICmpInst>(*
I->user_begin());
344 if (CI->isSigned() || CI->isEquality())
348 if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
349 ICmpConstant =
Const;
350 else if (
auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
351 ICmpConstant =
Const;
356 APInt OverflowConst = cast<ConstantInt>(
I->getOperand(1))->getValue();
357 if (Opc == Instruction::Sub)
358 OverflowConst = -OverflowConst;
365 if (OverflowConst.
sgt(ICmpConst)) {
366 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
367 <<
"const of " << *
I <<
"\n");
371 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Allowing safe overflow for sext "
372 <<
"const of " << *
I <<
" and " << *CI <<
"\n");
380bool TypePromotionImpl::shouldPromote(
Value *V) {
381 if (!isa<IntegerType>(
V->getType()) || isSink(V))
387 auto *
I = dyn_cast<Instruction>(V);
391 if (isa<ICmpInst>(
I))
403 if (!isa<OverflowingBinaryOperator>(
I))
406 return I->hasNoUnsignedWrap();
412 bool ReplacedAll =
true;
418 auto *
User = cast<Instruction>(
U.getUser());
419 if (InstTo &&
User->isIdenticalTo(InstTo)) {
426 for (
auto *U :
Users)
427 U->replaceUsesOfWith(
From, To);
430 if (
auto *
I = dyn_cast<Instruction>(
From))
431 InstsToRemove.insert(
I);
434void IRPromoter::ExtendSources() {
438 assert(
V->getType() != ExtTy &&
"zext already extends to i32");
439 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Inserting ZExt for " << *V <<
"\n");
440 Builder.SetInsertPoint(InsertPt);
441 if (
auto *
I = dyn_cast<Instruction>(V))
442 Builder.SetCurrentDebugLocation(
I->getDebugLoc());
444 Value *ZExt = Builder.CreateZExt(V, ExtTy);
445 if (
auto *
I = dyn_cast<Instruction>(ZExt)) {
446 if (isa<Argument>(V))
447 I->moveBefore(InsertPt);
449 I->moveAfter(InsertPt);
453 ReplaceAllUsersOfWith(V, ZExt);
458 for (
auto *V : Sources) {
460 if (
auto *
I = dyn_cast<Instruction>(V))
462 else if (
auto *Arg = dyn_cast<Argument>(V)) {
472void IRPromoter::PromoteTree() {
477 for (
auto *V : Visited) {
478 if (Sources.count(V))
481 auto *
I = cast<Instruction>(V);
485 for (
unsigned i = 0, e =
I->getNumOperands(); i < e; ++i) {
487 if ((
Op->getType() == ExtTy) || !isa<IntegerType>(
Op->getType()))
490 if (
auto *Const = dyn_cast<ConstantInt>(
Op)) {
497 (SafeWrap.contains(
I) &&
498 (
I->getOpcode() == Instruction::ICmp || i == 1) &&
499 I->getOpcode() != Instruction::Sub)
500 ?
Const->getValue().sext(PromotedWidth)
501 :
Const->getValue().zext(PromotedWidth));
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);
630 Builder.SetInsertPoint(Trunc);
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)) {
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:
728 case Instruction::BitCast:
729 return I->getOperand(0)->getType() ==
I->getType();
730 case Instruction::ZExt:
732 case Instruction::ICmp:
737 if (isa<PointerType>(
I->getOperand(0)->getType()))
739 return EqualTypeSize(
I->getOperand(0));
740 case Instruction::Call: {
744 auto *
Call = cast<CallInst>(
I);
746 Call->hasRetAttr(Attribute::AttrKind::ZExt);
749 }
else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
751 }
else if (isa<Argument>(V))
754 return isa<BasicBlock>(V);
760bool TypePromotionImpl::isLegalToPromote(
Value *V) {
761 auto *
I = dyn_cast<Instruction>(V);
765 if (SafeToPromote.count(
I))
769 SafeToPromote.insert(
I);
775bool TypePromotionImpl::TryToPromote(
Value *V,
unsigned PromotedWidth,
777 Type *OrigTy =
V->getType();
779 SafeToPromote.clear();
785 LLVM_DEBUG(
dbgs() <<
"IR Promotion: TryToPromote: " << *V <<
", from "
786 <<
TypeSize <<
" bits to " << PromotedWidth <<
"\n");
797 auto AddLegalInst = [&](
Value *
V) {
798 if (CurrentVisited.
count(V))
803 if (isa<GetElementPtrInst>(V))
807 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Can't handle: " << *V <<
"\n");
816 while (!WorkList.
empty()) {
818 if (CurrentVisited.
count(V))
822 if (!isa<Instruction>(V) && !isSource(V))
829 if (AllVisited.count(V))
833 AllVisited.insert(V);
837 Sinks.
insert(cast<Instruction>(V));
842 if (!isSink(V) && !isSource(V)) {
843 if (
auto *
I = dyn_cast<Instruction>(V)) {
845 for (
auto &U :
I->operands()) {
846 if (!AddLegalInst(U))
854 if (isSource(V) || shouldPromote(V)) {
855 for (
Use &U :
V->uses()) {
856 if (!AddLegalInst(
U.getUser()))
863 dbgs() <<
"IR Promotion: Visited nodes:\n";
864 for (
auto *
I : CurrentVisited)
868 unsigned ToPromote = 0;
869 unsigned NonFreeArgs = 0;
870 unsigned NonLoopSources = 0, LoopSinks = 0;
872 for (
auto *CV : CurrentVisited) {
873 if (
auto *
I = dyn_cast<Instruction>(CV))
876 if (Sources.
count(CV)) {
877 if (
auto *Arg = dyn_cast<Argument>(CV))
878 if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
880 if (!isa<Instruction>(CV) ||
886 if (isa<PHINode>(CV))
888 if (LI.
getLoopFor(cast<Instruction>(CV)->getParent()))
890 if (Sinks.
count(cast<Instruction>(CV)))
897 if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&
898 (ToPromote < 2 || (
Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))
901 IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
902 SafeWrap, InstsToRemove);
913 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Running on " <<
F.getName() <<
"\n");
916 SafeToPromote.clear();
918 bool MadeChange =
false;
924 Ctx = &
F.getParent()->getContext();
929 if (!isa<IntegerType>(
I->getType()))
936 if (TLI->
getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger)
941 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Couldn't find target register "
942 <<
"for promoted type\n");
950 auto BBIsInLoop = [&](
BasicBlock *BB) ->
bool {
959 if (AllVisited.count(&
I))
962 if (isa<ZExtInst>(&
I) && isa<PHINode>(
I.getOperand(0)) &&
963 isa<IntegerType>(
I.getType()) && BBIsInLoop(&BB)) {
965 << *
I.getOperand(0) <<
"\n");
969 if (RegisterBitWidth < PromoteWidth) {
971 <<
"register for ZExt type\n");
974 MadeChange |= TryToPromote(Phi, PromoteWidth, LI);
975 }
else if (
auto *ICmp = dyn_cast<ICmpInst>(&
I)) {
978 if (ICmp->isSigned())
981 LLVM_DEBUG(
dbgs() <<
"IR Promotion: Searching from: " << *ICmp <<
"\n");
983 for (
auto &
Op : ICmp->operands()) {
984 if (
auto *OpI = dyn_cast<Instruction>(
Op)) {
985 if (
auto PromotedWidth = GetPromoteWidth(OpI)) {
986 MadeChange |= TryToPromote(OpI, PromotedWidth, LI);
993 if (!InstsToRemove.empty()) {
994 for (
auto *
I : InstsToRemove)
995 I->eraseFromParent();
996 InstsToRemove.clear();
1001 SafeToPromote.clear();
1013char TypePromotionLegacy::
ID = 0;
1016 if (skipFunction(
F))
1019 auto &TPC = getAnalysis<TargetPassConfig>();
1021 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1022 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1024 TypePromotionImpl TP;
1025 return TP.run(
F,
TM,
TTI, LI);
1029 return new TypePromotionLegacy();
1036 TypePromotionImpl TP;
1038 bool Changed = TP.run(
F,
TM,
TTI, LI);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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...
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.
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.
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.
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.
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.
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.