Page MenuHomePhabricator

Introduce iterator sentinel to make graph traversal implementation more efficient and cleaner
Needs ReviewPublic

Authored by rusyaev-roman on Aug 8 2022, 3:13 PM.

Details

Summary

As of C++17, for "range-based for loop" the types of the begin-expr and the end-expr do not have to be the same,
and in fact the type of the end-expr does not have to be an iterator. This makes it possible to delimit
a range by a predicate for graph traversal iterators. To be more specific, it's not necessary to comapre
two containers in order to check that an iterator is the end iterator.
For more information see https://en.cppreference.com/w/cpp/language/range-for#Notes

Diff Detail

Unit TestsFailed

TimeTest
60,120 msx64 debian > AddressSanitizer-x86_64-linux-dynamic.TestCases::scariness_score_test.cpp
Script: -- : 'RUN: at line 4'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libasan -O0 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/scariness_score_test.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Output/scariness_score_test.cpp.tmp
60,140 msx64 debian > AddressSanitizer-x86_64-linux.TestCases::scariness_score_test.cpp
Script: -- : 'RUN: at line 4'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -O0 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/scariness_score_test.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxConfig/TestCases/Output/scariness_score_test.cpp.tmp

Event Timeline

rusyaev-roman created this revision.Aug 8 2022, 3:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 8 2022, 3:13 PM
rusyaev-roman requested review of this revision.Aug 8 2022, 3:13 PM
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project. · View Herald Transcript

Fix mlir build and rebase

Herald added a project: Restricted Project. · View Herald Transcript

In sum, this change brings the following improvements for all graph traversal iterators that are used in 'range-based for loop':

  • avoid creating an empty iterator (that holds containers inside) to compare with the end iterator
  • make 'empty()' call explicit (instead of comparing two containers of iterators) when an iterator is compared with the end iterator

lgtm for the MLInlineAdvisor bit

Direction seems pretty good - some of the details I'm fuzzy on. If there's easy ways to keep some of the existing syntax (like I see at least one loop that I think was querying the incremented iterator for "isAtEnd" - maybe that can be preserved initially) to reduce the number of places this patch has to touch, then incremental patches after this, and then removing the backcompat API?

llvm/include/llvm/ADT/BreadthFirstIterator.h
128–131

Generally any operator that can be a non-member should be a non-member (but can still be a friend) so there's equal conversion handling for LHS and RHS. Could you make these non-members? (maybe a separate patch to do the same to the existing op overloads, so the new ones don't look weird)

do you need the inverse operators too, so the sentinel can appear on either side of the comparison?

llvm/include/llvm/ADT/SCCIterator.h
49–50

does this need a value type too? (& then define the reference and pointer types relative to that)

152–162

I'm not quite following why this requires the proxy object - even after reading the comment above. It looks like this function is entirely in terms of the SCC object that's returned from operator* - so maybe this could be a free function, called with hasCycle(*some_iterator)?

165–170

I always forget in which cases you're allowed to return a proxy object from an iterator - I thought some iterator concepts (maybe random access is the level at which this kicks in?) that required something that amounts to "there has to be a real object that outlives the iterator"

Could you refresh my memory on that/on why proxy objects are acceptable for this iterator type? (where/how does this iterator declare what concept it models anyway, since this removed the facade helper?)

I haven't reviewed this in detail, but oh my I love LOVE LOVE this! llvm::scc_traversal(x) is so nice, great work!

First of all, thank you for your feedback! I've tried to address all your comments.

llvm/include/llvm/ADT/BreadthFirstIterator.h
128–131

Absolutely agree with all your points!

But I didn't want to make the code inconsistent and complicated in this patch. So, I suggest making all these operators 'friend' in a separate patch, otherwise it can lead to some boilerplate code like this:

friend bool operator==(const scc_iterator &SCCI, iterator_sentinel) {
  return SCCI.isAtEnd();
}

