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);
722void DAGTypeLegalizer::SetSoftenedFloat(
SDValue Op,
SDValue Result) {
728 "Invalid type for softened float");
730 AnalyzeNewValue(Result);
732 auto &OpIdEntry = SoftenedFloats[getTableId(Op)];
733 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
734 OpIdEntry = getTableId(Result);
737void DAGTypeLegalizer::SetPromotedFloat(
SDValue Op,
SDValue Result) {
740 "Invalid type for promoted float");
741 AnalyzeNewValue(Result);
743 auto &OpIdEntry = PromotedFloats[getTableId(Op)];
744 assert((OpIdEntry == 0) &&
"Node is already promoted!");
745 OpIdEntry = getTableId(Result);
748void DAGTypeLegalizer::SetSoftPromotedHalf(
SDValue Op,
SDValue Result) {
750 "Invalid type for soft-promoted half");
751 AnalyzeNewValue(Result);
753 auto &OpIdEntry = SoftPromotedHalfs[getTableId(Op)];
754 assert((OpIdEntry == 0) &&
"Node is already promoted!");
755 OpIdEntry = getTableId(Result);
758void DAGTypeLegalizer::SetScalarizedVector(
SDValue Op,
SDValue Result) {
765 Op.getScalarValueSizeInBits() &&
766 "Invalid type for scalarized vector");
767 AnalyzeNewValue(Result);
769 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)];
770 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
771 OpIdEntry = getTableId(Result);
776 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
777 assert((Entry.first != 0) &&
"Operand isn't expanded");
778 Lo = getSDValue(Entry.first);
779 Hi = getSDValue(Entry.second);
786 Hi.getValueType() ==
Lo.getValueType() &&
787 "Invalid type for expanded integer");
797 Lo.getValueSizeInBits());
801 Hi.getValueSizeInBits());
805 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)];
806 assert((Entry.first == 0) &&
"Node already expanded");
807 Entry.first = getTableId(
Lo);
808 Entry.second = getTableId(
Hi);
813 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
814 assert((Entry.first != 0) &&
"Operand isn't expanded");
815 Lo = getSDValue(Entry.first);
816 Hi = getSDValue(Entry.second);
823 Hi.getValueType() ==
Lo.getValueType() &&
824 "Invalid type for expanded float");
829 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)];
830 assert((Entry.first == 0) &&
"Node already expanded");
831 Entry.first = getTableId(
Lo);
832 Entry.second = getTableId(
Hi);
837 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
838 Lo = getSDValue(Entry.first);
839 Hi = getSDValue(Entry.second);
840 assert(
Lo.getNode() &&
"Operand isn't split");
846 assert(
Lo.getValueType().getVectorElementType() ==
847 Op.getValueType().getVectorElementType() &&
848 Lo.getValueType().getVectorElementCount() * 2 ==
849 Op.getValueType().getVectorElementCount() &&
850 Hi.getValueType() ==
Lo.getValueType() &&
851 "Invalid type for split vector");
857 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)];
858 assert((Entry.first == 0) &&
"Node already split");
859 Entry.first = getTableId(
Lo);
860 Entry.second = getTableId(
Hi);
863void DAGTypeLegalizer::SetWidenedVector(
SDValue Op,
SDValue Result) {
866 "Invalid type for widened vector");
867 AnalyzeNewValue(Result);
869 auto &OpIdEntry = WidenedVectors[getTableId(Op)];
870 assert((OpIdEntry == 0) &&
"Node already widened!");
871 OpIdEntry = getTableId(Result);
887SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(
SDValue Op) {
888 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
889 unsigned EltWidth =
Op.getScalarValueSizeInBits();
891 auto EltCnt =
Op.getValueType().getVectorElementCount();
924bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
941 "Custom lowering returned the wrong number of results!");
942 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
951bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
965 "Custom lowering returned the wrong number of results!");
966 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
977SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
978 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
981 return SDValue(
N->getOperand(ResNo));
986void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
998 EVT LVT =
Lo.getValueType();
999 EVT HVT =
Hi.getValueType();
1021void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1026 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1028 unsigned ReqShiftAmountInBits =
1041void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1045 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.