Changes in directory llvm/lib/CodeGen/SelectionDAG:
SelectionDAG.cpp updated: 1.314 -> 1.315
---
Log message:
Added AssignTopologicalOrder() to assign each node an unique id based on their
topological order.
---
Diffs of the changes: (+38 -2)
SelectionDAG.cpp | 40 ++++++++++++++++++++++++++++++++++++++--
1 files changed, 38 insertions(+), 2 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.314
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.315
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.314 Thu Jul 27
19:45:53 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp Tue Aug 1 03:20:41 2006
@@ -28,6 +28,7 @@
#include <set>
#include <cmath>
#include <algorithm>
+#include <deque>
using namespace llvm;
static bool isCommutativeBinOp(unsigned Opcode) {
@@ -2698,8 +2699,8 @@
}
-/// AssignNodeIds - Assign a unique node id for each node in the DAG. It
returns
-/// the maximum id.
+/// AssignNodeIds - Assign a unique node id for each node in the DAG based on
+/// their allnodes order. It returns the maximum id.
unsigned SelectionDAG::AssignNodeIds() {
unsigned Id = 0;
for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E;
++I){
@@ -2709,6 +2710,41 @@
return Id;
}
+/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
+/// based on their topological order. It returns a vector of the SDNodes* in
+/// assigned order.
+std::vector<SDNode*> SelectionDAG::AssignTopologicalOrder() {
+ unsigned DAGSize = AllNodes.size();
+ std::vector<SDNode*> TopOrder;
+ std::map<SDNode*, unsigned> InDegree;
+ std::deque<SDNode*> Sources;
+ for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
+ SDNode *N = I;
+ unsigned Degree = N->use_size();
+ InDegree[N] = Degree;
+ if (Degree == 0)
+ Sources.push_back(I);
+ }
+
+ int Id = 0;
+ while (!Sources.empty()) {
+ SDNode *N = Sources.front();
+ Sources.pop_front();
+ TopOrder.push_back(N);
+ N->setNodeId(Id++);
+ for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
+ SDNode *P = I->Val;
+ unsigned Degree = InDegree[P] - 1;
+ if (Degree == 0)
+ Sources.push_back(P);
+ InDegree[P] = Degree;
+ }
+ }
+
+ return TopOrder;
+}
+
+
//===----------------------------------------------------------------------===//
// SDNode Class
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
