aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/SelectionDAG
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG')
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp39
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp15
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp25
3 files changed, 67 insertions, 12 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 95f53fe..6ea2e27 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -12698,6 +12698,45 @@ unsigned SelectionDAG::AssignTopologicalOrder() {
return DAGSize;
}
+void SelectionDAG::getTopologicallyOrderedNodes(
+ SmallVectorImpl<const SDNode *> &SortedNodes) const {
+ SortedNodes.clear();
+ // Node -> remaining number of outstanding operands.
+ DenseMap<const SDNode *, unsigned> RemainingOperands;
+
+ // Put nodes without any operands into SortedNodes first.
+ for (const SDNode &N : allnodes()) {
+ checkForCycles(&N, this);
+ unsigned NumOperands = N.getNumOperands();
+ if (NumOperands == 0)
+ SortedNodes.push_back(&N);
+ else
+ // Record their total number of outstanding operands.
+ RemainingOperands[&N] = NumOperands;
+ }
+
+ // A node is pushed into SortedNodes when all of its operands (predecessors in
+ // the graph) are also in SortedNodes.
+ for (unsigned i = 0U; i < SortedNodes.size(); ++i) {
+ const SDNode *N = SortedNodes[i];
+ for (const SDNode *U : N->users()) {
+ unsigned &NumRemOperands = RemainingOperands[U];
+ assert(NumRemOperands && "Invalid number of remaining operands");
+ --NumRemOperands;
+ if (!NumRemOperands)
+ SortedNodes.push_back(U);
+ }
+ }
+
+ assert(SortedNodes.size() == AllNodes.size() && "Node count mismatch");
+ assert(SortedNodes.front()->getOpcode() == ISD::EntryToken &&
+ "First node in topological sort is not the entry token");
+ assert(SortedNodes.front()->getNumOperands() == 0 &&
+ "First node in topological sort has operands");
+ assert(SortedNodes.back()->use_empty() &&
+ "Last node in topologic sort has users");
+}
+
/// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
/// value is produced by SD.
void SelectionDAG::AddDbgValue(SDDbgValue *DB, bool isParameter) {
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
index 4b2a00c..fcfbfe6 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
@@ -1061,13 +1061,24 @@ static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
N->dump(G);
}
-LLVM_DUMP_METHOD void SelectionDAG::dump() const {
+LLVM_DUMP_METHOD void SelectionDAG::dump(bool Sorted) const {
dbgs() << "SelectionDAG has " << AllNodes.size() << " nodes:\n";
- for (const SDNode &N : allnodes()) {
+ auto dumpEachNode = [this](const SDNode &N) {
if (!N.hasOneUse() && &N != getRoot().getNode() &&
(!shouldPrintInline(N, this) || N.use_empty()))
DumpNodes(&N, 2, this);
+ };
+
+ if (Sorted) {
+ SmallVector<const SDNode *> SortedNodes;
+ SortedNodes.reserve(AllNodes.size());
+ getTopologicallyOrderedNodes(SortedNodes);
+ for (const SDNode *N : SortedNodes)
+ dumpEachNode(*N);
+ } else {
+ for (const SDNode &N : allnodes())
+ dumpEachNode(N);
}
if (getRoot().getNode()) DumpNodes(getRoot().getNode(), 2, this);
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index e61558c..c35f29d 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -144,6 +144,11 @@ UseMBPI("use-mbpi",
cl::init(true), cl::Hidden);
#ifndef NDEBUG
+static cl::opt<bool>
+ DumpSortedDAG("dump-sorted-dags", cl::Hidden,
+ cl::desc("Print DAGs with sorted nodes in debug dump"),
+ cl::init(false));
+
static cl::opt<std::string>
FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
cl::desc("Only display the basic block whose name "
@@ -932,7 +937,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nInitial selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -952,7 +957,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nOptimized lowered selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -974,7 +979,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nType-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -998,7 +1003,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nOptimized type-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1016,7 +1021,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nVector-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1032,7 +1037,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nVector/type-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1052,7 +1057,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nOptimized vector-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1072,7 +1077,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nLegalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1092,7 +1097,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nOptimized legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
if (TTI->hasBranchDivergence())
@@ -1116,7 +1121,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() {
ISEL_DUMP(dbgs() << "\nSelected selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
- CurDAG->dump());
+ CurDAG->dump(DumpSortedDAG));
if (ViewSchedDAGs && MatchFilterBB)
CurDAG->viewGraph("scheduler input for " + BlockName);
generated by cgit v1.1 at 2025-10-04 15:12:58 +0000