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) {
404 int NodeId =
User->getNodeId();
409 User->setNodeId(NodeId-1);
413 Worklist.push_back(
User);
431 Worklist.push_back(
User);
435#ifndef EXPENSIVE_CHECKS
438 PerformExpensiveChecks();
456 if (!IgnoreNodeResults(&Node))
457 for (
unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
458 if (!isTypeLegal(Node.getValueType(i))) {
459 dbgs() <<
"Result type " << i <<
" illegal: ";
465 for (
unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
466 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
467 !isTypeLegal(Node.getOperand(i).getValueType())) {
468 dbgs() <<
"Operand type " << i <<
" illegal: ";
469 Node.getOperand(i).dump(&DAG);
474 if (Node.getNodeId() ==
NewNode)
475 dbgs() <<
"New node not analyzed?\n";
477 dbgs() <<
"Unanalyzed node not noticed?\n";
478 else if (Node.getNodeId() > 0)
479 dbgs() <<
"Operand not processed?\n";
481 dbgs() <<
"Not added to worklist?\n";
486 Node.dump(&DAG);
dbgs() <<
"\n";
515 std::vector<SDValue> NewOps;
516 unsigned NumProcessed = 0;
517 for (
unsigned i = 0, e =
N->getNumOperands(); i != e; ++i) {
526 if (!NewOps.empty()) {
528 NewOps.push_back(
Op);
529 }
else if (
Op != OrigOp) {
531 NewOps.insert(NewOps.end(),
N->op_begin(),
N->op_begin() + i);
532 NewOps.push_back(
Op);
537 if (!NewOps.empty()) {
559 N->setNodeId(
N->getNumOperands() - NumProcessed);
561 Worklist.push_back(
N);
568void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
577void DAGTypeLegalizer::RemapValue(
SDValue &V) {
578 auto Id = getTableId(V);
582void DAGTypeLegalizer::RemapId(TableId &Id) {
583 auto I = ReplacedValues.find(Id);
584 if (
I != ReplacedValues.end()) {
585 assert(Id !=
I->second &&
"Id is mapped to itself.");
607 DTL(dtl), NodesToAnalyze(nta) {}
612 "Invalid node ID for RAUW deletion!");
615 assert(
E &&
"Node not replaced?");
630 void NodeUpdated(
SDNode *
N)
override {
636 "Invalid node ID for RAUW deletion!");
655 NodeUpdateListener NUL(*
this, NodesToAnalyze);
660 auto FromId = getTableId(
From);
661 auto ToId = getTableId(To);
664 ReplacedValues[FromId] = ToId;
668 while (!NodesToAnalyze.
empty()) {
681 assert(
M->getNodeId() !=
NewNode &&
"Analysis resulted in NewNode!");
682 assert(
N->getNumValues() ==
M->getNumValues() &&
683 "Node morphing changed the number of results!");
684 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
693 auto OldValId = getTableId(OldVal);
694 auto NewValId = getTableId(NewVal);
696 if (OldValId != NewValId)
697 ReplacedValues[OldValId] = NewValId;
705 }
while (!
From.use_empty());
711 "Invalid type for promoted integer");
712 AnalyzeNewValue(Result);
714 auto &OpIdEntry = PromotedIntegers[getTableId(
Op)];
715 assert((OpIdEntry == 0) &&
"Node is already promoted!");
716 OpIdEntry = getTableId(Result);
727 "Invalid type for softened float");
729 AnalyzeNewValue(Result);
731 auto &OpIdEntry = SoftenedFloats[getTableId(
Op)];
732 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
733 OpIdEntry = getTableId(Result);
739 "Invalid type for promoted float");
740 AnalyzeNewValue(Result);
742 auto &OpIdEntry = PromotedFloats[getTableId(
Op)];
743 assert((OpIdEntry == 0) &&
"Node is already promoted!");
744 OpIdEntry = getTableId(Result);
749 "Invalid type for soft-promoted half");
750 AnalyzeNewValue(Result);
752 auto &OpIdEntry = SoftPromotedHalfs[getTableId(
Op)];
753 assert((OpIdEntry == 0) &&
"Node is already promoted!");
754 OpIdEntry = getTableId(Result);
764 Op.getScalarValueSizeInBits() &&
765 "Invalid type for scalarized vector");
766 AnalyzeNewValue(Result);
768 auto &OpIdEntry = ScalarizedVectors[getTableId(
Op)];
769 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
770 OpIdEntry = getTableId(Result);
775 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
776 assert((Entry.first != 0) &&
"Operand isn't expanded");
777 Lo = getSDValue(Entry.first);
778 Hi = getSDValue(Entry.second);
785 Hi.getValueType() ==
Lo.getValueType() &&
786 "Invalid type for expanded integer");
796 Lo.getValueSizeInBits());
800 Hi.getValueSizeInBits());
804 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(
Op)];
805 assert((Entry.first == 0) &&
"Node already expanded");
806 Entry.first = getTableId(
Lo);
807 Entry.second = getTableId(
Hi);
812 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
813 assert((Entry.first != 0) &&
"Operand isn't expanded");
814 Lo = getSDValue(Entry.first);
815 Hi = getSDValue(Entry.second);
822 Hi.getValueType() ==
Lo.getValueType() &&
823 "Invalid type for expanded float");
828 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(
Op)];
829 assert((Entry.first == 0) &&
"Node already expanded");
830 Entry.first = getTableId(
Lo);
831 Entry.second = getTableId(
Hi);
836 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
837 Lo = getSDValue(Entry.first);
838 Hi = getSDValue(Entry.second);
839 assert(
Lo.getNode() &&
"Operand isn't split");
845 assert(
Lo.getValueType().getVectorElementType() ==
846 Op.getValueType().getVectorElementType() &&
847 Lo.getValueType().getVectorElementCount() * 2 ==
848 Op.getValueType().getVectorElementCount() &&
849 Hi.getValueType() ==
Lo.getValueType() &&
850 "Invalid type for split vector");
856 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(
Op)];
857 assert((Entry.first == 0) &&
"Node already split");
858 Entry.first = getTableId(
Lo);
859 Entry.second = getTableId(
Hi);
865 "Invalid type for widened vector");
866 AnalyzeNewValue(Result);
868 auto &OpIdEntry = WidenedVectors[getTableId(
Op)];
869 assert((OpIdEntry == 0) &&
"Node already widened!");
870 OpIdEntry = getTableId(Result);
887 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
888 unsigned EltWidth =
Op.getScalarValueSizeInBits();
890 auto EltCnt =
Op.getValueType().getVectorElementCount();
923bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
940 "Custom lowering returned the wrong number of results!");
941 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
950bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
964 "Custom lowering returned the wrong number of results!");
965 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
976SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
977 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
980 return SDValue(
N->getOperand(ResNo));
985void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
997 EVT LVT =
Lo.getValueType();
998 EVT HVT =
Hi.getValueType();
1020void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1025 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1027 unsigned ReqShiftAmountInBits =
1040void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1044 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.
This class represents an Operation in the Expression.
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 empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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.