[ADT] Actually mutate the iterator VisitStack.back().second, not its copy.

[timshen]

Summary

Before the change, *Opt never actually gets updated by the end
of toNext(), so for every next time the loop has to start over from
child_begin(). This bug doesn't affect the correctness, since Visited prevents
it from re-entering the same node again; but it's slow.

[dberris]

Is there a test that exposes the bug this is meant to fix?

[dberris]

(Replying here because the comments on the mailing list don't seem to get reflected in Phab)

I think what confused me asking for a test case was that it wasn't clear from the description what exactly is being "fixed" (because of the word "correct").

I think a comment in the code would help explain why you're doing this instead of using a range-based loop, and an update to the description would be really helpful.

[timshen]

In D23649#520437, @dberris wrote:

(Replying here because the comments on the mailing list don't seem to get reflected in Phab)

I think what confused me asking for a test case was that it wasn't clear from the description what exactly is being "fixed" (because of the word "correct").

I think a comment in the code would help explain why you're doing this instead of using a range-based loop, and an update to the description would be really helpful.

Done. Sorry for the confusion!

[dberris]

include/llvm/ADT/DepthFirstIterator.h

110–115

Perhaps comment before these lines to explain that you don't do a range-based for loop for the reasons you explain, so the next person reading this doesn't go "why don't we make it a range-based for loop instead?".

[timshen]

Add comment for the change.

[timshen]

Thanks for reviewing!

I should have added the comment at the very beginning. It probably will save the two turn arounds in the review.

[dblaikie]

Please update the title as well to match the intent (it's not so much about range based for loop as it is about mutating the original iterator).

Up to you if you consider the local reference preferable to directly modifying 'Opt'.

include/llvm/ADT/DepthFirstIterator.h

110–114

I /think/ it'd be more explicit & probably not need the comment if you wrote it without the reference:

for (; *Opt != GT::child_end(Node); ++*Opt) {
  NodeRef Next = **Opt;
  ...

[timshen]

Increase the iterator right after dereference it, not at the end of the loop body.

[timshen]

I also removed ++*Opt and increase it immediately at "NodeRef Next = *(*Opt)++;", so that even the early return executes, *Opt is still increased.

include/llvm/ADT/DepthFirstIterator.h

110–114

Done. It is more explicit.

[timshen]

Added a testcase.

[timshen]

Remove the duplicated Graph definition in SCCIteratorTest.cpp

[dblaikie]

unittests/ADT/DepthFirstIteratorTest.cpp

18–21 ↗

(On Diff #68758)

Might just make this a struct? (InsertVisited isn't protected in any way, for example, doesn't seem too important)

22 ↗

(On Diff #68758)

Typedef?

26 ↗

(On Diff #68758)

This should be implicit?

39 ↗

(On Diff #68758)

Do you need to write this copy ctor? Should be implicit, no?

44–45 ↗

(On Diff #68758)

I think we just use 'typedef' for this so far.

51–53 ↗

(On Diff #68758)

Probably drop braces on a single line loop.

Though maybe this is better expressed with a different construct?

(void)std::distance(begin, end), perhaps?

(saves the make_range, extra variable copies, etc?) Probably with a comment saying something like "walk the DF ordering & ensure each element was only visited once"

[timshen]

Updated as commented.

unittests/ADT/DepthFirstIteratorTest.cpp

22 ↗

(On Diff #68758)

When do we use using and when typedef? If I'm creating a new file I'd go for using.

51–53 ↗

(On Diff #68758)

std::distance doesn't do what we want on randomaccess iterators, so using std::distance makes it depends more on the context. I'd rather make it more explicit using range-based for loop.

include/llvm/ADT/DepthFirstIterator.h

private:
   inline void toNext() {
     do {
       NodeRef Node = VisitStack.back().first;
       Optional<ChildItTy> &Opt = VisitStack.back().second;
 
       if (!Opt)
         Opt.emplace(GT::child_begin(Node));
 
-      for (NodeRef Next : make_range(*Opt, GT::child_end(Node))) {
+      // Notice that we use `auto &It =` here, as opposed to `auto It =` or
+      // range-based for loop, so that VisitStack.back().second actually gets
+      // updated.
+      for (auto &It = *Opt; It != GT::child_end(Node); ++It) {
+        NodeRef Next = *It;
         // Has our next sibling been visited?
         if (this->Visited.insert(Next).second) {
           // No, do it now.
           VisitStack.push_back(StackElement(Next, None));
           return;
         }
       }
 
       // Oops, ran out of successors... go up a level on the stack.