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/>
>