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()) {
92 if (U.getResNo() == i)
94 "Remapped value has non-trivial use!");
98 auto NewValId =
I->second;
99 I = ReplacedValues.find(NewValId);
100 while (
I != ReplacedValues.end()) {
101 NewValId =
I->second;
102 I = ReplacedValues.find(NewValId);
104 SDValue NewVal = getSDValue(NewValId);
107 "ReplacedValues maps to a new node!");
109 if (PromotedIntegers.count(ResId))
111 if (SoftenedFloats.count(ResId))
113 if (ScalarizedVectors.count(ResId))
115 if (ExpandedIntegers.count(ResId))
117 if (ExpandedFloats.count(ResId))
119 if (SplitVectors.count(ResId))
121 if (WidenedVectors.count(ResId))
123 if (PromotedFloats.count(ResId))
125 if (SoftPromotedHalfs.count(ResId))
135 dbgs() <<
"Unprocessed value in a map!";
138 }
else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(&
Node)) {
140 dbgs() <<
"Value with legal type was transformed!";
145 SDValue NodeById = IdToValueMap.lookup(ResId);
152 dbgs() <<
"Processed value not in any map!";
155 }
else if (Mapped & (Mapped - 1)) {
156 dbgs() <<
"Value in multiple maps!";
163 dbgs() <<
" ReplacedValues";
165 dbgs() <<
" PromotedIntegers";
167 dbgs() <<
" SoftenedFloats";
169 dbgs() <<
" ScalarizedVectors";
171 dbgs() <<
" ExpandedIntegers";
173 dbgs() <<
" ExpandedFloats";
175 dbgs() <<
" SplitVectors";
177 dbgs() <<
" WidenedVectors";
179 dbgs() <<
" PromotedFloats";
181 dbgs() <<
" SoftPromoteHalfs";
192 assert(
U->getNodeId() ==
NewNode &&
"NewNode used by non-NewNode!");
201 bool Changed =
false;
217 if (Node.getNumOperands() == 0) {
219 Worklist.push_back(&Node);
226 while (!Worklist.empty()) {
227#ifndef EXPENSIVE_CHECKS
230 PerformExpensiveChecks();
232 SDNode *
N = Worklist.pop_back_val();
234 "Node should be ready if on worklist!");
237 if (IgnoreNodeResults(
N)) {
244 for (
unsigned i = 0, NumResults =
N->getNumValues(); i < NumResults; ++i) {
245 EVT ResultVT =
N->getValueType(i);
246 LLVM_DEBUG(
dbgs() <<
"Analyzing result type: " << ResultVT <<
"\n");
247 switch (getTypeAction(ResultVT)) {
253 "Scalarization of scalable vectors is not supported.");
260 PromoteIntegerResult(
N, i);
264 ExpandIntegerResult(
N, i);
268 SoftenFloatResult(
N, i);
272 ExpandFloatResult(
N, i);
276 ScalarizeVectorResult(
N, i);
280 SplitVectorResult(
N, i);
284 WidenVectorResult(
N, i);
288 PromoteFloatResult(
N, i);
292 SoftPromoteHalfResult(
N, i);
302 unsigned NumOperands =
N->getNumOperands();
303 bool NeedsReanalyzing =
false;
305 for (i = 0; i != NumOperands; ++i) {
306 if (IgnoreNodeResults(
N->getOperand(i).getNode()))
309 const auto &
Op =
N->getOperand(i);
311 EVT OpVT =
Op.getValueType();
312 switch (getTypeAction(OpVT)) {
318 "Scalarization of scalable vectors is not supported.");
323 NeedsReanalyzing = PromoteIntegerOperand(
N, i);
327 NeedsReanalyzing = ExpandIntegerOperand(
N, i);
331 NeedsReanalyzing = SoftenFloatOperand(
N, i);
335 NeedsReanalyzing = ExpandFloatOperand(
N, i);
339 NeedsReanalyzing = ScalarizeVectorOperand(
N, i);
343 NeedsReanalyzing = SplitVectorOperand(
N, i);
347 NeedsReanalyzing = WidenVectorOperand(
N, i);
351 NeedsReanalyzing = PromoteFloatOperand(
N, i);
355 NeedsReanalyzing = SoftPromoteHalfOperand(
N, i);
365 if (NeedsReanalyzing) {
378 assert(
N->getNumValues() == M->getNumValues() &&
379 "Node morphing changed the number of results!");
380 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
390 if (i == NumOperands) {
402 int NodeId =
User->getNodeId();
407 User->setNodeId(NodeId-1);
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()) {
557 N->setNodeId(
N->getNumOperands() - NumProcessed);
559 Worklist.push_back(
N);
566void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
575void DAGTypeLegalizer::RemapValue(
SDValue &V) {
576 auto Id = getTableId(V);
580void DAGTypeLegalizer::RemapId(TableId &Id) {
581 auto I = ReplacedValues.find(Id);
582 if (
I != ReplacedValues.end()) {
583 assert(Id !=
I->second &&
"Id is mapped to itself.");
605 DTL(dtl), NodesToAnalyze(nta) {}
610 "Invalid node ID for RAUW deletion!");
613 assert(
E &&
"Node not replaced?");
628 void NodeUpdated(
SDNode *
N)
override {
634 "Invalid node ID for RAUW deletion!");
653 NodeUpdateListener NUL(*
this, NodesToAnalyze);
658 auto FromId = getTableId(
From);
659 auto ToId = getTableId(To);
662 ReplacedValues[FromId] = ToId;
666 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);
725 "Invalid type for softened float");
727 AnalyzeNewValue(Result);
729 auto &OpIdEntry = SoftenedFloats[getTableId(
Op)];
730 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
731 OpIdEntry = getTableId(Result);
737 "Invalid type for promoted float");
738 AnalyzeNewValue(Result);
740 auto &OpIdEntry = PromotedFloats[getTableId(
Op)];
741 assert((OpIdEntry == 0) &&
"Node is already promoted!");
742 OpIdEntry = getTableId(Result);
747 "Invalid type for soft-promoted half");
748 AnalyzeNewValue(Result);
750 auto &OpIdEntry = SoftPromotedHalfs[getTableId(
Op)];
751 assert((OpIdEntry == 0) &&
"Node is already promoted!");
752 OpIdEntry = getTableId(Result);
762 Op.getScalarValueSizeInBits() &&
763 "Invalid type for scalarized vector");
764 AnalyzeNewValue(Result);
766 auto &OpIdEntry = ScalarizedVectors[getTableId(
Op)];
767 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
768 OpIdEntry = getTableId(Result);
773 std::pair<TableId, TableId> &
Entry = ExpandedIntegers[getTableId(
Op)];
774 assert((
Entry.first != 0) &&
"Operand isn't expanded");
783 Hi.getValueType() ==
Lo.getValueType() &&
784 "Invalid type for expanded integer");
794 Lo.getValueSizeInBits());
798 Hi.getValueSizeInBits());
802 std::pair<TableId, TableId> &
Entry = ExpandedIntegers[getTableId(
Op)];
803 assert((
Entry.first == 0) &&
"Node already expanded");
810 std::pair<TableId, TableId> &
Entry = ExpandedFloats[getTableId(
Op)];
811 assert((
Entry.first != 0) &&
"Operand isn't expanded");
820 Hi.getValueType() ==
Lo.getValueType() &&
821 "Invalid type for expanded float");
826 std::pair<TableId, TableId> &
Entry = ExpandedFloats[getTableId(
Op)];
827 assert((
Entry.first == 0) &&
"Node already expanded");
834 std::pair<TableId, TableId> &
Entry = SplitVectors[getTableId(
Op)];
837 assert(
Lo.getNode() &&
"Operand isn't split");
843 assert(
Lo.getValueType().getVectorElementType() ==
844 Op.getValueType().getVectorElementType() &&
845 Lo.getValueType().getVectorElementCount() * 2 ==
846 Op.getValueType().getVectorElementCount() &&
847 Hi.getValueType() ==
Lo.getValueType() &&
848 "Invalid type for split vector");
854 std::pair<TableId, TableId> &
Entry = SplitVectors[getTableId(
Op)];
855 assert((
Entry.first == 0) &&
"Node already split");
863 "Invalid type for widened vector");
864 AnalyzeNewValue(Result);
866 auto &OpIdEntry = WidenedVectors[getTableId(
Op)];
867 assert((OpIdEntry == 0) &&
"Node already widened!");
868 OpIdEntry = getTableId(Result);
885 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
886 unsigned EltWidth =
Op.getScalarValueSizeInBits();
888 auto EltCnt =
Op.getValueType().getVectorElementCount();
921bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
938 "Custom lowering returned the wrong number of results!");
939 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
948bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
962 "Custom lowering returned the wrong number of results!");
963 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
974SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
975 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
978 return SDValue(
N->getOperand(ResNo));
983void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
995 EVT LVT =
Lo.getValueType();
996 EVT HVT =
Hi.getValueType();
1018void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1023 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1025 unsigned ReqShiftAmountInBits =
1038void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1042 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...
Represents one node in the SelectionDAG.
int getNodeId() const
Return the unique node id.
Represents a use of a SDNode.
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) 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.