Go to the documentation of this file.
23 #define DEBUG_TYPE "legalize-types"
29 void DAGTypeLegalizer::PerformExpensiveChecks() {
76 if (Node.getNodeId() ==
NewNode)
77 NewNodes.push_back(&Node);
79 for (
unsigned i = 0,
e = Node.getNumValues();
i !=
e; ++
i) {
83 auto ResId = ValueToIdMap.lookup(Res);
87 auto I = ReplacedValues.
find(ResId);
88 if (
I != ReplacedValues.
end()) {
93 if (UI.getUse().getResNo() ==
i)
95 "Remapped value has non-trivial use!");
99 auto NewValId =
I->second;
100 I = ReplacedValues.
find(NewValId);
101 while (
I != ReplacedValues.
end()) {
102 NewValId =
I->second;
103 I = ReplacedValues.
find(NewValId);
105 SDValue NewVal = getSDValue(NewValId);
108 "ReplacedValues maps to a new node!");
110 if (PromotedIntegers.
count(ResId))
112 if (SoftenedFloats.
count(ResId))
114 if (ScalarizedVectors.
count(ResId))
116 if (ExpandedIntegers.
count(ResId))
118 if (ExpandedFloats.
count(ResId))
120 if (SplitVectors.
count(ResId))
122 if (WidenedVectors.
count(ResId))
124 if (PromotedFloats.
count(ResId))
126 if (SoftPromotedHalfs.
count(ResId))
134 if ((Node.getNodeId() ==
NewNode && Mapped > 1) ||
135 (Node.getNodeId() !=
NewNode && Mapped != 0)) {
136 dbgs() <<
"Unprocessed value in a map!";
139 }
else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(&Node)) {
141 dbgs() <<
"Value with legal type was transformed!";
146 SDValue NodeById = IdToValueMap.lookup(ResId);
153 dbgs() <<
"Processed value not in any map!";
156 }
else if (Mapped & (Mapped - 1)) {
157 dbgs() <<
"Value in multiple maps!";
164 dbgs() <<
" ReplacedValues";
166 dbgs() <<
" PromotedIntegers";
168 dbgs() <<
" SoftenedFloats";
170 dbgs() <<
" ScalarizedVectors";
172 dbgs() <<
" ExpandedIntegers";
174 dbgs() <<
" ExpandedFloats";
176 dbgs() <<
" SplitVectors";
178 dbgs() <<
" WidenedVectors";
180 dbgs() <<
" PromotedFloats";
182 dbgs() <<
" SoftPromoteHalfs";
191 for (
unsigned i = 0,
e = NewNodes.size();
i !=
e; ++
i) {
194 assert(U->getNodeId() ==
NewNode &&
"NewNode used by non-NewNode!");
203 bool Changed =
false;
219 if (Node.getNumOperands() == 0) {
221 Worklist.push_back(&Node);
228 while (!Worklist.empty()) {
229 #ifndef EXPENSIVE_CHECKS
232 PerformExpensiveChecks();
234 SDNode *
N = Worklist.pop_back_val();
236 "Node should be ready if on worklist!");
239 if (IgnoreNodeResults(
N)) {
246 for (
unsigned i = 0, NumResults =
N->getNumValues();
i < NumResults; ++
i) {
247 EVT ResultVT =
N->getValueType(
i);
250 switch (getTypeAction(ResultVT)) {
256 "Scalarization of scalable vectors is not supported.");
263 PromoteIntegerResult(
N,
i);
267 ExpandIntegerResult(
N,
i);
271 SoftenFloatResult(
N,
i);
275 ExpandFloatResult(
N,
i);
279 ScalarizeVectorResult(
N,
i);
283 SplitVectorResult(
N,
i);
287 WidenVectorResult(
N,
i);
291 PromoteFloatResult(
N,
i);
295 SoftPromoteHalfResult(
N,
i);
305 unsigned NumOperands =
N->getNumOperands();
306 bool NeedsReanalyzing =
false;
308 for (
i = 0;
i != NumOperands; ++
i) {
309 if (IgnoreNodeResults(
N->getOperand(
i).getNode()))
312 const auto &
Op =
N->getOperand(
i);
314 EVT OpVT =
Op.getValueType();
315 switch (getTypeAction(OpVT)) {
321 "Scalarization of scalable vectors is not supported.");
326 NeedsReanalyzing = PromoteIntegerOperand(
N,
i);
330 NeedsReanalyzing = ExpandIntegerOperand(
N,
i);
334 NeedsReanalyzing = SoftenFloatOperand(
N,
i);
338 NeedsReanalyzing = ExpandFloatOperand(
N,
i);
342 NeedsReanalyzing = ScalarizeVectorOperand(
N,
i);
346 NeedsReanalyzing = SplitVectorOperand(
N,
i);
350 NeedsReanalyzing = WidenVectorOperand(
N,
i);
354 NeedsReanalyzing = PromoteFloatOperand(
N,
i);
358 NeedsReanalyzing = SoftPromoteHalfOperand(
N,
i);
368 if (NeedsReanalyzing) {
381 assert(
N->getNumValues() ==
M->getNumValues() &&
382 "Node morphing changed the number of results!");
383 for (
unsigned i = 0,
e =
N->getNumValues();
i !=
e; ++
i)
393 if (
i == NumOperands) {
415 Worklist.push_back(
User);
433 Worklist.push_back(
User);
437 #ifndef EXPENSIVE_CHECKS
440 PerformExpensiveChecks();
458 if (!IgnoreNodeResults(&Node))
459 for (
unsigned i = 0, NumVals = Node.getNumValues();
i < NumVals; ++
i)
460 if (!isTypeLegal(Node.getValueType(
i))) {
461 dbgs() <<
"Result type " <<
i <<
" illegal: ";
467 for (
unsigned i = 0, NumOps = Node.getNumOperands();
i < NumOps; ++
i)
468 if (!IgnoreNodeResults(Node.getOperand(
i).getNode()) &&
469 !isTypeLegal(Node.getOperand(
i).getValueType())) {
470 dbgs() <<
"Operand type " <<
i <<
" illegal: ";
471 Node.getOperand(
i).dump(&DAG);
476 if (Node.getNodeId() ==
NewNode)
477 dbgs() <<
"New node not analyzed?\n";
479 dbgs() <<
"Unanalyzed node not noticed?\n";
480 else if (Node.getNodeId() > 0)
481 dbgs() <<
"Operand not processed?\n";
483 dbgs() <<
"Not added to worklist?\n";
488 Node.dump(&DAG);
dbgs() <<
"\n";
517 std::vector<SDValue> NewOps;
518 unsigned NumProcessed = 0;
519 for (
unsigned i = 0,
e =
N->getNumOperands();
i !=
e; ++
i) {
528 if (!NewOps.empty()) {
530 NewOps.push_back(
Op);
531 }
else if (
Op != OrigOp) {
533 NewOps.insert(NewOps.end(),
N->op_begin(),
N->op_begin() +
i);
534 NewOps.push_back(
Op);
539 if (!NewOps.empty()) {
561 N->setNodeId(
N->getNumOperands() - NumProcessed);
563 Worklist.push_back(
N);
570 void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
579 void DAGTypeLegalizer::RemapValue(
SDValue &V) {
580 auto Id = getTableId(V);
584 void DAGTypeLegalizer::RemapId(TableId &
Id) {
585 auto I = ReplacedValues.
find(
Id);
586 if (
I != ReplacedValues.
end()) {
587 assert(
Id !=
I->second &&
"Id is mapped to itself.");
609 DTL(dtl), NodesToAnalyze(nta) {}
614 "Invalid node ID for RAUW deletion!");
617 assert(
E &&
"Node not replaced?");
632 void NodeUpdated(
SDNode *
N)
override {
638 "Invalid node ID for RAUW deletion!");
657 NodeUpdateListener NUL(*
this, NodesToAnalyze);
662 auto FromId = getTableId(
From);
663 auto ToId = getTableId(To);
666 ReplacedValues[FromId] = ToId;
670 while (!NodesToAnalyze.
empty()) {
683 assert(
M->getNodeId() !=
NewNode &&
"Analysis resulted in NewNode!");
684 assert(
N->getNumValues() ==
M->getNumValues() &&
685 "Node morphing changed the number of results!");
686 for (
unsigned i = 0,
e =
N->getNumValues();
i !=
e; ++
i) {
695 auto OldValId = getTableId(OldVal);
696 auto NewValId = getTableId(NewVal);
698 if (OldValId != NewValId)
699 ReplacedValues[OldValId] = NewValId;
707 }
while (!
From.use_empty());
713 "Invalid type for promoted integer");
714 AnalyzeNewValue(Result);
716 auto &OpIdEntry = PromotedIntegers[getTableId(
Op)];
717 assert((OpIdEntry == 0) &&
"Node is already promoted!");
718 OpIdEntry = getTableId(Result);
727 "Invalid type for softened float");
728 AnalyzeNewValue(Result);
730 auto &OpIdEntry = SoftenedFloats[getTableId(
Op)];
731 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
732 OpIdEntry = getTableId(Result);
738 "Invalid type for promoted float");
739 AnalyzeNewValue(Result);
741 auto &OpIdEntry = PromotedFloats[getTableId(
Op)];
742 assert((OpIdEntry == 0) &&
"Node is already promoted!");
743 OpIdEntry = getTableId(Result);
748 "Invalid type for soft-promoted half");
749 AnalyzeNewValue(Result);
751 auto &OpIdEntry = SoftPromotedHalfs[getTableId(
Op)];
752 assert((OpIdEntry == 0) &&
"Node is already promoted!");
753 OpIdEntry = getTableId(Result);
763 Op.getScalarValueSizeInBits() &&
764 "Invalid type for scalarized vector");
765 AnalyzeNewValue(Result);
767 auto &OpIdEntry = ScalarizedVectors[getTableId(
Op)];
768 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
769 OpIdEntry = getTableId(Result);
774 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
775 assert((Entry.first != 0) &&
"Operand isn't expanded");
776 Lo = getSDValue(Entry.first);
777 Hi = getSDValue(Entry.second);
784 Hi.getValueType() ==
Lo.getValueType() &&
785 "Invalid type for expanded integer");
795 Lo.getValueSizeInBits());
799 Hi.getValueSizeInBits());
803 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
804 assert((Entry.first == 0) &&
"Node already expanded");
805 Entry.first = getTableId(Lo);
806 Entry.second = getTableId(Hi);
811 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
812 assert((Entry.first != 0) &&
"Operand isn't expanded");
813 Lo = getSDValue(Entry.first);
814 Hi = getSDValue(Entry.second);
821 Hi.getValueType() ==
Lo.getValueType() &&
822 "Invalid type for expanded float");
827 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
828 assert((Entry.first == 0) &&
"Node already expanded");
829 Entry.first = getTableId(Lo);
830 Entry.second = getTableId(Hi);
835 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
836 Lo = getSDValue(Entry.first);
837 Hi = getSDValue(Entry.second);
838 assert(
Lo.getNode() &&
"Operand isn't split");
844 assert(
Lo.getValueType().getVectorElementType() ==
845 Op.getValueType().getVectorElementType() &&
846 Lo.getValueType().getVectorElementCount() * 2 ==
847 Op.getValueType().getVectorElementCount() &&
848 Hi.getValueType() ==
Lo.getValueType() &&
849 "Invalid type for split vector");
855 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
856 assert((Entry.first == 0) &&
"Node already split");
857 Entry.first = getTableId(Lo);
858 Entry.second = getTableId(Hi);
864 "Invalid type for widened vector");
865 AnalyzeNewValue(Result);
867 auto &OpIdEntry = WidenedVectors[getTableId(
Op)];
868 assert((OpIdEntry == 0) &&
"Node already widened!");
869 OpIdEntry = getTableId(Result);
886 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
887 unsigned EltWidth =
Op.getScalarValueSizeInBits();
889 auto EltCnt =
Op.getValueType().getVectorElementCount();
922 bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
939 "Custom lowering returned the wrong number of results!");
949 bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
963 "Custom lowering returned the wrong number of results!");
975 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
976 for (
unsigned i = 0,
e =
N->getNumValues();
i !=
e; ++
i)
979 return SDValue(
N->getOperand(ResNo));
984 void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
999 EVT LVT =
Lo.getValueType();
1000 EVT HVT =
Hi.getValueType();
1022 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1027 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1029 unsigned ReqShiftAmountInBits =
1042 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1046 SplitInteger(
Op, HalfVT, HalfVT, Lo, Hi);
void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits=0, unsigned SizeInBits=0, bool InvalidateDbg=true)
Transfer debug values from one node to another, while optionally generating fragment expressions for ...
virtual void LowerOperationWrapper(SDNode *N, SmallVectorImpl< SDValue > &Results, SelectionDAG &DAG) const
This callback is invoked by the type legalizer to legalize nodes with an illegal operand type but leg...
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
@ BITCAST
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
SDNode * getNode() const
get the SDNode which holds the desired result
@ TypeScalarizeScalableVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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...
@ ANY_EXTEND
ANY_EXTEND - Used for integer types. The high bits are undefined.
Represents one node in the SelectionDAG.
This class provides iterator support for SDUse operands that use a specific SDNode.
SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, Align Alignment, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes())
Helper function to build ISD::STORE nodes.
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.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Function Alias Analysis Results
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
@ Unanalyzed
This node's ID needs to be set to the number of its unprocessed operands.
LegalizeAction getOperationAction(unsigned Op, EVT VT) const
Return how this operation should be treated: either it is legal, needs to be promoted to a larger siz...
LLVMContext * getContext() const
EVT getShiftAmountTy(EVT LHSTy, const DataLayout &DL, bool LegalTypes=true) const
Returns the type for the shift amount of a shift opcode.
This takes an arbitrary SelectionDAG as input and hacks on it until only value types the target machi...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool remove(const value_type &X)
Remove an item from the set vector.
SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, MaybeAlign Alignment=MaybeAlign(), MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr)
Loads are not normal binary operators: their result type is not determined by their operands,...
EVT getValueType() const
Return the ValueType of the referenced return value.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
SDNode * UpdateNodeOperands(SDNode *N, SDValue Op)
Mutate the specified node in-place to have the specified operands.
testing::Matcher< const detail::ErrorHolder & > Failed()
@ ZERO_EXTEND
ZERO_EXTEND - Used for integer types, zeroing the new bits.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
void NoteDeletion(SDNode *Old, SDNode *New)
@ TRUNCATE
TRUNCATE - Completely drop the high bits.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
This struct is a compact representation of a valid (non-zero power of two) alignment.
bool empty() const
Determine if the SetVector is empty or not.
EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
@ Processed
This is a node that has already been processed.
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL, bool isTarget=false)
This class contains a discriminated union of information about pointers in memory operands,...
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
iterator_range< allnodes_iterator > allnodes()
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth)
Returns the EVT that represents an integer with the given number of bits.
TypeSize getSizeInBits() const
Returns the size of the specified MVT in bits.
int getNodeId() const
Return the unique node id.
SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment)
Create a stack temporary based on the size in bytes and the alignment.
bool insert(const value_type &X)
Insert a new element into the SetVector.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void ReplaceAllUsesOfValueWith(SDValue From, SDValue To)
Replace any uses of From with To, leaving uses of other values produced by From.getNode() alone.
Align getReducedAlign(EVT VT, bool UseABI)
In most cases this function returns the ABI alignment for a given type, except for illegal vector typ...
std::string getEVTString() const
This function returns value type as a string, e.g. "i32".
@ NewNode
This is a new node, not before seen, that was created in the process of legalizing some other node.
static cl::opt< bool > EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden)
virtual MVT getScalarShiftAmountTy(const DataLayout &, EVT) const
Return the type to use for a scalar shift opcode, given the shifted amount type.
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
const DataLayout & getDataLayout() const
constexpr unsigned BitWidth
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
virtual void ReplaceNodeResults(SDNode *, SmallVectorImpl< SDValue > &, SelectionDAG &) const
This callback is invoked when a node result type is illegal for the target, and the operation was reg...
unsigned getNumOperands() const
@ SHL
Shift and rotation operations.
A SetVector that performs no allocations if smaller than a certain size.
Type * getValueType() const
BlockVerifier::State From
void setNode(SDNode *N)
set the SDNode
Clients of various APIs that cause global effects on the DAG can optionally implement this interface.
SDValue promoteTargetBoolean(SelectionDAG &DAG, SDValue Bool, EVT ValVT) const
Promote the given target boolean to a target boolean of the given type.
bool run()
This is the main entry point for the type legalizer.
@ ReadyToProcess
All operands have been processed, so this node is ready to be handled.
LLVM_NODISCARD T pop_back_val()
@ EXTRACT_ELEMENT
EXTRACT_ELEMENT - This is used to get the lower or upper (determined by a Constant,...
static MVT getIntegerVT(unsigned BitWidth)