24#define DEBUG_TYPE "legalize-types"
27void DAGTypeLegalizer::PerformExpensiveChecks() {
77 for (
unsigned i = 0, e =
Node.getNumValues(); i != e; ++i) {
81 auto ResId = ValueToIdMap.lookup(Res);
85 auto I = ReplacedValues.find(ResId);
86 if (
I != ReplacedValues.end()) {
90 if (U.getResNo() == i)
92 "Remapped value has non-trivial use!");
96 auto NewValId =
I->second;
97 I = ReplacedValues.find(NewValId);
98 while (
I != ReplacedValues.end()) {
100 I = ReplacedValues.find(NewValId);
102 SDValue NewVal = getSDValue(NewValId);
105 "ReplacedValues maps to a new node!");
107 if (PromotedIntegers.count(ResId))
109 if (SoftenedFloats.count(ResId))
111 if (ScalarizedVectors.count(ResId))
113 if (ExpandedIntegers.count(ResId))
115 if (ExpandedFloats.count(ResId))
117 if (SplitVectors.count(ResId))
119 if (WidenedVectors.count(ResId))
121 if (SoftPromotedHalfs.count(ResId))
131 dbgs() <<
"Unprocessed value in a map!";
136 dbgs() <<
"Value with legal type was transformed!";
141 SDValue NodeById = IdToValueMap.lookup(ResId);
148 dbgs() <<
"Processed value not in any map!";
151 }
else if (Mapped & (Mapped - 1)) {
152 dbgs() <<
"Value in multiple maps!";
159 dbgs() <<
" ReplacedValues";
161 dbgs() <<
" PromotedIntegers";
163 dbgs() <<
" SoftenedFloats";
165 dbgs() <<
" ScalarizedVectors";
167 dbgs() <<
" ExpandedIntegers";
169 dbgs() <<
" ExpandedFloats";
171 dbgs() <<
" SplitVectors";
173 dbgs() <<
" WidenedVectors";
175 dbgs() <<
" SoftPromoteHalfs";
186 assert(U->getNodeId() ==
NewNode &&
"NewNode used by non-NewNode!");
211 if (
Node.getNumOperands() == 0) {
213 Worklist.push_back(&
Node);
220 while (!Worklist.empty()) {
221#ifndef EXPENSIVE_CHECKS
222 if (DAG.getSelectionDAGOptions().enable_legalize_types_checking)
224 PerformExpensiveChecks();
226 SDNode *
N = Worklist.pop_back_val();
228 "Node should be ready if on worklist!");
235 if (IgnoreNodeResults(
N)) {
242 for (
unsigned i = 0, NumResults =
N->getNumValues(); i < NumResults; ++i) {
243 EVT ResultVT =
N->getValueType(i);
244 LLVM_DEBUG(
dbgs() <<
"Analyzing result type: " << ResultVT <<
"\n");
245 switch (getTypeAction(ResultVT)) {
251 "scalarization of scalable vectors is not supported");
258 PromoteIntegerResult(
N, i);
262 ExpandIntegerResult(
N, i);
266 SoftenFloatResult(
N, i);
270 ExpandFloatResult(
N, i);
274 ScalarizeVectorResult(
N, i);
278 SplitVectorResult(
N, i);
282 WidenVectorResult(
N, i);
286 SoftPromoteHalfResult(
N, i);
296 unsigned NumOperands =
N->getNumOperands();
297 bool NeedsReanalyzing =
false;
299 for (i = 0; i != NumOperands; ++i) {
300 if (IgnoreNodeResults(
N->getOperand(i).getNode()))
303 const auto &
Op =
N->getOperand(i);
305 EVT OpVT =
Op.getValueType();
306 switch (getTypeAction(OpVT)) {
312 "scalarization of scalable vectors is not supported");
317 NeedsReanalyzing = PromoteIntegerOperand(
N, i);
321 NeedsReanalyzing = ExpandIntegerOperand(
N, i);
325 NeedsReanalyzing = SoftenFloatOperand(
N, i);
329 NeedsReanalyzing = ExpandFloatOperand(
N, i);
333 NeedsReanalyzing = ScalarizeVectorOperand(
N, i);
337 NeedsReanalyzing = SplitVectorOperand(
N, i);
341 NeedsReanalyzing = WidenVectorOperand(
N, i);
345 NeedsReanalyzing = SoftPromoteHalfOperand(
N, i);
355 if (NeedsReanalyzing) {
368 assert(
N->getNumValues() == M->getNumValues() &&
369 "Node morphing changed the number of results!");
370 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
380 if (i == NumOperands) {
392 int NodeId =
User->getNodeId();
397 User->setNodeId(NodeId-1);
401 Worklist.push_back(
User);
419 Worklist.push_back(
User);
423#ifndef EXPENSIVE_CHECKS
424 if (DAG.getSelectionDAGOptions().enable_legalize_types_checking)
426 PerformExpensiveChecks();
435 DAG.RemoveDeadNodes();
444 if (!IgnoreNodeResults(&
Node))
445 for (
unsigned i = 0, NumVals =
Node.getNumValues(); i < NumVals; ++i)
446 if (!isTypeLegal(
Node.getValueType(i))) {
447 dbgs() <<
"Result type " << i <<
" illegal: ";
454 if (!IgnoreNodeResults(
Node.getOperand(i).getNode()) &&
455 !isTypeLegal(
Node.getOperand(i).getValueType())) {
456 dbgs() <<
"Operand type " << i <<
" illegal: ";
463 dbgs() <<
"New node not analyzed?\n";
465 dbgs() <<
"Unanalyzed node not noticed?\n";
466 else if (
Node.getNodeId() > 0)
467 dbgs() <<
"Operand not processed?\n";
469 dbgs() <<
"Not added to worklist?\n";
503 std::vector<SDValue> NewOps;
504 unsigned NumProcessed = 0;
505 for (
unsigned i = 0, e =
N->getNumOperands(); i != e; ++i) {
514 if (!NewOps.empty()) {
516 NewOps.push_back(
Op);
517 }
else if (
Op != OrigOp) {
520 NewOps.push_back(
Op);
525 if (!NewOps.empty()) {
526 SDNode *
M = DAG.UpdateNodeOperands(
N, NewOps);
547 N->setNodeId(
N->getNumOperands() - NumProcessed);
549 Worklist.push_back(
N);
556void DAGTypeLegalizer::AnalyzeNewValue(
SDValue &Val) {
565void DAGTypeLegalizer::RemapValue(
SDValue &
V) {
566 auto Id = getTableId(
V);
567 SDValue Mapped = getSDValue(Id);
568 if (
V && Mapped &&
V.getNode() != Mapped.
getNode())
573void DAGTypeLegalizer::RemapId(TableId &Id) {
574 auto I = ReplacedValues.find(Id);
575 if (
I != ReplacedValues.end()) {
576 assert(Id !=
I->second &&
"Id is mapped to itself.");
592 DAGTypeLegalizer &DTL;
593 SmallSetVector<SDNode*, 16> &NodesToAnalyze;
595 explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
596 SmallSetVector<SDNode*, 16> &nta)
597 : SelectionDAG::DAGUpdateListener(dtl.getDAG()),
598 DTL(dtl), NodesToAnalyze(nta) {}
600 void NodeDeleted(SDNode *
N, SDNode *
E)
override {
603 "Invalid node ID for RAUW deletion!");
606 assert(
E &&
"Node not replaced?");
621 void NodeUpdated(SDNode *
N)
override {
627 "Invalid node ID for RAUW deletion!");
637void DAGTypeLegalizer::ReplaceValueWith(
SDValue From,
SDValue To) {
645 SmallSetVector<SDNode*, 16> NodesToAnalyze;
646 NodeUpdateListener NUL(*
this, NodesToAnalyze);
651 auto FromId = getTableId(From);
652 auto ToId = getTableId(To);
655 ReplacedValues[FromId] = ToId;
656 DAG.ReplaceAllUsesOfValueWith(From, To);
659 while (!NodesToAnalyze.
empty()) {
668 SDNode *
M = AnalyzeNewNode(
N);
672 assert(
M->getNodeId() !=
NewNode &&
"Analysis resulted in NewNode!");
673 assert(
N->getNumValues() ==
M->getNumValues() &&
674 "Node morphing changed the number of results!");
675 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
684 auto OldValId = getTableId(OldVal);
685 auto NewValId = getTableId(NewVal);
686 DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
693 if (OldValId != NewValId)
694 ReplacedValues[OldValId] = NewValId;
707 TLI.getTypeToTransformTo(*DAG.getContext(),
Op.getValueType()) &&
708 "Invalid type for promoted integer");
709 AnalyzeNewValue(Result);
711 auto &OpIdEntry = PromotedIntegers[getTableId(
Op)];
712 assert((OpIdEntry == 0) &&
"Node is already promoted!");
713 OpIdEntry = getTableId(Result);
715 DAG.transferDbgValues(
Op, Result);
720 EVT VT =
Result.getValueType();
721 LLVMContext &Ctx = *DAG.getContext();
723 VT == TLI.getTypeToTransformTo(Ctx,
Op.getValueType())) &&
724 "Invalid type for softened float");
726 AnalyzeNewValue(Result);
728 auto &OpIdEntry = SoftenedFloats[getTableId(
Op)];
729 assert((OpIdEntry == 0) &&
"Node is already converted to integer!");
730 OpIdEntry = getTableId(Result);
735 "Invalid type for soft-promoted half");
736 AnalyzeNewValue(Result);
738 auto &OpIdEntry = SoftPromotedHalfs[getTableId(
Op)];
739 assert((OpIdEntry == 0) &&
"Node is already promoted!");
740 OpIdEntry = getTableId(Result);
750 Op.getScalarValueSizeInBits() &&
751 "Invalid type for scalarized vector");
752 AnalyzeNewValue(Result);
754 auto &OpIdEntry = ScalarizedVectors[getTableId(
Op)];
755 assert((OpIdEntry == 0) &&
"Node is already scalarized!");
756 OpIdEntry = getTableId(Result);
761 std::pair<TableId, TableId> &
Entry = ExpandedIntegers[getTableId(
Op)];
762 assert((
Entry.first != 0) &&
"Operand isn't expanded");
770 TLI.getTypeToTransformTo(*DAG.getContext(),
Op.getValueType()) &&
771 Hi.getValueType() ==
Lo.getValueType() &&
772 "Invalid type for expanded integer");
779 if (DAG.getDataLayout().isBigEndian()) {
780 DAG.transferDbgValues(
Op,
Hi, 0,
Hi.getValueSizeInBits(),
false);
781 DAG.transferDbgValues(
Op,
Lo,
Hi.getValueSizeInBits(),
782 Lo.getValueSizeInBits());
784 DAG.transferDbgValues(
Op,
Lo, 0,
Lo.getValueSizeInBits(),
false);
785 DAG.transferDbgValues(
Op,
Hi,
Lo.getValueSizeInBits(),
786 Hi.getValueSizeInBits());
790 std::pair<TableId, TableId> &
Entry = ExpandedIntegers[getTableId(
Op)];
791 assert((
Entry.first == 0) &&
"Node already expanded");
798 std::pair<TableId, TableId> &
Entry = ExpandedFloats[getTableId(
Op)];
799 assert((
Entry.first != 0) &&
"Operand isn't expanded");
807 TLI.getTypeToTransformTo(*DAG.getContext(),
Op.getValueType()) &&
808 Hi.getValueType() ==
Lo.getValueType() &&
809 "Invalid type for expanded float");
814 std::pair<TableId, TableId> &
Entry = ExpandedFloats[getTableId(
Op)];
815 assert((
Entry.first == 0) &&
"Node already expanded");
822 std::pair<TableId, TableId> &
Entry = SplitVectors[getTableId(
Op)];
825 assert(
Lo.getNode() &&
"Operand isn't split");
831 assert(
Lo.getValueType().getVectorElementType() ==
832 Op.getValueType().getVectorElementType() &&
833 Lo.getValueType().getVectorElementCount() * 2 ==
834 Op.getValueType().getVectorElementCount() &&
835 Hi.getValueType() ==
Lo.getValueType() &&
836 "Invalid type for split vector");
842 std::pair<TableId, TableId> &
Entry = SplitVectors[getTableId(
Op)];
843 assert((
Entry.first == 0) &&
"Node already split");
850 TLI.getTypeToTransformTo(*DAG.getContext(),
Op.getValueType()) &&
851 "Invalid type for widened vector");
852 AnalyzeNewValue(Result);
854 auto &OpIdEntry = WidenedVectors[getTableId(
Op)];
855 assert((OpIdEntry == 0) &&
"Node already widened!");
856 OpIdEntry = getTableId(Result);
873 assert(
Op.getValueType().isVector() &&
"Only applies to vectors!");
874 unsigned EltWidth =
Op.getScalarValueSizeInBits();
876 auto EltCnt =
Op.getValueType().getVectorElementCount();
889 Align DestAlign = DAG.getReducedAlign(DestVT,
false);
890 Align OpAlign = DAG.getReducedAlign(
Op.getValueType(),
false);
893 DAG.CreateStackTemporary(
Op.getValueType().getStoreSize(), Align);
895 SDValue Store = DAG.getStore(DAG.getEntryNode(), dl,
Op, StackPtr,
896 MachinePointerInfo(), Align);
898 return DAG.getLoad(DestVT, dl,
Store, StackPtr, MachinePointerInfo(), Align);
909bool DAGTypeLegalizer::CustomLowerNode(
SDNode *
N,
EVT VT,
bool LegalizeResult) {
916 TLI.ReplaceNodeResults(
N,
Results, DAG);
918 TLI.LowerOperationWrapper(
N,
Results, DAG);
926 "Custom lowering returned the wrong number of results!");
927 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
936bool DAGTypeLegalizer::CustomWidenLowerNode(
SDNode *
N,
EVT VT) {
942 TLI.ReplaceNodeResults(
N,
Results, DAG);
950 "Custom lowering returned the wrong number of results!");
951 for (
unsigned i = 0, e =
Results.
size(); i != e; ++i) {
962SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(
SDNode *
N,
unsigned ResNo) {
963 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i)
966 return SDValue(
N->getOperand(ResNo));
971void DAGTypeLegalizer::GetPairElements(
SDValue Pair,
974 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.
getValueType());
975 std::tie(
Lo,
Hi) = DAG.SplitScalar(Pair, dl, NVT, NVT);
983 EVT LVT =
Lo.getValueType();
984 EVT HVT =
Hi.getValueType();
1001 return TLI.promoteTargetBoolean(DAG, Bool, ValVT);
1005void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1010 Op.getValueSizeInBits() &&
"Invalid integer splitting!");
1014 DAG.getShiftAmountConstant(LoVT.
getSizeInBits(),
Op.getValueType(), dl));
1020void DAGTypeLegalizer::SplitInteger(
SDValue Op,
1024 SplitInteger(
Op, HalfVT, HalfVT,
Lo,
Hi);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Function Alias Analysis Results
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
This file implements a set that has insertion order iteration characteristics.
DEMANGLE_DUMP_METHOD void dump() const
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.
Convenience struct for specifying and reasoning about fast-math flags.
Type * getValueType() const
This class is used to form a handle around another node that is persistent and is updated across invo...
const SDValue & getValue() const
Represents one node in the SelectionDAG.
int getNodeId() const
Return the unique node id.
void setNodeId(int Id)
Set unique node id.
LLVM_ABI void intersectFlagsWith(const SDNodeFlags Flags)
Clear any flags in this node that aren't also set in Flags.
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.
bool use_empty() const
Return true if there are no nodes using value ResNo of Node.
void setNode(SDNode *N)
set the SDNode
Help to insert SDNodeFlags automatically in transforming.
iterator_range< allnodes_iterator > allnodes()
LLVM_ABI 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()
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
@ TypeScalarizeScalableVector
unsigned getNumOperands() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
@ 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.
@ Store
The extracted value is stored (ExtractElement only).
testing::Matcher< const detail::ErrorHolder & > Failed()
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
DWARFExpression::Operation Op
constexpr unsigned BitWidth
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.
These are IR-level optimization flags that may be propagated to SDNodes.
Clients of various APIs that cause global effects on the DAG can optionally implement this interface.