Issue 4865045: Generic topological sorting for graphs in llvm/ADT
Patch Set 1 #
Total comments: 41
Patch Set 2 : Generic topological sort, with style changes #
Total comments: 34
Patch Set 3 : Final changes to topological sort #
MessagesTotal messages: 6
Mostly style comments. This needs a pretty rigorous run through the LLVM coding standards. Also, looking at other code in LLVM might help. I've not looked at all at the test code, but I think the primary source code should get cleaned up first. Feel free to mail this patch at any point upstream and start getting feedback there as well. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort.h File include/llvm/ADT/TopologicalSort.h (right): http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:26: template<class GraphType, class IGT = IndexedGraphTraits<GraphType> > space after template, and I suspect we'll want to use 'typename' here instead of 'class'. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:31: // associate a depth with each node Comments should be complete sentences. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:32: struct NodeInfo { I might just forward declare this here, then provide the public interface, then go back and define them at the bottom in the private section. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:36: NodeInfo() : Node(NULL), Depth(-1) { } It's really unfortunate to make this class no longer a POD or an Aggregate. It might be worthwhile to design a setup where Depth can be zero in the "null" state. Also, use '0' not 'NULL' for pointers in LLVM and Clang. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:40: { } place the { on the previous line. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:54: // used within the sort() routine complete sentences http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:63: private: This is redundant in this particular location, but I would rotate most of this to the bottom of the class so that the public API comes first. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:68: // Perform a topological sort Complete sentence. Even better would likely be to not comment here, and provide a full doxygen comment below. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:72: explicit TopologicallySortedGraph(const GraphType& G) always attach '*' and '&' to the variable name (this applies to several places in this file) http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:76: { { on the previous line. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:102: inline iterator begin() { return iterator(NodeInfoVect.begin()); } No need for the inline keyword here or below. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:122: // An iterative algorithm is used to avoid stack overflow for large graphs. Doxygen comments please. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:128: std::vector<bool> Visited(NumNodes, false); No. no nononono. ;] vector<bool> is bad. have you read http://llvm.org/docs/ProgrammersManual.html? It provides really good guidance on what data structures to use throughout LLVM. You probably want something from here: http://llvm.org/docs/ProgrammersManual.html#ds_bit http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:132: std::vector<StackFrame> Stack; SmallVector would seem very handy here to make small graphs go very fast. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:153: NextNodeInfo->Depth < static_cast<int>(Stack.size())+1) { To me, this is a sign that Depth should be a size_t http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:170: else if (Stack.size() > 0) { else should go after } on the same line. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:171: // finish processing current node This makes me think that you actually have an inner loop and an outer loop. Maybe not. Either way, this loop could use some comments. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:185: std::sort(NodeInfoVect.begin(), NodeInfoVect.end()); As annoying as it is, you should probably use array_pod_sort (http://llvm.org/doxygen/STLExtras_8h_source.html#l00271) http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:188: for (typename std::vector<NodeInfo>::iterator I = NodeInfoVect.begin(), Why not just use an index? http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:190: Depths[IGT::getIndex((*I).Node)] = (*I).Depth; I->Node and I->Depth
Sign in to reply to this message.
http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort.h File include/llvm/ADT/TopologicalSort.h (right): http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:26: template<class GraphType, class IGT = IndexedGraphTraits<GraphType> > On 2011/08/15 22:12:15, chandlerc wrote: > space after template, and I suspect we'll want to use 'typename' here instead of > 'class'. Space is fixed. GraphTraits.h uses "class". http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:31: // associate a depth with each node On 2011/08/15 22:12:15, chandlerc wrote: > Comments should be complete sentences. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:32: struct NodeInfo { On 2011/08/15 22:12:15, chandlerc wrote: > I might just forward declare this here, then provide the public interface, then > go back and define them at the bottom in the private section. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:36: NodeInfo() : Node(NULL), Depth(-1) { } Done. Although... > Also, use '0' not 'NULL' for pointers in LLVM and Clang. Seriously? If we wanted to write C code, then why use C++? I have serious moral objections to pretending that integers are pointers. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:40: { } On 2011/08/15 22:12:15, chandlerc wrote: > place the { on the previous line. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:54: // used within the sort() routine On 2011/08/15 22:12:15, chandlerc wrote: > complete sentences Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:63: private: On 2011/08/15 22:12:15, chandlerc wrote: > This is redundant in this particular location, but I would rotate most of this > to the bottom of the class so that the public API comes first. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:68: // Perform a topological sort On 2011/08/15 22:12:15, chandlerc wrote: > Complete sentence. Even better would likely be to not comment here, and provide > a full doxygen comment below. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:72: explicit TopologicallySortedGraph(const GraphType& G) On 2011/08/15 22:12:15, chandlerc wrote: > always attach '*' and '&' to the variable name (this applies to several places > in this file) Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:76: { On 2011/08/15 22:12:15, chandlerc wrote: > { on the previous line. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:102: inline iterator begin() { return iterator(NodeInfoVect.begin()); } On 2011/08/15 22:12:15, chandlerc wrote: > No need for the inline keyword here or below. Done. Also removed inline on the iterator definition above. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:122: // An iterative algorithm is used to avoid stack overflow for large graphs. On 2011/08/15 22:12:15, chandlerc wrote: > Doxygen comments please. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:128: std::vector<bool> Visited(NumNodes, false); On 2011/08/15 22:12:15, chandlerc wrote: > No. no nononono. ;] > > vector<bool> is bad. have you read http://llvm.org/docs/ProgrammersManual.html? > It provides really good guidance on what data structures to use throughout LLVM. > > You probably want something from here: > http://llvm.org/docs/ProgrammersManual.html#ds_bit Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:132: std::vector<StackFrame> Stack; On 2011/08/15 22:12:15, chandlerc wrote: > SmallVector would seem very handy here to make small graphs go very fast. I'm not sure that's a win here, although I am willing to be persuaded. It's very difficult to predict in advance what the appropriate size for a SmallVector should be, especially since this is a generic routine. Moreover, with a vector I can reserve the size in advance, and thus keep memory overhead to a single allocation in all cases. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:153: NextNodeInfo->Depth < static_cast<int>(Stack.size())+1) { On 2011/08/15 22:12:15, chandlerc wrote: > To me, this is a sign that Depth should be a size_t Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:170: else if (Stack.size() > 0) { On 2011/08/15 22:12:15, chandlerc wrote: > else should go after } on the same line. Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:171: // finish processing current node On 2011/08/15 22:12:15, chandlerc wrote: > This makes me think that you actually have an inner loop and an outer loop. > Maybe not. Either way, this loop could use some comments. The recursive version has a for loop with a nested recursive call. The iterative version eliminates the call in favor of a stack, but this has the side effect of obfuscating the loop. I've added additional comments. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:185: std::sort(NodeInfoVect.begin(), NodeInfoVect.end()); On 2011/08/15 22:12:15, chandlerc wrote: > As annoying as it is, you should probably use array_pod_sort > (http://llvm.org/doxygen/STLExtras_8h_source.html#l00271) Done. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:188: for (typename std::vector<NodeInfo>::iterator I = NodeInfoVect.begin(), On 2011/08/15 22:12:15, chandlerc wrote: > Why not just use an index? In the case of std::vector, is there a difference? I assumed that iterators were the preferred mechanism for any container class. http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:190: Depths[IGT::getIndex((*I).Node)] = (*I).Depth; On 2011/08/15 22:12:15, chandlerc wrote: > I->Node and I->Depth Done.
Sign in to reply to this message.
http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort.h File include/llvm/ADT/TopologicalSort.h (right): http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort... include/llvm/ADT/TopologicalSort.h:132: std::vector<StackFrame> Stack; On 2011/08/16 18:15:22, delesley wrote: > On 2011/08/15 22:12:15, chandlerc wrote: > > SmallVector would seem very handy here to make small graphs go very fast. > > I'm not sure that's a win here, although I am willing to be persuaded. It's > very difficult to predict in advance what the appropriate size for a SmallVector > should be, especially since this is a generic routine. Moreover, with a vector > I can reserve the size in advance, and thus keep memory overhead to a single > allocation in all cases. SmallVector<> also has reserve(). I don't have an opinion on whether common graphs are small enough to take advantage of a SmallVector here. 32 frames would be enough to capture a lot of C++ functions though. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h File include/llvm/ADT/GraphTraits.h (right): http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:107: // typedef NodeType - Type of Node in the graph Don't put so many spaces between the typedef and its meaning. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:108: // static unsigned int getIndex(NodeType*) LLVM tends to use just "unsigned" instead of "unsigned int". http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:109: // Return the integer index of a node Maybe describe the invariant that the result is <getMaxIndex? http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... File include/llvm/ADT/TopologicalSort.h (right): http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:11: // topological order, and provides an iterator for traversing the graph in "... in topological order, defined as increasing maximum acyclic path length from the entry node." Otherwise it's not clear what order will be produced for cyclic graphs. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:55: NodeType *operator*() const { return (*I).Node; } s/(*I)./I->/g http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:56: iterator& operator++() { ++I; return *this; } It looks weird to me to have "NodeType *operator" but "iterator& operator". http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:62: NodeType *operator->() const { return &(operator*()); } Does this work? operator* returns a pointer by value, so how can you take its address? Add a use of this to your test. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:82: unsigned int Depth; Remove extra spaces; use just 'unsigned'. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:99: private: No need for the redundant private marker. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:114: /// node, where the depth of a node is defined as the longest acyclic path to s/longest/length of the longest/ http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:116: /// all predecessors of a node, except back-edges, will have smaller depth). It seems more that this definition of depth allows you to define back-edges as edges from a higher depth to a lower depth, and that back-edges so-defined generally correspond to what we'd intuitively identify as loop backedges. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:123: void TopologicallySortedGraph<GraphType, IGT>::sort() { Here's another sort() implementation that passes your test, and structures its stack in a way that I think is easier to understand: template <class GraphType, class IGT> void TopologicallySortedGraph<GraphType, IGT>::sort() { int NumNodes = IGT::getMaxIndex(Graph); // record which nodes have been visited on the current path BitVector Visited(NumNodes, false); NodeType *EntryNode = IGT::getEntryNode(Graph); if (EntryNode == NULL) return; // Set info for entry node. NodeInfo *EntryNodeInfo = &NodeInfoVect[IGT::getIndex(EntryNode)]; EntryNodeInfo->Node = EntryNode; EntryNodeInfo->Depth = 0; Visited[IGT::getIndex(EntryNode)] = true; // Stack for the depth-first search. // // Stores [current, end) iterator ranges for the nodes we're currently // visiting. std::vector<std::pair<ChildIteratorType, ChildIteratorType> > Stack; Stack.reserve(NumNodes); // Invariants. For all frames in Stack: // 1) [frame.first, frame.second) is a valid range. // 2) There is some node s.t. IGT::child_end(node)==frame.second, and // Visited[node] == true. Stack.push_back(make_pair(IGT::child_begin(EntryNode), IGT::child_end(EntryNode))); while (true) { if (Stack.back().first == Stack.back().second) { // We're done processing the current node. Restore previous state by // popping it off of the stack, and resume processing with the next child // of the parent node. Stack.pop_back(); if (Stack.empty()) break; Visited.reset(IGT::getIndex(*Stack.back().first)); ++Stack.back().first; } else { NodeType *NextNode = *Stack.back().first; int NextNodeID = IGT::getIndex(NextNode); NodeInfo *NextNodeInfo = &NodeInfoVect[NextNodeID]; if (!Visited.test(NextNodeID) && NextNodeInfo->Depth < Stack.size()) { assert(NextNodeInfo->Node == NULL || NextNodeInfo->Node == NextNode); NextNodeInfo->Node = NextNode; NextNodeInfo->Depth = Stack.size(); // Save current state by pushing it onto the stack, // and start processing the child node. Visited.set(NextNodeID); Stack.push_back(make_pair(IGT::child_begin(NextNode), IGT::child_end(NextNode))); } else { // Skip processing of the next block. ++Stack.back().first; } } } // sort according to depth array_pod_sort(NodeInfoVect.begin(), NodeInfoVect.end()); // store the depths of all blocks for (typename std::vector<NodeInfo>::iterator I = NodeInfoVect.begin(), E = NodeInfoVect.end(); I != E; ++I) { Depths[IGT::getIndex(I->Node)] = I->Depth; } } http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:148: int NextNodeID = IGT::getIndex(*CurrentIter); s/int/unsigned/ http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:156: Visited.set(NextNodeID); I'd stay with Visited[NextNodeID] = true; http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... File unittests/ADT/TopologicalTest.cpp (right): http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... unittests/ADT/TopologicalTest.cpp:304: // For debugging use only: gtest has a way to print arbitrary messages on test failure: http://code.google.com/p/googletest/wiki/AdvancedGuide#Using_a_Function_That_... http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... unittests/ADT/TopologicalTest.cpp:324: TEST(TopologicalSortTest, SmallGraph) { While randomized tests can be helpful, you also need tests of particular graph structures with precise assertions about what order is produced. http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt File unittests/CMakeLists.txt (right): http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt#newc... unittests/CMakeLists.txt:76: ADT/TopologicalTest.cpp Alphabetize.
Sign in to reply to this message.
Ping? Can we at least send this out to llvm-commits so that we can finish its review concurrently with the review for the warnings that use it? On Tue, Aug 16, 2011 at 2:23 PM, <jyasskin@google.com> wrote: > > http://codereview.appspot.com/**4865045/diff/1/include/llvm/** > ADT/TopologicalSort.h<http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort.h> > File include/llvm/ADT/**TopologicalSort.h (right): > > http://codereview.appspot.com/**4865045/diff/1/include/llvm/** > ADT/TopologicalSort.h#**newcode132<http://codereview.appspot.com/4865045/diff/1/include/llvm/ADT/TopologicalSort.h#newcode132> > include/llvm/ADT/**TopologicalSort.h:132: std::vector<StackFrame> Stack; > On 2011/08/16 18:15:22, delesley wrote: > >> On 2011/08/15 22:12:15, chandlerc wrote: >> > SmallVector would seem very handy here to make small graphs go very >> > fast. > > I'm not sure that's a win here, although I am willing to be persuaded. >> > It's > >> very difficult to predict in advance what the appropriate size for a >> > SmallVector > >> should be, especially since this is a generic routine. Moreover, with >> > a vector > >> I can reserve the size in advance, and thus keep memory overhead to a >> > single > >> allocation in all cases. >> > > SmallVector<> also has reserve(). I don't have an opinion on whether > common graphs are small enough to take advantage of a SmallVector here. > 32 frames would be enough to capture a lot of C++ functions though. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/GraphTraits.h<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h> > File include/llvm/ADT/GraphTraits.h (right): > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/GraphTraits.h#**newcode107<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h#newcode107> > include/llvm/ADT/GraphTraits.**h:107: // typedef NodeType > - Type of Node in the graph > Don't put so many spaces between the typedef and its meaning. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/GraphTraits.h#**newcode108<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h#newcode108> > include/llvm/ADT/GraphTraits.**h:108: // static unsigned int > getIndex(NodeType*) > LLVM tends to use just "unsigned" instead of "unsigned int". > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/GraphTraits.h#**newcode109<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h#newcode109> > include/llvm/ADT/GraphTraits.**h:109: // Return the integer index of a > node > Maybe describe the invariant that the result is <getMaxIndex? > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h> > > File include/llvm/ADT/**TopologicalSort.h (right): > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode11<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode11> > include/llvm/ADT/**TopologicalSort.h:11: // topological order, and > provides an iterator for traversing the graph in > "... in topological order, defined as increasing maximum acyclic path > length from the entry node." Otherwise it's not clear what order will be > produced for cyclic graphs. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode55<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode55> > include/llvm/ADT/**TopologicalSort.h:55: NodeType *operator*() const { > return (*I).Node; } > s/(*I)./I->/g > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode56<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode56> > include/llvm/ADT/**TopologicalSort.h:56: iterator& operator++() { ++I; > return *this; } > It looks weird to me to have "NodeType *operator" but "iterator& > operator". > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode62<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode62> > include/llvm/ADT/**TopologicalSort.h:62: NodeType *operator->() const { > return &(operator*()); } > Does this work? operator* returns a pointer by value, so how can you > take its address? > > Add a use of this to your test. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode82<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode82> > include/llvm/ADT/**TopologicalSort.h:82: unsigned int Depth; > Remove extra spaces; use just 'unsigned'. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode99<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode99> > include/llvm/ADT/**TopologicalSort.h:99: private: > No need for the redundant private marker. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode114<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode114> > include/llvm/ADT/**TopologicalSort.h:114: /// node, where the depth of a > node is defined as the longest acyclic path to > s/longest/length of the longest/ > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode116<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode116> > include/llvm/ADT/**TopologicalSort.h:116: /// all predecessors of a node, > except back-edges, will have smaller depth). > It seems more that this definition of depth allows you to define > back-edges as edges from a higher depth to a lower depth, and that > back-edges so-defined generally correspond to what we'd intuitively > identify as loop backedges. > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode123<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode123> > include/llvm/ADT/**TopologicalSort.h:123: void > TopologicallySortedGraph<**GraphType, IGT>::sort() { > Here's another sort() implementation that passes your test, and > structures its stack in a way that I think is easier to understand: > > > > template <class GraphType, class IGT> > void TopologicallySortedGraph<**GraphType, IGT>::sort() { > int NumNodes = IGT::getMaxIndex(Graph); > > // record which nodes have been visited on the current path > BitVector Visited(NumNodes, false); > > NodeType *EntryNode = IGT::getEntryNode(Graph); > if (EntryNode == NULL) return; > > // Set info for entry node. > NodeInfo *EntryNodeInfo = &NodeInfoVect[IGT::getIndex(**EntryNode)]; > EntryNodeInfo->Node = EntryNode; > EntryNodeInfo->Depth = 0; > Visited[IGT::getIndex(**EntryNode)] = true; > > // Stack for the depth-first search. > // > // Stores [current, end) iterator ranges for the nodes we're currently > // visiting. > std::vector<std::pair<**ChildIteratorType, ChildIteratorType> > Stack; > Stack.reserve(NumNodes); > // Invariants. For all frames in Stack: > // 1) [frame.first, frame.second) is a valid range. > // 2) There is some node s.t. IGT::child_end(node)==frame.**second, and > // Visited[node] == true. > Stack.push_back(make_pair(IGT:**:child_begin(EntryNode), > IGT::child_end(EntryNode))); > while (true) { > if (Stack.back().first == Stack.back().second) { > // We're done processing the current node. Restore previous state > by > // popping it off of the stack, and resume processing with the > next child > // of the parent node. > Stack.pop_back(); > if (Stack.empty()) > break; > Visited.reset(IGT::getIndex(***Stack.back().first)); > ++Stack.back().first; > } else { > NodeType *NextNode = *Stack.back().first; > int NextNodeID = IGT::getIndex(NextNode); > NodeInfo *NextNodeInfo = &NodeInfoVect[NextNodeID]; > > if (!Visited.test(NextNodeID) && > NextNodeInfo->Depth < Stack.size()) { > assert(NextNodeInfo->Node == NULL || > NextNodeInfo->Node == NextNode); > NextNodeInfo->Node = NextNode; > NextNodeInfo->Depth = Stack.size(); > // Save current state by pushing it onto the stack, > // and start processing the child node. > Visited.set(NextNodeID); > Stack.push_back(make_pair(IGT:**:child_begin(NextNode), > IGT::child_end(NextNode))); > } else { > // Skip processing of the next block. > ++Stack.back().first; > } > } > } > > // sort according to depth > array_pod_sort(NodeInfoVect.**begin(), NodeInfoVect.end()); > > // store the depths of all blocks > > for (typename std::vector<NodeInfo>::**iterator I = > NodeInfoVect.begin(), > E = NodeInfoVect.end(); I != E; ++I) { > > Depths[IGT::getIndex(I->Node)] = I->Depth; > } > } > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode148<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode148> > include/llvm/ADT/**TopologicalSort.h:148: int NextNodeID = > IGT::getIndex(*CurrentIter); > s/int/unsigned/ > > http://codereview.appspot.com/**4865045/diff/4001/include/** > llvm/ADT/TopologicalSort.h#**newcode156<http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalSort.h#newcode156> > include/llvm/ADT/**TopologicalSort.h:156: Visited.set(NextNodeID); > I'd stay with Visited[NextNodeID] = true; > > http://codereview.appspot.com/**4865045/diff/4001/unittests/** > ADT/TopologicalTest.cpp<http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest.cpp> > File unittests/ADT/TopologicalTest.**cpp (right): > > http://codereview.appspot.com/**4865045/diff/4001/unittests/** > ADT/TopologicalTest.cpp#**newcode304<http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest.cpp#newcode304> > unittests/ADT/TopologicalTest.**cpp:304: // For debugging use only: > gtest has a way to print arbitrary messages on test failure: > http://code.google.com/p/**googletest/wiki/AdvancedGuide#** > Using_a_Function_That_Returns_**an_AssertionResult<http://code.google.com/p/googletest/wiki/AdvancedGuide#Using_a_Function_That_Returns_an_AssertionResult> > > http://codereview.appspot.com/**4865045/diff/4001/unittests/** > ADT/TopologicalTest.cpp#**newcode324<http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest.cpp#newcode324> > unittests/ADT/TopologicalTest.**cpp:324: TEST(TopologicalSortTest, > SmallGraph) { > While randomized tests can be helpful, you also need tests of particular > graph structures with precise assertions about what order is produced. > > http://codereview.appspot.com/**4865045/diff/4001/unittests/** > CMakeLists.txt<http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt> > File unittests/CMakeLists.txt (right): > > http://codereview.appspot.com/**4865045/diff/4001/unittests/** > CMakeLists.txt#newcode76<http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt#newcode76> > unittests/CMakeLists.txt:76: ADT/TopologicalTest.cpp > Alphabetize. > > > http://codereview.appspot.com/**4865045/<http://codereview.appspot.com/4865045/> >
Sign in to reply to this message.
http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... File include/llvm/ADT/TopologicalSort.h (right): http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:11: // topological order, and provides an iterator for traversing the graph in On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > "... in topological order, defined as increasing maximum acyclic path length > from the entry node." Otherwise it's not clear what order will be produced for > cyclic graphs. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:55: NodeType *operator*() const { return (*I).Node; } On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > s/(*I)./I->/g Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:56: iterator& operator++() { ++I; return *this; } On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > It looks weird to me to have "NodeType *operator" but "iterator& operator". Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:62: NodeType *operator->() const { return &(operator*()); } On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Does this work? operator* returns a pointer by value, so how can you take its > address? > > Add a use of this to your test. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:82: unsigned int Depth; On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Remove extra spaces; use just 'unsigned'. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:99: private: On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > No need for the redundant private marker. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:114: /// node, where the depth of a node is defined as the longest acyclic path to On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > s/longest/length of the longest/ Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:116: /// all predecessors of a node, except back-edges, will have smaller depth). On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > It seems more that this definition of depth allows you to define back-edges as > edges from a higher depth to a lower depth, and that back-edges so-defined > generally correspond to what we'd intuitively identify as loop backedges. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:123: void TopologicallySortedGraph<GraphType, IGT>::sort() { As per our semi-scientific test, I am leaving the loop structure unchanged. :-) On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Here's another sort() implementation that passes your test, and structures its > stack in a way that I think is easier to understand: > > > template <class GraphType, class IGT> > void TopologicallySortedGraph<GraphType, IGT>::sort() { > int NumNodes = IGT::getMaxIndex(Graph); > > // record which nodes have been visited on the current path > BitVector Visited(NumNodes, false); > > NodeType *EntryNode = IGT::getEntryNode(Graph); > if (EntryNode == NULL) return; > > // Set info for entry node. > NodeInfo *EntryNodeInfo = &NodeInfoVect[IGT::getIndex(EntryNode)]; > EntryNodeInfo->Node = EntryNode; > EntryNodeInfo->Depth = 0; > Visited[IGT::getIndex(EntryNode)] = true; > > // Stack for the depth-first search. > // > // Stores [current, end) iterator ranges for the nodes we're currently > // visiting. > std::vector<std::pair<ChildIteratorType, ChildIteratorType> > Stack; > Stack.reserve(NumNodes); > // Invariants. For all frames in Stack: > // 1) [frame.first, frame.second) is a valid range. > // 2) There is some node s.t. IGT::child_end(node)==frame.second, and > // Visited[node] == true. > Stack.push_back(make_pair(IGT::child_begin(EntryNode), > IGT::child_end(EntryNode))); > while (true) { > if (Stack.back().first == Stack.back().second) { > // We're done processing the current node. Restore previous state by > // popping it off of the stack, and resume processing with the next child > // of the parent node. > Stack.pop_back(); > if (Stack.empty()) > break; > Visited.reset(IGT::getIndex(*Stack.back().first)); > ++Stack.back().first; > } else { > NodeType *NextNode = *Stack.back().first; > int NextNodeID = IGT::getIndex(NextNode); > NodeInfo *NextNodeInfo = &NodeInfoVect[NextNodeID]; > > if (!Visited.test(NextNodeID) && > NextNodeInfo->Depth < Stack.size()) { > assert(NextNodeInfo->Node == NULL || > NextNodeInfo->Node == NextNode); > NextNodeInfo->Node = NextNode; > NextNodeInfo->Depth = Stack.size(); > // Save current state by pushing it onto the stack, > // and start processing the child node. > Visited.set(NextNodeID); > Stack.push_back(make_pair(IGT::child_begin(NextNode), > IGT::child_end(NextNode))); > } else { > // Skip processing of the next block. > ++Stack.back().first; > } > } > } > > // sort according to depth > array_pod_sort(NodeInfoVect.begin(), NodeInfoVect.end()); > > // store the depths of all blocks > for (typename std::vector<NodeInfo>::iterator I = NodeInfoVect.begin(), > E = NodeInfoVect.end(); I != E; ++I) { > Depths[IGT::getIndex(I->Node)] = I->Depth; > } > } http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:148: int NextNodeID = IGT::getIndex(*CurrentIter); On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > s/int/unsigned/ Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/TopologicalS... include/llvm/ADT/TopologicalSort.h:156: Visited.set(NextNodeID); On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > I'd stay with Visited[NextNodeID] = true; Done. http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... File unittests/ADT/TopologicalTest.cpp (right): http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... unittests/ADT/TopologicalTest.cpp:304: // For debugging use only: On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > gtest has a way to print arbitrary messages on test failure: > http://code.google.com/p/googletest/wiki/AdvancedGuide#Using_a_Function_That_... Done. http://codereview.appspot.com/4865045/diff/4001/unittests/ADT/TopologicalTest... unittests/ADT/TopologicalTest.cpp:324: TEST(TopologicalSortTest, SmallGraph) { On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > While randomized tests can be helpful, you also need tests of particular graph > structures with precise assertions about what order is produced. Done.
Sign in to reply to this message.
http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.h File include/llvm/ADT/GraphTraits.h (right): http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:107: // typedef NodeType - Type of Node in the graph On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Don't put so many spaces between the typedef and its meaning. Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:108: // static unsigned int getIndex(NodeType*) On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > LLVM tends to use just "unsigned" instead of "unsigned int". Done. http://codereview.appspot.com/4865045/diff/4001/include/llvm/ADT/GraphTraits.... include/llvm/ADT/GraphTraits.h:109: // Return the integer index of a node On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Maybe describe the invariant that the result is <getMaxIndex? Done. http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt File unittests/CMakeLists.txt (right): http://codereview.appspot.com/4865045/diff/4001/unittests/CMakeLists.txt#newc... unittests/CMakeLists.txt:76: ADT/TopologicalTest.cpp On 2011/08/16 21:23:11, Jeffrey Yasskin (google) wrote: > Alphabetize. Done.
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
