This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by timshen on Aug 18 2016, 1:35 AM.

Details

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.

Diff Detail

Event Timeline

timshen updated this revision to Diff 68494.Aug 18 2016, 1:35 AM
timshen retitled this revision from to [ADT] Change the range-based for loop in DFS to normal loop. NFC..
timshen updated this object.
timshen added a reviewer: dblaikie.
timshen added a subscriber: llvm-commits.

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

(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 updated this object.Aug 18 2016, 11:01 PM

(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!

timshen updated this object.Aug 18 2016, 11:04 PM
dberris accepted this revision.Aug 18 2016, 11:15 PM
dberris added a reviewer: dberris.
dberris added inline comments.
include/llvm/ADT/DepthFirstIterator.h
110–111

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?".

This revision is now accepted and ready to land.Aug 18 2016, 11:15 PM
timshen updated this revision to Diff 68651.Aug 18 2016, 11:22 PM
timshen edited edge metadata.

Add comment for the change.

timshen marked an inline comment as done.Aug 18 2016, 11:24 PM

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 accepted this revision.Aug 19 2016, 10:19 AM
dblaikie edited edge metadata.

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–112

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 updated this revision to Diff 68709.Aug 19 2016, 10:33 AM
timshen edited edge metadata.

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

timshen marked an inline comment as done.Aug 19 2016, 10:35 AM

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–112

Done. It is more explicit.

timshen retitled this revision from [ADT] Change the range-based for loop in DFS to normal loop. NFC. to [ADT] Actually mutate the iterator VisitStack.back().second, not its copy..Aug 19 2016, 10:58 AM
timshen updated this object.
timshen updated this revision to Diff 68756.Aug 19 2016, 6:30 PM
timshen marked an inline comment as done.

Added a testcase.

timshen updated this revision to Diff 68758.Aug 19 2016, 6:34 PM

Remove the duplicated Graph definition in SCCIteratorTest.cpp

dblaikie added inline comments.Aug 22 2016, 11:14 AM
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 this revision to Diff 68915.Aug 22 2016, 2:41 PM
timshen marked 5 inline comments as done.

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.

This revision was automatically updated to reflect the committed changes.