26 #define DEBUG_TYPE "legalize-types" 32 void DAGTypeLegalizer::PerformExpensiveChecks() {
79 if (Node.getNodeId() ==
NewNode)
82 for (
unsigned i = 0,
e = Node.getNumValues(); i !=
e; ++i) {
86 auto ResId = (ValueToIdMap.count(Res)) ? ValueToIdMap[Res] : 0;
89 if (ResId && (ReplacedValues.find(ResId) != ReplacedValues.end())) {
94 if (UI.getUse().getResNo() == i)
96 "Remapped value has non-trivial use!");
100 auto NewValId = ReplacedValues[ResId];
101 auto I = ReplacedValues.find(NewValId);
102 while (
I != ReplacedValues.end()) {
103 NewValId =
I->second;
104 I = ReplacedValues.find(NewValId);
106 SDValue NewVal = getSDValue(NewValId);
109 "ReplacedValues maps to a new node!");
111 if (ResId && PromotedIntegers.find(ResId) != PromotedIntegers.end())
113 if (ResId && SoftenedFloats.find(ResId) != SoftenedFloats.end())
115 if (ResId && ScalarizedVectors.find(ResId) != ScalarizedVectors.end())
117 if (ResId && ExpandedIntegers.find(ResId) != ExpandedIntegers.end())
119 if (ResId && ExpandedFloats.find(ResId) != ExpandedFloats.end())
121 if (ResId && SplitVectors.find(ResId) != SplitVectors.end())
123 if (ResId && WidenedVectors.find(ResId) != WidenedVectors.end())
125 if (ResId && PromotedFloats.find(ResId) != PromotedFloats.end())
127 if (ResId && SoftPromotedHalfs.find(ResId) != SoftPromotedHalfs.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(Res.getValueType()) || IgnoreNodeResults(&Node)) {
141 dbgs() <<
"Value with legal type was transformed!";
146 dbgs() <<
"Processed value not in any map!";
148 }
else if (Mapped & (Mapped - 1)) {
149 dbgs() <<
"Value in multiple maps!";
156 dbgs() <<
" ReplacedValues";
158 dbgs() <<
" PromotedIntegers";
160 dbgs() <<
" SoftenedFloats";
162 dbgs() <<
" ScalarizedVectors";
164 dbgs() <<
" ExpandedIntegers";
166 dbgs() <<
" ExpandedFloats";
168 dbgs() <<
" SplitVectors";
170 dbgs() <<
" WidenedVectors";
172 dbgs() <<
" PromotedFloats";
174 dbgs() <<
" SoftPromoteHalfs";
183 for (
unsigned i = 0,
e = NewNodes.
size(); i !=
e; ++i) {
187 assert(UI->getNodeId() ==
NewNode &&
"NewNode used by non-NewNode!");
196 bool Changed =
false;
212 if (Node.getNumOperands() == 0) {
214 Worklist.push_back(&Node);
221 while (!Worklist.empty()) {
222 #ifndef EXPENSIVE_CHECKS 225 PerformExpensiveChecks();
230 "Node should be ready if on worklist!");
233 if (IgnoreNodeResults(
N)) {
240 for (
unsigned i = 0, NumResults =
N->getNumValues(); i < NumResults; ++i) {
241 EVT ResultVT =
N->getValueType(i);
244 switch (getTypeAction(ResultVT)) {
250 "Scalarization of scalable vectors is not supported.");
257 PromoteIntegerResult(
N, i);
261 ExpandIntegerResult(
N, i);
265 SoftenFloatResult(
N, i);
269 ExpandFloatResult(
N, i);
273 ScalarizeVectorResult(
N, i);
277 SplitVectorResult(
N, i);
281 WidenVectorResult(
N, i);
285 PromoteFloatResult(
N, i);
289 SoftPromoteHalfResult(
N, i);
299 unsigned NumOperands =
N->getNumOperands();
300 bool NeedsReanalyzing =
false;
302 for (i = 0; i != NumOperands; ++i) {
303 if (IgnoreNodeResults(
N->getOperand(i).getNode()))
306 const auto Op =
N->getOperand(i);
308 EVT OpVT =
Op.getValueType();
309 switch (getTypeAction(OpVT)) {
315 "Scalarization of scalable vectors is not supported.");
320 NeedsReanalyzing = PromoteIntegerOperand(
N, i);
324 NeedsReanalyzing = ExpandIntegerOperand(
N, i);
328 NeedsReanalyzing = SoftenFloatOperand(
N, i);
332 NeedsReanalyzing = ExpandFloatOperand(
N, i);
336 NeedsReanalyzing = ScalarizeVectorOperand(
N, i);
340 NeedsReanalyzing = SplitVectorOperand(
N, i);
344 NeedsReanalyzing = WidenVectorOperand(
N, i);
348 NeedsReanalyzing = PromoteFloatOperand(
N, i);
352 NeedsReanalyzing = SoftPromoteHalfOperand(
N, i);
362 if (NeedsReanalyzing) {
375 assert(
N->getNumValues() == M->getNumValues() &&
376 "Node morphing changed the number of results!");
377 for (
unsigned i = 0,
e =
N->getNumValues(); i !=
e; ++i)
387 if (i == NumOperands) {
411 Worklist.push_back(
User);
429 Worklist.push_back(
User);
433 #ifndef EXPENSIVE_CHECKS 436 PerformExpensiveChecks();
454 if (!IgnoreNodeResults(&Node))
455 for (
unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
456 if (!isTypeLegal(Node.getValueType(i))) {
457 dbgs() <<
"Result type " << i <<
" illegal: ";
463 for (
unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
464 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
465 !isTypeLegal(Node.getOperand(i).getValueType())) {
466 dbgs() <<
"Operand type " << i <<
" illegal: ";
467 Node.getOperand(i).dump(&DAG);
472 if (Node.getNodeId() ==
NewNode)
473 dbgs() <<
"New node not analyzed?\n";
475 dbgs() <<
"Unanalyzed node not noticed?\n";
476 else if (Node.getNodeId() > 0)
477 dbgs() <<
"Operand not processed?\n";
479 dbgs() <<
"Not added to worklist?\n";
484 Node.dump(&DAG);
dbgs() <<
"\n";
513 std::vector<SDValue> NewOps;
514 unsigned NumProcessed = 0;
515 for (
unsigned i = 0,
e =
N->getNumOperands(); i !=
e; ++i) {
524 if (!NewOps.empty()) {
526 NewOps.push_back(
Op);
527 }
else if (
Op != OrigOp) {
529 NewOps.insert(NewOps.end(),
N->op_begin(),
N->op_begin() + i);
530 NewOps.push_back(
Op);
535 if (!NewOps.empty()) {
556 N->setNodeId(
N->getNumOperands() - NumProcessed);
558 Worklist.push_back(
N);
565 void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
574 void DAGTypeLegalizer::RemapValue(
SDValue &V) {
575 auto Id = getTableId(V);
579 void DAGTypeLegalizer::RemapId(TableId &
Id) {
580 auto I = ReplacedValues.find(
Id);
581 if (
I != ReplacedValues.end()) {
582 assert(
Id !=
I->second &&
"Id is mapped to itself.");
604 DTL(dtl), NodesToAnalyze(nta) {}
609 "Invalid node ID for RAUW deletion!");
612 assert(
E &&
"Node not replaced?");
627 void NodeUpdated(
SDNode *
N)
override {
633 "Invalid node ID for RAUW deletion!");
652 NodeUpdateListener NUL(*
this, NodesToAnalyze);
657 auto FromId = getTableId(
From);
658 auto ToId = getTableId(To);
661 ReplacedValues[FromId] = ToId;
665 while (!NodesToAnalyze.
empty()) {
679 assert(
M->getNodeId() !=
NewNode &&
"Analysis resulted in NewNode!");
680 assert(
N->getNumValues() ==
M->getNumValues() &&
681 "Node morphing changed the number of results!");
682 for (
unsigned i = 0,
e =
N->getNumValues(); i !=
e; ++i) {
691 auto OldValId = getTableId(OldVal);
692 auto NewValId = getTableId(NewVal);
694 if (OldValId != NewValId)
695 ReplacedValues[OldValId] = NewValId;
703 }
while (!
From.use_empty());
709 "Invalid type for promoted integer");
710 AnalyzeNewValue(Result);
712 auto &OpIdEntry = PromotedIntegers[getTableId(
Op)];
713 assert((OpIdEntry == 0) &&
"Node is already promoted!");
714 OpIdEntry = getTableId(Result);
723 "Invalid type for softened float");
724 AnalyzeNewValue(Result);
726 auto &OpIdEntry = SoftenedFloats[getTableId(
Op)];
727 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
728 OpIdEntry = getTableId(Result);
734 "Invalid type for promoted float");
735 AnalyzeNewValue(Result);
737 auto &OpIdEntry = PromotedFloats[getTableId(
Op)];
738 assert((OpIdEntry == 0) &&
"Node is already promoted!");
739 OpIdEntry = getTableId(Result);
744 "Invalid type for soft-promoted half");
745 AnalyzeNewValue(Result);
747 auto &OpIdEntry = SoftPromotedHalfs[getTableId(
Op)];
748 assert((OpIdEntry == 0) &&
"Node is already promoted!");
749 OpIdEntry = getTableId(Result);
759 Op.getScalarValueSizeInBits() &&
760 "Invalid type for scalarized vector");
761 AnalyzeNewValue(Result);
763 auto &OpIdEntry = ScalarizedVectors[getTableId(
Op)];
764 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
765 OpIdEntry = getTableId(Result);
770 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
771 assert((Entry.first != 0) &&
"Operand isn't expanded");
772 Lo = getSDValue(Entry.first);
773 Hi = getSDValue(Entry.second);
780 Hi.getValueType() ==
Lo.getValueType() &&
781 "Invalid type for expanded integer");
791 Lo.getValueSizeInBits());
795 Hi.getValueSizeInBits());
799 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
800 assert((Entry.first == 0) &&
"Node already expanded");
801 Entry.first = getTableId(
Lo);
802 Entry.second = getTableId(
Hi);
807 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
808 assert((Entry.first != 0) &&
"Operand isn't expanded");
809 Lo = getSDValue(Entry.first);
810 Hi = getSDValue(Entry.second);
817 Hi.getValueType() ==
Lo.getValueType() &&
818 "Invalid type for expanded float");
823 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
824 assert((Entry.first == 0) &&
"Node already expanded");
825 Entry.first = getTableId(
Lo);
826 Entry.second = getTableId(
Hi);
831 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
832 Lo = getSDValue(Entry.first);
833 Hi = getSDValue(Entry.second);
834 assert(
Lo.getNode() &&
"Operand isn't split");
840 assert(
Lo.getValueType().getVectorElementType() ==
841 Op.getValueType().getVectorElementType() &&
842 Lo.getValueType().getVectorElementCount() * 2 ==
843 Op.getValueType().getVectorElementCount() &&
844 Hi.getValueType() ==
Lo.getValueType() &&
845 "Invalid type for split vector");
851 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
852 assert((Entry.first == 0) &&
"Node already split");
853 Entry.first = getTableId(
Lo);
854 Entry.second = getTableId(
Hi);
860 "Invalid type for widened vector");
861 AnalyzeNewValue(Result);
863 auto &OpIdEntry = WidenedVectors[getTableId(
Op)];
864 assert((OpIdEntry == 0) &&
"Node already widened!");
865 OpIdEntry = getTableId(Result);
882 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
883 unsigned EltWidth =
Op.getScalarValueSizeInBits();
885 auto EltCnt =
Op.getValueType().getVectorElementCount();
918 bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
935 "Custom lowering returned the wrong number of results!");
945 bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
959 "Custom lowering returned the wrong number of results!");
971 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
972 for (
unsigned i = 0,
e =
N->getNumValues(); i !=
e; ++i)
975 return SDValue(
N->getOperand(ResNo));
980 void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
995 EVT LVT =
Lo.getValueType();
996 EVT HVT =
Hi.getValueType();
1015 EVT BoolVT = getSetCCResultType(ValVT);
1018 return DAG.
getNode(ExtendCode, dl, BoolVT, Bool);
1022 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1027 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1029 unsigned ReqShiftAmountInBits =
1033 if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits())
1042 void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1046 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,...
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
This class represents lattice values for constants.
void push_back(const T &Elt)
Clients of various APIs that cause global effects on the DAG can optionally implement this interface.
static ISD::NodeType getExtendForContent(BooleanContent Content)
Function Alias Analysis Results
This takes an arbitrary SelectionDAG as input and hacks on it until only value types the target machi...
BooleanContent getBooleanContents(bool isVec, bool isFloat) const
For targets without i1 registers, this gives the nature of the high-bits of boolean values held in ty...
SDNode * getNode() const
get the SDNode which holds the desired result
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
const T & back() const
Return the last element of the SetVector.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
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 ...
SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL, bool isTarget=false)
This node's ID needs to be set to the number of its unprocessed operands.
Shift and rotation operations.
Align getReducedAlign(EVT VT, bool UseABI)
In most cases this function returns the ABI alignment for a given type, except for illegal vector typ...
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
const DataLayout & getDataLayout() const
bool remove(const value_type &X)
Remove an item from the set vector.
void pop_back()
Remove the last element of the SetVector.
iterator_range< allnodes_iterator > allnodes()
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...
bool insert(const value_type &X)
Insert a new element into the SetVector.
static cl::opt< bool > EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden)
bool run()
This is the main entry point for the type legalizer.
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")
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".
constexpr unsigned BitWidth
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
This class contains a discriminated union of information about pointers in memory operands,...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This struct is a compact representation of a valid (non-zero power of two) alignment.
void NoteDeletion(SDNode *Old, SDNode *New)
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...
SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment)
Create a stack temporary based on the size in bytes and the alignment.
A SetVector that performs no allocations if smaller than a certain size.
unsigned getNumOperands() const
BlockVerifier::State From
void setNode(SDNode *N)
set the SDNode
Align max(MaybeAlign Lhs, Align Rhs)
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 used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
virtual MVT getScalarShiftAmountTy(const DataLayout &, EVT) const
EVT is not used in-tree, but is used by out-of-tree target.
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...
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.
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.
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.
bool empty() const
Determine if the SetVector is empty or not.
Type * getValueType() const
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
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.
void ReplaceAllUsesOfValueWith(SDValue From, SDValue To)
Replace any uses of From with To, leaving uses of other values produced by From.getNode() alone.
TRUNCATE - Completely drop the high bits.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
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,...
static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth)
Returns the EVT that represents an integer with the given number of bits.
EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
LLVMContext * getContext() const
EVT getShiftAmountTy(EVT LHSTy, const DataLayout &DL, bool LegalTypes=true) const