23#define DEBUG_TYPE "legalize-types"
29void DAGTypeLegalizer::PerformExpensiveChecks() {
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))
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) {
406 int NodeId =
User->getNodeId();
411 User->setNodeId(NodeId-1);
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) {
525 if (Op.getNode()->getNodeId() ==
Processed)
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);
570void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
579void DAGTypeLegalizer::RemapValue(
SDValue &V) {
580 auto Id = getTableId(V);
584void 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());
710void DAGTypeLegalizer::SetPromotedInteger(
SDValue Op,
SDValue Result) {
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);
724void DAGTypeLegalizer::SetSoftenedFloat(
SDValue Op,
SDValue Result) {
730 "Invalid type for softened float");
732 AnalyzeNewValue(Result);
734 auto &OpIdEntry = SoftenedFloats[getTableId(Op)];
735 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
736 OpIdEntry = getTableId(Result);
739void DAGTypeLegalizer::SetPromotedFloat(
SDValue Op,
SDValue Result) {
742 "Invalid type for promoted float");
743 AnalyzeNewValue(Result);
745 auto &OpIdEntry = PromotedFloats[getTableId(Op)];
746 assert((OpIdEntry == 0) &&
"Node is already promoted!");
747 OpIdEntry = getTableId(Result);
750void DAGTypeLegalizer::SetSoftPromotedHalf(
SDValue Op,
SDValue Result) {
752 "Invalid type for soft-promoted half");
753 AnalyzeNewValue(Result);
755 auto &OpIdEntry = SoftPromotedHalfs[getTableId(Op)];
756 assert((OpIdEntry == 0) &&
"Node is already promoted!");
757 OpIdEntry = getTableId(Result);
760void DAGTypeLegalizer::SetScalarizedVector(
SDValue Op,
SDValue Result) {
767 Op.getScalarValueSizeInBits() &&
768 "Invalid type for scalarized vector");
769 AnalyzeNewValue(Result);
771 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)];
772 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
773 OpIdEntry = getTableId(Result);
778 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
779 assert((Entry.first != 0) &&
"Operand isn't expanded");
780 Lo = getSDValue(Entry.first);
781 Hi = getSDValue(Entry.second);
788 Hi.getValueType() ==
Lo.getValueType() &&
789 "Invalid type for expanded integer");
799 Lo.getValueSizeInBits());
803 Hi.getValueSizeInBits());
807 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
808 assert((Entry.first == 0) &&
"Node already expanded");
809 Entry.first = getTableId(
Lo);
810 Entry.second = getTableId(
Hi);
815 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
816 assert((Entry.first != 0) &&
"Operand isn't expanded");
817 Lo = getSDValue(Entry.first);
818 Hi = getSDValue(Entry.second);
825 Hi.getValueType() ==
Lo.getValueType() &&
826 "Invalid type for expanded float");
831 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
832 assert((Entry.first == 0) &&
"Node already expanded");
833 Entry.first = getTableId(
Lo);
834 Entry.second = getTableId(
Hi);
839 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
840 Lo = getSDValue(Entry.first);
841 Hi = getSDValue(Entry.second);
842 assert(
Lo.getNode() &&
"Operand isn't split");
848 assert(
Lo.getValueType().getVectorElementType() ==
849 Op.getValueType().getVectorElementType() &&
850 Lo.getValueType().getVectorElementCount() * 2 ==
851 Op.getValueType().getVectorElementCount() &&
852 Hi.getValueType() ==
Lo.getValueType() &&
853 "Invalid type for split vector");
859 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
860 assert((Entry.first == 0) &&
"Node already split");
861 Entry.first = getTableId(
Lo);
862 Entry.second = getTableId(
Hi);
865void DAGTypeLegalizer::SetWidenedVector(
SDValue Op,
SDValue Result) {
868 "Invalid type for widened vector");
869 AnalyzeNewValue(Result);
871 auto &OpIdEntry = WidenedVectors[getTableId(Op)];
872 assert((OpIdEntry == 0) &&
"Node already widened!");
873 OpIdEntry = getTableId(Result);
889SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(
SDValue Op) {
890 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
891 unsigned EltWidth =
Op.getScalarValueSizeInBits();
893 auto EltCnt =
Op.getValueType().getVectorElementCount();
926bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
943 "Custom lowering returned the wrong number of results!");
944 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
953bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
967 "Custom lowering returned the wrong number of results!");
968 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
979SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
980 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
983 return SDValue(
N->getOperand(ResNo));
988void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
1003 EVT LVT =
Lo.getValueType();
1004 EVT HVT =
Hi.getValueType();
1026void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1031 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1033 unsigned ReqShiftAmountInBits =
1046void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1050 SplitInteger(Op, HalfVT, HalfVT,
Lo,
Hi);
Function Alias Analysis Results
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< bool > EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This takes an arbitrary SelectionDAG as input and hacks on it until only value types the target machi...
bool run()
This is the main entry point for the type legalizer.
void NoteDeletion(SDNode *Old, SDNode *New)
@ ReadyToProcess
All operands have been processed, so this node is ready to be handled.
@ NewNode
This is a new node, not before seen, that was created in the process of legalizing some other node.
@ Unanalyzed
This node's ID needs to be set to the number of its unprocessed operands.
@ Processed
This is a node that has already been processed.
Type * getValueType() const
This class is used to form a handle around another node that is persistent and is updated across invo...
This is an important class for using LLVM in a threaded context.
TypeSize getSizeInBits() const
Returns the size of the specified MVT in bits.
static MVT getIntegerVT(unsigned BitWidth)
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
This class provides iterator support for SDUse operands that use a specific SDNode.
Represents one node in the SelectionDAG.
int getNodeId() const
Return the unique node id.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
EVT getValueType() const
Return the ValueType of the referenced return value.
void setNode(SDNode *N)
set the SDNode
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Align getReducedAlign(EVT VT, bool UseABI)
In most cases this function returns the ABI alignment for a given type, except for illegal vector typ...
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
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,...
const DataLayout & getDataLayout() const
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
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.
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
iterator_range< allnodes_iterator > allnodes()
SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL, bool isTarget=false)
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
void ReplaceAllUsesOfValueWith(SDValue From, SDValue To)
Replace any uses of From with To, leaving uses of other values produced by From.getNode() alone.
LLVMContext * getContext() const
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment)
Create a stack temporary based on the size in bytes and the alignment.
SDNode * UpdateNodeOperands(SDNode *N, SDValue Op)
Mutate the specified node in-place to have the specified operands.
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
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 ...
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
bool remove(const value_type &X)
Remove an item from the set vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SDValue promoteTargetBoolean(SelectionDAG &DAG, SDValue Bool, EVT ValVT) const
Promote the given target boolean to a target boolean of the given type.
@ TypeScalarizeScalableVector
EVT getShiftAmountTy(EVT LHSTy, const DataLayout &DL, bool LegalTypes=true) const
Returns the type for the shift amount of a shift opcode.
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
virtual MVT getScalarShiftAmountTy(const DataLayout &, EVT) const
Return the type to use for a scalar shift opcode, given the shifted amount type.
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...
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...
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...
unsigned getNumOperands() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ ANY_EXTEND
ANY_EXTEND - Used for integer types. The high bits are undefined.
@ BITCAST
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
@ EXTRACT_ELEMENT
EXTRACT_ELEMENT - This is used to get the lower or upper (determined by a Constant,...
@ SHL
Shift and rotation operations.
@ ZERO_EXTEND
ZERO_EXTEND - Used for integer types, zeroing the new bits.
@ TRUNCATE
TRUNCATE - Completely drop the high bits.
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
testing::Matcher< const detail::ErrorHolder & > Failed()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
constexpr unsigned BitWidth
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
This struct is a compact representation of a valid (non-zero power of two) alignment.
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.
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth)
Returns the EVT that represents an integer with the given number of bits.
std::string getEVTString() const
This function returns value type as a string, e.g. "i32".
This class contains a discriminated union of information about pointers in memory operands,...
Clients of various APIs that cause global effects on the DAG can optionally implement this interface.