friend bool operator==(iterator_sentinel IS, const scc_iterator &SCCI) {
  return SCCI == IS;
}

friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
  return !(SCCI == IS);
}

friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
  return !(IS == SCCI);
}

This boilerplate code can be avoided using special helper classes, but I wouldn't like to implement them in this patch in order to keep it simple.

What do you think?

llvm/include/llvm/ADT/SCCIterator.h
49–50

Thanks, good point! I forgot to add additional types and member functions to satisfy forward iterator requirements when I removed iterator_facade base class. I'll update the patch (maybe get iterator_facade back)

152–162

maybe this could be a free function, called with hasCycle(*some_iterator)?

This was my initial intention.

But in the case of free function (or maybe static function of scc_iterator class) a user should write the following code:

for (const auto& SCC : scc_traversal(Graph))
  if (hasCycle<decltype(Graph)>(SCC)) // or in more complicated case when GraphTraits cannot be deduced from Graph type -- hasCycle<decltype(Graph), SubtGraphTraits>(SCC))
     ...

This is the main reason of SCCProxy introduction -- to make it possible to write like this:

for (const auto& SCC : scc_traversal(Graph))
  if (SCC.hasCycle())
     ...
165–170

A proxy object is allowed to be returned while dereferencing an input iterator (https://en.cppreference.com/w/cpp/named_req/InputIterator#Notes)

The reference type for an input iterator that is not also a LegacyForwardIterator does not have to be a reference type: dereferencing an input iterator may return a proxy object or value_type itself by value

For our case (that's forward iterator) we need to satisfy the following thing:

 The type std::iterator_traits<It>::reference must be exactly 
   ...
   * const T& otherwise (It is constant), 

(where T is the type denoted by std::iterator_traits<It>::value_type)

I'll also update the patch according to this point. Other things are ok for using a proxy object.

dblaikie added inline comments.Aug 11 2022, 1:22 PM
llvm/include/llvm/ADT/BreadthFirstIterator.h
128–131

Sure sure - before or after's fine by me.

llvm/include/llvm/ADT/SCCIterator.h
152–162

Ooh, it's the graph traits that's the extra (type) parameter. Makes sense.

Yeah, if this is workable while meeting the iterator requirements/proxy discussion elsewhere, sounds good.

165–170

Thanks for doing the legwork/quotations there.

so what's the solution here, if we're going to meet the forward iterator requirements but want a proxy object?

ychen added a subscriber: ychen.Aug 11 2022, 2:05 PM
dexonsmith added inline comments.Aug 11 2022, 2:24 PM
llvm/include/llvm/ADT/SCCIterator.h
165–170

IIRC, one solution is to store a proxy object inside the iterator, make using value_type = ProxyT, update what the stored proxy points at on operator*(), and return ProxyT& when dereferencing. But maybe I'm misremembering. (I'm pretty sure iterator_facade_base has machinery to help with this stuff, either way; might be worth looking at other uses of it.)

For a while I will be in a place where the Internet does not work well. I'll finish the patch when I come back.

rusyaev-roman added inline comments.Aug 11 2022, 11:46 PM
llvm/include/llvm/ADT/SCCIterator.h
165–170

so what's the solution here, if we're going to meet the forward iterator requirements but want a proxy object?

We need to modify the code according to the above comment. I'm highlighting it below. (maybe, I was not clear. Sorry for this. @dexonsmith has provided more detailed explanation)

For our case (that's forward iterator) we need to satisfy the following thing:

 The type std::iterator_traits<It>::reference must be exactly 
   ...
   * const T& otherwise (It is constant), 

(where T is the type denoted by std::iterator_traits<It>::value_type)

I'll also update the patch according to this point. Other things are ok for using a proxy object.

craig.topper added inline comments.Aug 12 2022, 9:52 AM
llvm/include/llvm/ADT/iterator_range.h
50

"based-range" should be "range-based" shouldn't it?