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);
248 LLVM_DEBUG(
dbgs() <<
"Analyzing result type: " << ResultVT <<
"\n");
249 switch (getTypeAction(ResultVT)) {
255 "Scalarization of scalable vectors is not supported.");
262 PromoteIntegerResult(
N, i);
266 ExpandIntegerResult(
N, i);
270 SoftenFloatResult(
N, i);
274 ExpandFloatResult(
N, i);
278 ScalarizeVectorResult(
N, i);
282 SplitVectorResult(
N, i);
286 WidenVectorResult(
N, i);
290 PromoteFloatResult(
N, i);
294 SoftPromoteHalfResult(
N, i);
304 unsigned NumOperands =
N->getNumOperands();
305 bool NeedsReanalyzing =
false;
307 for (i = 0; i != NumOperands; ++i) {
308 if (IgnoreNodeResults(
N->getOperand(i).getNode()))
311 const auto &Op =
N->getOperand(i);
313 EVT OpVT = Op.getValueType();
314 switch (getTypeAction(OpVT)) {
320 "Scalarization of scalable vectors is not supported.");
325 NeedsReanalyzing = PromoteIntegerOperand(
N, i);
329 NeedsReanalyzing = ExpandIntegerOperand(
N, i);
333 NeedsReanalyzing = SoftenFloatOperand(
N, i);
337 NeedsReanalyzing = ExpandFloatOperand(
N, i);
341 NeedsReanalyzing = ScalarizeVectorOperand(
N, i);
345 NeedsReanalyzing = SplitVectorOperand(
N, i);
349 NeedsReanalyzing = WidenVectorOperand(
N, i);
353 NeedsReanalyzing = PromoteFloatOperand(
N, i);
357 NeedsReanalyzing = SoftPromoteHalfOperand(
N, i);
367 if (NeedsReanalyzing) {
380 assert(
N->getNumValues() == M->getNumValues() &&
381 "Node morphing changed the number of results!");
382 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
392 if (i == NumOperands) {
405 int NodeId =
User->getNodeId();
410 User->setNodeId(NodeId-1);
414 Worklist.push_back(
User);
432 Worklist.push_back(
User);
436#ifndef EXPENSIVE_CHECKS
439 PerformExpensiveChecks();
457 if (!IgnoreNodeResults(&Node))
458 for (
unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
459 if (!isTypeLegal(Node.getValueType(i))) {
460 dbgs() <<
"Result type " << i <<
" illegal: ";
466 for (
unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
467 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
468 !isTypeLegal(Node.getOperand(i).getValueType())) {
469 dbgs() <<
"Operand type " << i <<
" illegal: ";
470 Node.getOperand(i).dump(&DAG);
475 if (Node.getNodeId() ==
NewNode)
476 dbgs() <<
"New node not analyzed?\n";
478 dbgs() <<
"Unanalyzed node not noticed?\n";
479 else if (Node.getNodeId() > 0)
480 dbgs() <<
"Operand not processed?\n";
482 dbgs() <<
"Not added to worklist?\n";
487 Node.dump(&DAG);
dbgs() <<
"\n";
516 std::vector<SDValue> NewOps;
517 unsigned NumProcessed = 0;
518 for (
unsigned i = 0, e =
N->getNumOperands(); i != e; ++i) {
524 if (Op.getNode()->getNodeId() ==
Processed)
527 if (!NewOps.empty()) {
529 NewOps.push_back(Op);
530 }
else if (Op != OrigOp) {
532 NewOps.insert(NewOps.end(),
N->op_begin(),
N->op_begin() + i);
533 NewOps.push_back(Op);
538 if (!NewOps.empty()) {
560 N->setNodeId(
N->getNumOperands() - NumProcessed);
562 Worklist.push_back(
N);
569void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
578void DAGTypeLegalizer::RemapValue(
SDValue &V) {
579 auto Id = getTableId(V);
583void DAGTypeLegalizer::RemapId(TableId &Id) {
584 auto I = ReplacedValues.find(Id);
585 if (
I != ReplacedValues.end()) {
586 assert(Id !=
I->second &&
"Id is mapped to itself.");
608 DTL(dtl), NodesToAnalyze(nta) {}
613 "Invalid node ID for RAUW deletion!");
616 assert(
E &&
"Node not replaced?");
631 void NodeUpdated(
SDNode *
N)
override {
637 "Invalid node ID for RAUW deletion!");
656 NodeUpdateListener NUL(*
this, NodesToAnalyze);
661 auto FromId = getTableId(
From);
662 auto ToId = getTableId(To);
665 ReplacedValues[FromId] = ToId;
669 while (!NodesToAnalyze.
empty()) {
682 assert(
M->getNodeId() !=
NewNode &&
"Analysis resulted in NewNode!");
683 assert(
N->getNumValues() ==
M->getNumValues() &&
684 "Node morphing changed the number of results!");
685 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
694 auto OldValId = getTableId(OldVal);
695 auto NewValId = getTableId(NewVal);
697 if (OldValId != NewValId)
698 ReplacedValues[OldValId] = NewValId;
706 }
while (!
From.use_empty());
709void DAGTypeLegalizer::SetPromotedInteger(
SDValue Op,
SDValue Result) {
712 "Invalid type for promoted integer");
713 AnalyzeNewValue(Result);
715 auto &OpIdEntry = PromotedIntegers[getTableId(Op)];
716 assert((OpIdEntry == 0) &&
"Node is already promoted!");
717 OpIdEntry = getTableId(Result);
723void DAGTypeLegalizer::SetSoftenedFloat(
SDValue Op,
SDValue Result) {
729 "Invalid type for softened float");
731 AnalyzeNewValue(Result);
733 auto &OpIdEntry = SoftenedFloats[getTableId(Op)];
734 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
735 OpIdEntry = getTableId(Result);
738void DAGTypeLegalizer::SetPromotedFloat(
SDValue Op,
SDValue Result) {
741 "Invalid type for promoted float");
742 AnalyzeNewValue(Result);
744 auto &OpIdEntry = PromotedFloats[getTableId(Op)];
745 assert((OpIdEntry == 0) &&
"Node is already promoted!");
746 OpIdEntry = getTableId(Result);
749void DAGTypeLegalizer::SetSoftPromotedHalf(
SDValue Op,
SDValue Result) {
751 "Invalid type for soft-promoted half");
752 AnalyzeNewValue(Result);
754 auto &OpIdEntry = SoftPromotedHalfs[getTableId(Op)];
755 assert((OpIdEntry == 0) &&
"Node is already promoted!");
756 OpIdEntry = getTableId(Result);
759void DAGTypeLegalizer::SetScalarizedVector(
SDValue Op,
SDValue Result) {
766 Op.getScalarValueSizeInBits() &&
767 "Invalid type for scalarized vector");
768 AnalyzeNewValue(Result);
770 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)];
771 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
772 OpIdEntry = getTableId(Result);
777 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
778 assert((Entry.first != 0) &&
"Operand isn't expanded");
779 Lo = getSDValue(Entry.first);
780 Hi = getSDValue(Entry.second);
787 Hi.getValueType() ==
Lo.getValueType() &&
788 "Invalid type for expanded integer");
798 Lo.getValueSizeInBits());
802 Hi.getValueSizeInBits());
806 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
807 assert((Entry.first == 0) &&
"Node already expanded");
808 Entry.first = getTableId(
Lo);
809 Entry.second = getTableId(
Hi);
814 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
815 assert((Entry.first != 0) &&
"Operand isn't expanded");
816 Lo = getSDValue(Entry.first);
817 Hi = getSDValue(Entry.second);
824 Hi.getValueType() ==
Lo.getValueType() &&
825 "Invalid type for expanded float");
830 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
831 assert((Entry.first == 0) &&
"Node already expanded");
832 Entry.first = getTableId(
Lo);
833 Entry.second = getTableId(
Hi);
838 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
839 Lo = getSDValue(Entry.first);
840 Hi = getSDValue(Entry.second);
841 assert(
Lo.getNode() &&
"Operand isn't split");
847 assert(
Lo.getValueType().getVectorElementType() ==
848 Op.getValueType().getVectorElementType() &&
849 Lo.getValueType().getVectorElementCount() * 2 ==
850 Op.getValueType().getVectorElementCount() &&
851 Hi.getValueType() ==
Lo.getValueType() &&
852 "Invalid type for split vector");
858 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
859 assert((Entry.first == 0) &&
"Node already split");
860 Entry.first = getTableId(
Lo);
861 Entry.second = getTableId(
Hi);
864void DAGTypeLegalizer::SetWidenedVector(
SDValue Op,
SDValue Result) {
867 "Invalid type for widened vector");
868 AnalyzeNewValue(Result);
870 auto &OpIdEntry = WidenedVectors[getTableId(Op)];
871 assert((OpIdEntry == 0) &&
"Node already widened!");
872 OpIdEntry = getTableId(Result);
888SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(
SDValue Op) {
889 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
890 unsigned EltWidth =
Op.getScalarValueSizeInBits();
892 auto EltCnt =
Op.getValueType().getVectorElementCount();
925bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
942 "Custom lowering returned the wrong number of results!");
943 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
952bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
966 "Custom lowering returned the wrong number of results!");
967 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
978SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
979 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
982 return SDValue(
N->getOperand(ResNo));
987void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
999 EVT LVT =
Lo.getValueType();
1000 EVT HVT =
Hi.getValueType();
1022void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1027 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1029 unsigned ReqShiftAmountInBits =
1042void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1046 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 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.
std::pair< SDValue, SDValue > SplitScalar(const SDValue &N, const SDLoc &DL, const EVT &LoVT, const EVT &HiVT)
Split the scalar node with EXTRACT_ELEMENT using the provided VTs and return the low/high part.
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.
value_type pop_back_val()
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...
@ 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.
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.