27 #define DEBUG_TYPE "legalize-types" 33 void DAGTypeLegalizer::PerformExpensiveChecks() {
80 if (Node.getNodeId() ==
NewNode)
83 for (
unsigned i = 0, e = Node.getNumValues(); i != e; ++i) {
85 EVT VT = Res.getValueType();
88 auto ResId = (ValueToIdMap.count(Res)) ? ValueToIdMap[Res] : 0;
91 if (ResId && (ReplacedValues.find(ResId) != ReplacedValues.end())) {
96 if (UI.getUse().getResNo() == i)
98 "Remapped value has non-trivial use!");
102 auto NewValId = ReplacedValues[ResId];
103 auto I = ReplacedValues.find(NewValId);
104 while (
I != ReplacedValues.end()) {
105 NewValId =
I->second;
106 I = ReplacedValues.find(NewValId);
108 SDValue NewVal = getSDValue(NewValId);
111 "ReplacedValues maps to a new node!");
113 if (ResId && PromotedIntegers.find(ResId) != PromotedIntegers.end())
115 if (ResId && SoftenedFloats.find(ResId) != SoftenedFloats.end())
117 if (ResId && ScalarizedVectors.find(ResId) != ScalarizedVectors.end())
119 if (ResId && ExpandedIntegers.find(ResId) != ExpandedIntegers.end())
121 if (ResId && ExpandedFloats.find(ResId) != ExpandedFloats.end())
123 if (ResId && SplitVectors.find(ResId) != SplitVectors.end())
125 if (ResId && WidenedVectors.find(ResId) != WidenedVectors.end())
127 if (ResId && PromotedFloats.find(ResId) != PromotedFloats.end())
134 if ((Node.getNodeId() ==
NewNode && Mapped > 1) ||
135 (Node.getNodeId() !=
NewNode && Mapped != 0)) {
136 dbgs() <<
"Unprocessed value in a map!";
139 }
else if (isTypeLegal(VT) || IgnoreNodeResults(&Node)) {
141 dbgs() <<
"Value with legal type was transformed!";
149 isLegalInHWReg(VT))) {
150 dbgs() <<
"Processed value not in any map!";
152 }
else if (Mapped & (Mapped - 1)) {
153 dbgs() <<
"Value in multiple maps!";
160 dbgs() <<
" ReplacedValues";
162 dbgs() <<
" PromotedIntegers";
164 dbgs() <<
" SoftenedFloats";
166 dbgs() <<
" ScalarizedVectors";
168 dbgs() <<
" ExpandedIntegers";
170 dbgs() <<
" ExpandedFloats";
172 dbgs() <<
" SplitVectors";
174 dbgs() <<
" WidenedVectors";
176 dbgs() <<
" PromotedFloats";
184 for (
unsigned i = 0, e = NewNodes.
size(); i != e; ++i) {
188 assert(UI->getNodeId() ==
NewNode &&
"NewNode used by non-NewNode!");
196 bool Changed =
false;
212 if (Node.getNumOperands() == 0) {
213 AddToWorklist(&Node);
220 while (!Worklist.empty()) {
221 #ifndef EXPENSIVE_CHECKS 224 PerformExpensiveChecks();
226 SDNode *N = Worklist.back();
229 "Node should be ready if on worklist!");
232 if (IgnoreNodeResults(N)) {
239 for (
unsigned i = 0, NumResults = N->
getNumValues(); i < NumResults; ++i) {
243 switch (getTypeAction(ResultVT)) {
253 PromoteIntegerResult(N, i);
257 ExpandIntegerResult(N, i);
261 Changed = SoftenFloatResult(N, i);
265 assert(isLegalInHWReg(ResultVT) &&
266 "Unchanged SoftenFloatResult should be legal in register!");
269 ExpandFloatResult(N, i);
273 ScalarizeVectorResult(N, i);
277 SplitVectorResult(N, i);
281 WidenVectorResult(N, i);
285 PromoteFloatResult(N, i);
296 bool NeedsReanalyzing =
false;
298 for (i = 0; i != NumOperands; ++i) {
304 EVT OpVT =
Op.getValueType();
305 switch (getTypeAction(OpVT)) {
313 NeedsReanalyzing = PromoteIntegerOperand(N, i);
317 NeedsReanalyzing = ExpandIntegerOperand(N, i);
321 NeedsReanalyzing = SoftenFloatOperand(N, i);
325 NeedsReanalyzing = ExpandFloatOperand(N, i);
329 NeedsReanalyzing = ScalarizeVectorOperand(N, i);
333 NeedsReanalyzing = SplitVectorOperand(N, i);
337 NeedsReanalyzing = WidenVectorOperand(N, i);
341 NeedsReanalyzing = PromoteFloatOperand(N, i);
351 if (NeedsReanalyzing) {
357 SDNode *M = AnalyzeNewNode(N);
365 "Node morphing changed the number of results!");
366 for (
unsigned i = 0, e = N->
getNumValues(); i != e; ++i)
376 if (i == NumOperands) {
400 Worklist.push_back(User);
418 Worklist.push_back(User);
422 #ifndef EXPENSIVE_CHECKS 425 PerformExpensiveChecks();
448 if (!IgnoreNodeResults(&Node))
449 for (
unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
450 if (!isTypeLegal(Node.getValueType(i)) &&
452 dbgs() <<
"Result type " << i <<
" illegal: ";
458 for (
unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
459 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
460 !isTypeLegal(Node.getOperand(i).getValueType()) &&
461 !TLI.
isTypeLegal(Node.getOperand(i).getValueType())) {
462 dbgs() <<
"Operand type " << i <<
" illegal: ";
463 Node.getOperand(i).dump(&DAG);
468 if (Node.getNodeId() ==
NewNode)
469 dbgs() <<
"New node not analyzed?\n";
471 dbgs() <<
"Unanalyzed node not noticed?\n";
472 else if (Node.getNodeId() > 0)
473 dbgs() <<
"Operand not processed?\n";
475 dbgs() <<
"Not added to worklist?\n";
480 Node.dump(&DAG);
dbgs() <<
"\n";
509 std::vector<SDValue> NewOps;
510 unsigned NumProcessed = 0;
520 if (!NewOps.empty()) {
522 NewOps.push_back(Op);
523 }
else if (Op != OrigOp) {
526 NewOps.push_back(Op);
531 if (!NewOps.empty()) {
554 Worklist.push_back(N);
561 void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
570 void DAGTypeLegalizer::RemapValue(
SDValue &V) {
571 auto Id = getTableId(V);
575 void DAGTypeLegalizer::RemapId(
TableId &
Id) {
576 auto I = ReplacedValues.find(Id);
577 if (
I != ReplacedValues.end()) {
578 assert(Id !=
I->second &&
"Id is mapped to itself.");
600 DTL(dtl), NodesToAnalyze(nta) {}
605 "Invalid node ID for RAUW deletion!");
608 assert(E &&
"Node not replaced?");
623 void NodeUpdated(
SDNode *N)
override {
629 "Invalid node ID for RAUW deletion!");
648 NodeUpdateListener NUL(*
this, NodesToAnalyze);
653 auto FromId = getTableId(From);
654 auto ToId = getTableId(To);
657 ReplacedValues[FromId] = ToId;
658 DAG.ReplaceAllUsesOfValueWith(From, To);
661 while (!NodesToAnalyze.
empty()) {
671 SDNode *M = AnalyzeNewNode(N);
677 "Node morphing changed the number of results!");
678 for (
unsigned i = 0, e = N->
getNumValues(); i != e; ++i) {
687 auto OldValId = getTableId(OldVal);
688 auto NewValId = getTableId(NewVal);
689 DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
690 if (OldValId != NewValId)
691 ReplacedValues[OldValId] = NewValId;
704 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) &&
705 "Invalid type for promoted integer");
706 AnalyzeNewValue(Result);
708 auto &OpIdEntry = PromotedIntegers[getTableId(Op)];
709 assert((OpIdEntry == 0) &&
"Node is already promoted!");
710 OpIdEntry = getTableId(Result);
712 DAG.transferDbgValues(Op, Result);
715 void DAGTypeLegalizer::SetSoftenedFloat(
SDValue Op,
SDValue Result) {
719 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) ||
721 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType())) &&
722 "Invalid type for softened float");
723 AnalyzeNewValue(Result);
725 auto &OpIdEntry = SoftenedFloats[getTableId(Op)];
729 assert(((OpIdEntry == 0) ||
731 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType())) &&
732 "Node is already converted to integer!");
733 OpIdEntry = getTableId(Result);
736 void DAGTypeLegalizer::SetPromotedFloat(
SDValue Op,
SDValue Result) {
738 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) &&
739 "Invalid type for promoted float");
740 AnalyzeNewValue(Result);
742 auto &OpIdEntry = PromotedFloats[getTableId(Op)];
743 assert((OpIdEntry == 0) &&
"Node is already promoted!");
744 OpIdEntry = getTableId(Result);
747 void DAGTypeLegalizer::SetScalarizedVector(
SDValue Op,
SDValue Result) {
752 "Invalid type for scalarized vector");
753 AnalyzeNewValue(Result);
755 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)];
756 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
757 OpIdEntry = getTableId(Result);
762 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
763 assert((Entry.first != 0) &&
"Operand isn't expanded");
764 Lo = getSDValue(Entry.first);
765 Hi = getSDValue(Entry.second);
771 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) &&
773 "Invalid type for expanded integer");
780 if (DAG.getDataLayout().isBigEndian()) {
791 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
792 assert((Entry.first == 0) &&
"Node already expanded");
793 Entry.first = getTableId(Lo);
794 Entry.second = getTableId(Hi);
799 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
800 assert((Entry.first != 0) &&
"Operand isn't expanded");
801 Lo = getSDValue(Entry.first);
802 Hi = getSDValue(Entry.second);
808 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) &&
810 "Invalid type for expanded float");
815 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
816 assert((Entry.first == 0) &&
"Node already expanded");
817 Entry.first = getTableId(Lo);
818 Entry.second = getTableId(Hi);
823 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
824 Lo = getSDValue(Entry.first);
825 Hi = getSDValue(Entry.second);
837 "Invalid type for split vector");
843 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
844 assert((Entry.first == 0) &&
"Node already split");
845 Entry.first = getTableId(Lo);
846 Entry.second = getTableId(Hi);
849 void DAGTypeLegalizer::SetWidenedVector(
SDValue Op,
SDValue Result) {
851 TLI.getTypeToTransformTo(*DAG.getContext(), Op.
getValueType()) &&
852 "Invalid type for widened vector");
853 AnalyzeNewValue(Result);
855 auto &OpIdEntry = WidenedVectors[getTableId(Op)];
856 assert((OpIdEntry == 0) &&
"Node already widened!");
857 OpIdEntry = getTableId(Result);
873 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(
SDValue Op) {
903 bool DAGTypeLegalizer::CustomLowerNode(
SDNode *N,
EVT VT,
bool LegalizeResult) {
910 TLI.ReplaceNodeResults(N, Results, DAG);
912 TLI.LowerOperationWrapper(N, Results, DAG);
923 SetExpandedInteger(
SDValue(N, 0), Results[0], Results[1]);
925 ReplaceValueWith(
SDValue(N, 1), Results[2]);
931 "Custom lowering returned the wrong number of results!");
932 for (
unsigned i = 0, e = Results.
size(); i != e; ++i) {
933 ReplaceValueWith(
SDValue(N, i), Results[i]);
941 bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *N,
EVT VT) {
947 TLI.ReplaceNodeResults(N, Results, DAG);
955 "Custom lowering returned the wrong number of results!");
956 for (
unsigned i = 0, e = Results.
size(); i != e; ++i) {
959 ReplaceValueWith(
SDValue(N, i), Results[i]);
961 SetWidenedVector(
SDValue(N, i), Results[i]);
966 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *N,
unsigned ResNo) {
967 for (
unsigned i = 0, e = N->
getNumValues(); i != e; ++i)
975 void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
978 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.
getValueType());
980 DAG.getIntPtrConstant(0, dl));
982 DAG.getIntPtrConstant(1, dl));
995 EVT ShiftAmtVT = TLI.getShiftAmountTy(NVT, DAG.getDataLayout(),
false);
1000 return DAG.getNode(
ISD::OR, dlHi, NVT, Lo, Hi);
1011 }
else if (NumOps == 1) {
1013 return TLI.makeLibCall(DAG, LC, N->
getValueType(0),
Op, isSigned,
1015 }
else if (NumOps == 2) {
1017 return TLI.makeLibCall(DAG, LC, N->
getValueType(0), Ops, isSigned,
1021 for (
unsigned i = 0; i < NumOps; ++i)
1029 std::pair<SDValue, SDValue>
1042 Entry.
IsZExt = !isSigned;
1043 Args.push_back(Entry);
1045 SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
1046 TLI.getPointerTy(DAG.getDataLayout()));
1053 .
setLibCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee,
1055 .setSExtResult(isSigned)
1058 std::pair<SDValue, SDValue>
CallInfo = TLI.LowerCallTo(CLI);
1070 EVT BoolVT = getSetCCResultType(ValVT);
1073 return DAG.getNode(ExtendCode, dl, BoolVT, Bool);
1077 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1084 unsigned ReqShiftAmountInBits =
1087 TLI.getScalarShiftAmountTy(DAG.getDataLayout(), Op.
getValueType());
1088 if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits())
1097 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1101 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi);
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
static MVT getIntegerVT(unsigned BitWidth)
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
EVT getValueType() const
Return the ValueType of the referenced return value.
EXTRACT_ELEMENT - This is used to get the lower or upper (determined by a Constant, which is required to be operand #1) half of the integer or float value specified as operand #0.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
This class represents lattice values for constants.
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
void push_back(const T &Elt)
Clients of various APIs that cause global effects on the DAG can optionally implement this interface...
friend struct DAGUpdateListener
DAGUpdateListener is a friend so it can manipulate the listener stack.
Libcall
RTLIB::Libcall enum - This enum defines all of the runtime library calls the backend can emit...
static ISD::NodeType getExtendForContent(BooleanContent Content)
Function Alias Analysis Results
CallLoweringInfo & setDebugLoc(const SDLoc &dl)
This takes an arbitrary SelectionDAG as input and hacks on it until only value types the target machi...
void setNodeId(int Id)
Set unique node id.
SDNode * getNode() const
get the SDNode which holds the desired result
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
const T & back() const
Return the last element of the SetVector.
unsigned getValueSizeInBits() const
Returns the size of the value in bits.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
This node's ID needs to be set to the number of its unprocessed operands.
Shift and rotation operations.
Type * getTypeForEVT(LLVMContext &Context) const
This method returns an LLVM type corresponding to the specified EVT.
CallLoweringInfo & setChain(SDValue InChain)
unsigned getScalarValueSizeInBits() const
MVT::ElementCount getVectorElementCount() const
bool remove(const value_type &X)
Remove an item from the set vector.
void pop_back()
Remove the last element of the SetVector.
SelectionDAG & getDAG() const
iterator_range< allnodes_iterator > allnodes()
unsigned getSizeInBits() const
Return the size of the specified value type in bits.
bool insert(const value_type &X)
Insert a new element into the SetVector.
CallLoweringInfo & setZExtResult(bool Value=true)
op_iterator op_begin() const
amdgpu Simplify well known AMD library false Value * Callee
bool use_empty() const
Return true if there are no nodes using value ResNo of Node.
static cl::opt< bool > EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden)
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool run()
This is the main entry point for the type legalizer.
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
The instances of the Type class are immutable: once they are created, they are never changed...
unsigned getVectorNumElements() const
Given a vector type, return the number of elements it contains.
This is a new node, not before seen, that was created in the process of legalizing some other node...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const SDValue & getOperand(unsigned Num) const
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
This class provides iterator support for SDUse operands that use a specific SDNode.
std::string getEVTString() const
This function returns value type as a string, e.g. "i32".
std::vector< ArgListEntry > ArgListTy
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
This structure contains all information that is necessary for lowering calls.
This class contains a discriminated union of information about pointers in memory operands...
unsigned getNumOperands() const
Return the number of values used by this operation.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void NoteDeletion(SDNode *Old, SDNode *New)
void dump() const
Dump this node, for debugging.
A SetVector that performs no allocations if smaller than a certain size.
BlockVerifier::State From
void setNode(SDNode *N)
set the SDNode
EVT getVectorElementType() const
Given a vector type, return the type of each element.
testing::Matcher< const detail::ErrorHolder & > Failed()
SDNode * UpdateNodeOperands(SDNode *N, SDValue Op)
Mutate the specified node in-place to have the specified operands.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
This is a node that has already been processed.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static EVT getVectorVT(LLVMContext &Context, EVT VT, unsigned NumElements, bool IsScalable=false)
Returns the EVT that represents a vector NumElements in length, where each element is of type VT...
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
static use_iterator use_end()
ZERO_EXTEND - Used for integer types, zeroing the new bits.
ANY_EXTEND - Used for integer types. The high bits are undefined.
int getNodeId() const
Return the unique node id.
bool isVector() const
Return true if this is a vector value type.
LLVM_NODISCARD bool empty() const
bool empty() const
Determine if the SetVector is empty or not.
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
This class is used to form a handle around another node that is persistent and is updated across invo...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
All operands have been processed, so this node is ready to be handled.
TRUNCATE - Completely drop the high bits.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth)
Returns the EVT that represents an integer with the given number of bits.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
CallLoweringInfo & setLibCallee(CallingConv::ID CC, Type *ResultType, SDValue Target, ArgListTy &&ArgsList)
DAGTypeLegalizer(SelectionDAG &dag)