This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Allow `llvm::enumerate` to enumerate over multiple ranges
ClosedPublic

Authored by kuhar on Feb 21 2023, 9:18 AM.

Details

Summary

This does not work by a mere composition of enumerate and zip_equal,
because C++17 does not allow for recursive expansion of structured
bindings.

This implementation uses zippy to manage the iteratees and adds the
stream of indices as the first zipped range. Because we have an upfront
assertion that all input ranges are of the same length, we only need to
check if the second range has ended during iteration.

As a consequence of using zippy, enumerate will now follow the
reference and lifetime semantics of the zip* family of functions. The
main difference is that enumerate exposes each tuple of references
through a new tuple-like type enumerate_result, with the familiar
.index() and .value() member functions.

Because the enumerate_result returned on dereference is a
temporary, enumeration result can no longer be used through an
lvalue ref.

Diff Detail

Event Timeline

kuhar created this revision.Feb 21 2023, 9:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2023, 9:18 AM
Herald added a subscriber: hanchung. · View Herald Transcript
kuhar requested review of this revision.Feb 21 2023, 9:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2023, 9:18 AM
kuhar updated this revision to Diff 499209.Feb 21 2023, 9:19 AM

Clean up

Implementation makes sense to me and matches my expectation. Wouldn't really know how to do this any simpler than the current state myself to be honest.

llvm/include/llvm/ADT/STLExtras.h
29

Watch out, this is not a standard C++ header but an implementation detail from libstdc++

2223

ditto with copy constructor here

2250

Any reason to explicitly default these? IIRC doing so even deletes the move constructors and move assignment

2265

Am I correct that these casts here are only necassery since zip only ever uses the ranges const iterator? I don't see any other reasons since these are otherwise noop casts.
Fixing zip would also "fix" needing the const below in the test case on Range. Possibly out of scope for this patch.

2268

I believe you meant this to be range_reference_tuple instead of value_reference_tuple, in which case you can just directly do return get_values(...));

Otherwise this 1) does not compile if calling .value() on the result with more than one range 2) would otherwise return a tuple with the value returned by index() in the first position.

Please add a test case for this case as well.

llvm/unittests/ADT/STLExtrasTest.cpp
168

Can you elaborate what you mean with const reference here? As far as I can tell, from all the types involved in the ranged for below none of them are const references.

kuhar added inline comments.Feb 21 2023, 11:37 AM
llvm/include/llvm/ADT/STLExtras.h
29

Gah, clangd end up pulling in funny includes sometimes...

2265

Exactly. I've struggled with const references in my implementation, I'll try your suggestion to see if it simplifies things.

llvm/unittests/ADT/STLExtrasTest.cpp
168

Thanks, the comment is out of sync with the code.

kuhar updated this revision to Diff 499260.Feb 21 2023, 11:49 AM
kuhar marked 4 inline comments as done.

Address comments from @zero9178

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

kuhar added a comment.Feb 21 2023, 1:58 PM

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

kuhar added a comment.Feb 21 2023, 3:00 PM

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

I see. I think in this specific case the ergonomics make this work in real world. We have a considerable amount of code in MLIR and IREE that iterates over multidimensional stuff in lockstep, and it's nice to have a concise and safe way to manage that. I don't think that flatten achieves that given the total amount of nesting. Instead, one could unpack the values in the first statement inside the loop like so:

for (auto [Idx, Val] : enumerate(zip_equal(...))) {
  auto [X, Y, Z] = Val.value()

Another issue I see is unintentionally unpacking a single element in generic code -- a single range can contain tuple values, and I don't think we can tell this apart from zip(...) without checking the range/iterator type.

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

I see. I think in this specific case the ergonomics make this work in real world. We have a considerable amount of code in MLIR and IREE that iterates over multidimensional stuff in lockstep, and it's nice to have a concise and safe way to manage that. I don't think that flatten achieves that given the total amount of nesting.

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Instead, one could unpack the values in the first statement inside the loop like so:

for (auto [Idx, Val] : enumerate(zip_equal(...))) {
  auto [X, Y, Z] = Val.value()

That seems fine too as a solution to the issue, rather than introducing this enumerate+zip special case?

Another issue I see is unintentionally unpacking a single element in generic code -- a single range can contain tuple values, and I don't think we can tell this apart from zip(...) without checking the range/iterator type.

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

kuhar added a comment.EditedFeb 22 2023, 2:40 PM

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Your comments got me thinking about a different solution; I'd like to try to decompose this as follows something like this:

  • use the zippy to take care of enumeration of all subranges, including the index. Drop all the custom iterator/enumerator types etc.
  • add a wrapper reference type that produces a nice interface over each tuple of elements from zippy (very similar to enumerator_result here)
  • use something like map_range to expose the zipped ranges via this wrapper element reference type

In pseudocode:

auto enumerate(ranges...) {
  return map_range(zippy<zip_second>(index_stream{}, ranges...), to_enumerate_result);
}

WDYT?

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

I was worried about code that takes a variadic number of ranges and passes them to enumerate, but you are right that this is a non-issue if we leave enumerate unary and have a new wrapper function.

So a potential solution would be to introduce enumerate_zip that takes 2 or more ranges and is implemented like this:

auto enumerate_zip(first, second, rest...) {
  return zippy<zip_second>(index_stream{}, first, second, rest...);
}

and does not support .index() and .value(). I think that's also a viable option and doesn't even need flatten if we give up on those two accessors anyway.

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Your comments got me thinking about a different solution; I'd like to try to decompose this as follows something like this:

  • use the zippy to take care of enumeration of all subranges, including the index. Drop all the custom iterator/enumerator types etc.
  • add a wrapper reference type that produces a nice interface over each tuple of elements from zippy (very similar to enumerator_result here)
  • use something like map_range to expose the zipped ranges via this wrapper element reference type

In pseudocode:

auto enumerate(ranges...) {
  return map_range(zippy<zip_second>(index_stream{}, ranges...), to_enumerate_result);
}

WDYT?

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

I was worried about code that takes a variadic number of ranges and passes them to enumerate, but you are right that this is a non-issue if we leave enumerate unary and have a new wrapper function.

So a potential solution would be to introduce enumerate_zip that takes 2 or more ranges and is implemented like this:

auto enumerate_zip(first, second, rest...) {
  return zippy<zip_second>(index_stream{}, first, second, rest...);
}

and does not support .index() and .value(). I think that's also a viable option and doesn't even need flatten if we give up on those two accessors anyway.

Yeah, either of these sound OK to me - thanks for working through them.

(be nice if enumerate_resulrt or equivalent were a bit simpler, but I haven't looked closely at all the complexities/understood their motivation)

I guess llvm::enumerate doesn't have any particular API it's trying to emulate (like I don't immediately see a standardized version on the horizon? Is there a boost or other one that we should be trying to keep this looking similar to)? If there is some similar one we're trying to stay close to, does that one support N-ary enumerate? if it doesn't, then I'd be happy to keep the current enumerate as singular, and add the separate enumerate_zip, probably. As much as the "wrapping it in a nice result with index() and value()" is a bit of a pain/bunch of work compared to the generic tuple, I guess having the index named is worthwhile - even with the prevalence of structured bindings, so I don't object to the enumerate_result or equivalent being implemented)

+1 finally I'm happy to see this

kuhar updated this revision to Diff 502393.Mar 4 2023, 3:33 PM

Implement enumerate in terms of zippy with a custom zip iterator.

Fix issues with constness.

kuhar retitled this revision from [WIP][STLExtras] Allow `llvm::enumerate` to enumerate over multiple ranges to [ADT] Allow `llvm::enumerate` to enumerate over multiple ranges.Mar 4 2023, 3:37 PM
kuhar edited the summary of this revision. (Show Details)
kuhar added a reviewer: Mogball.
kuhar added a comment.Mar 4 2023, 3:49 PM

I iterated on this a fair bit and come up with this implementation that uses zippy to manage iterators and ranges. This way all we need to do is to define a zip iterator type that returns an enumeration result on dereference. This enumeration result is essentially a tuple of references that exposes the enumeration interface (.index() and .value()). This way, we do not duplicate similar iteration machinery across multiple APIs: zip*, enumerate, or enumerate_zip, and do not have to duplicate tests cases either.

I guess llvm::enumerate doesn't have any particular API it's trying to emulate (like I don't immediately see a standardized version on the horizon? Is there a boost or other one that we should be trying to keep this looking similar to)? If there is some similar one we're trying to stay close to, does that one support N-ary enumerate? if it doesn't, then I'd be happy to keep the current enumerate as singular, and add the separate enumerate_zip, probably.

I looked at Python and a few newer languages, but it seems like they can avoid this complexity by supporting 'nested structured bindings', which C++17 does not have. IMO, n-ary enumeration is a pretty natural extension -- the evidence for that is the number of loops that already do enumerate(zip(...)), despite its current clunkiness.

I tried wrapping results of enumerate(zip(args...)) with flatten or similar functions, and found this to be much more complicated and have some clear drawbacks like multiple moves of the input ranges, unclear lifetime semantics when composing multiple range adaptors, etc. The new implementation in this revision avoids that by reusing what zippy already handles and passes existing enumerate tests that check for the expected semantics.

kuhar updated this revision to Diff 502494.Mar 5 2023, 5:42 PM

Rebase. Update commit description.

kuhar edited the summary of this revision. (Show Details)Mar 5 2023, 5:45 PM
kuhar marked an inline comment as done.
kuhar marked an inline comment as done.Mar 5 2023, 5:47 PM
dexonsmith resigned from this revision.Mar 6 2023, 1:58 PM

Because the enumerate_result returned on dereference is a temporary, enumeration result can no longer be used through an lvalue ref.

Is it valid to have a value-returning iterator? (what about op->, which needs a pointer returned?) I thought that wasn't valid for most iterator categories & you had to resort to storing an object inside the iterator to return a pointer to in op*/op->

kuhar added a comment.Mar 7 2023, 8:11 AM

Because the enumerate_result returned on dereference is a temporary, enumeration result can no longer be used through an lvalue ref.

Is it valid to have a value-returning iterator? (what about op->, which needs a pointer returned?) I thought that wasn't valid for most iterator categories

This is already the case with other iterators returned from zip* functions -- their reference type is the same as value type (tuple of references). Other common iterators that return values that come to my mind are SafeIntIterator (from llvm::seq and llvm::iota_range), vector<bool>::iterator (reference wrapper). If I understand '[forward.iterators]' correctly, this seems fine as long as reference is *some* reference type convertible to the value type:

— if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,
— the expressions in Table 97 are valid and have the indicated semantics, and

In table 97:

Expression | Return type
*r++ | reference

And in '[input.iterators]:

A class or pointer type X satisfies the requirements of an input iterator for the value type T if X satisfies the
Iterator (27.2.2) and EqualityComparable (Table 20) requirements and the expressions in Table 95 are
valid and have the indicated semantics.

In table 95:

Expression | Return type
*a | reference, convertible to T

Right now, enumerate is returns only forward_iterators, but we should be able to make it bidirectional and probably random in the future without having to change the iterator reference type (provided that all nested iterators have the required categories).

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)
dblaikie accepted this revision.Mar 8 2023, 12:52 PM

I don't totally object - though, for myself (I think this was discussed previously, but I don't fully understand the refutation/disagreement) I think I'd prefer to expose the compositions themselves and probably not have a special return type, so the end result is:

for (auto &[index, v1, v2] : zip(index{}, r1, r2))

And drop "enumerate" entirely? It doesn't seem like it adds enough - though I guess having a name for it is useful. *shrug*

llvm/include/llvm/ADT/STLExtras.h
2315–2316

Could this be conforming/have a real reference type (& Return ref from op*)?

2324–2329

prefer non-member (can be a friend) op overloads where possible - makes sure implicit conversions happen equally on LHS and RHS

This revision is now accepted and ready to land.Mar 8 2023, 12:52 PM
kuhar added a comment.Mar 8 2023, 1:02 PM

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

I think its also fair to say that this is somewhat a historical mistake that was never properly followed (see std::vector<bool>) which is probably why this requirement was dropped in C++20 concepts for forward iterators: https://en.cppreference.com/w/cpp/iterator/forward_iterator

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

I think its also fair to say that this is somewhat a historical mistake that was never properly followed (see std::vector<bool>) which is probably why this requirement was dropped in C++20 concepts for forward iterators: https://en.cppreference.com/w/cpp/iterator/forward_iterator

Yeah, sort of nice to see (insofar as I can see it/read the concepts as best I can) - op-> is awkward & weird when it's not supported, but probably the best tradeoff to lose that consistency for the greater flexibility. (Not sure what to make of comments like "Pointers and references obtained from a forward iterator into a range remain valid while the range exists.".

kuhar updated this revision to Diff 504809.Mar 13 2023, 12:39 PM
kuhar marked 2 inline comments as done.

Rebase. Add comments clarifying iterator reference_type requirments.

llvm/include/llvm/ADT/STLExtras.h
2315–2316

I looked into returning the reference to the index but this breaks the requirement of references being valid as long as the range is valid:

Pointers and references obtained from a forward iterator into a range remain valid while the range exists.

I kept this as-is and added a comment.

My plan is to land a series of clean-up commits removing lvalue references to enumerate elements and once these are in land this patch (probably end of this week or beginning of the next week).

kuhar updated this revision to Diff 505497.Mar 15 2023, 8:13 AM

Rebase. Update existing uses of enumerate with non-const lvalue refs.
Replace some enumerate(zip* patterns with n-ary enumerate.

dblaikie accepted this revision.Mar 15 2023, 10:37 AM
dblaikie added inline comments.
llvm/unittests/ADT/STLExtrasTest.cpp
222
zero9178 accepted this revision.Mar 15 2023, 10:44 AM

LGTM!

llvm/include/llvm/ADT/STLExtras.h
2234
2244

nit: remove trivial braces here and below

kuhar updated this revision to Diff 505576.Mar 15 2023, 11:27 AM
kuhar marked 2 inline comments as done.

Address comments.

kuhar marked an inline comment as done.Mar 15 2023, 11:28 AM
kuhar updated this revision to Diff 505587.Mar 15 2023, 12:11 PM

Fix outdated usage in AArch64PerfectShuffle

srj added a subscriber: srj.Mar 16 2023, 6:02 PM

According to git bisect, this change appears to have broken llvm-tblgen when building under MSVC

C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): error C2440: 'initializing':
cannot convert from 'size_t' to '_This'
        with
        [
            _This=const llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0> &
        ]
C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): note: Reason: cannot convert
from 'size_t' to 'const T'
        with
        [
            T=llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0>
        ]
C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): note: Constructor for class '
llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0>' is declared 'explicit'

this has rendered all Windows-based testing of Halide impossible; I urge someone to fix (or revert) this change as soon as conveniently possible.

srj added a comment.Mar 16 2023, 6:05 PM

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]
kuhar added a comment.Mar 16 2023, 6:14 PM

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

Hi @srj,

Is there some public buildbot that experienced the same failure? Do you have some info on the build environment, version of the compiler, etc? I haven't seen this affect other windows buildbots.
If this is blocking you and you need a quick fix isolated to these two places, I suggest patching these two loops something like this:

for (const auto &En :
     enumerate(Intrinsic.ArgumentAttributes)) {
     size_t AttrIdx = En.index();
     auto& Attrs = En.value();

or even with manual indexing:

size_t AttrIdx = 0;
 for (const auto &Attrs : Intrinsic.ArgumentAttributes) {
      
  ...
  ++AttIdx;
}
srj added a comment.Mar 16 2023, 6:20 PM

Is there some public buildbot that experienced the same failure?

You can see the build logs here: https://buildbot.halide-lang.org/master/#/builders/105/builds/8

Do you have some info on the build environment, version of the compiler, etc? I haven't seen this affect other windows buildbots.

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

If this is blocking you and you need a quick fix isolated to these two places, I suggest patching these two loops something like this:

Thanks, but we need to figure out if this is a problem in our build environment or a corner case of broken code -- we rely on testing unchanged LLVM versions.

srj added a comment.Mar 16 2023, 6:25 PM

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

EDIT: looks like there are some uninstalled updates -- I'll get those installed and re-check, maybe this is just an MSVC bug.

srj added a comment.Mar 17 2023, 9:43 AM

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

EDIT: looks like there are some uninstalled updates -- I'll get those installed and re-check, maybe this is just an MSVC bug.

So after installing the latest VS2022 updates, things appear to be working smoothly!

I was not expecting this at all -- it's been a long time since I've seen a miscompilation of this sort in any modern compiler so I didn't even think to check this.

Sorry for the noise!

In module 'LLVM_Utils' imported from /Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/tools/llvm-pdbutil/StreamUtil.h:12:
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2389:11: error: no matching function for call to 'all_equal'
          all_equal({std::distance(adl_begin(First), adl_end(First)),
          ^~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.3.sdk/usr/include/assert.h:93:25: note: expanded from macro 'assert'
    (__builtin_expect(!(e), 0) ? __assert_rtn(__func__, __FILE__, __LINE__, #e) : (void)0)
                        ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/tools/llvm-pdbutil/ExplainOutputStyle.cpp:129:28: note: in instantiation of function template specialization 'llvm::enumerate<const std::__1::vector<llvm::ArrayRef<llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::little, 1, 1>>> &>' requested here
  for (const auto &Entry : enumerate(Layout.StreamMap)) {
                           ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2056:28: note: candidate template ignored: couldn't infer template argument 'R'
template <typename R> bool all_equal(R &&Range) {
                           ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2064:28: note: candidate template ignored: couldn't infer template argument 'T'
template <typename T> bool all_equal(std::initializer_list<T> Values) {
                           ^
1 error generated.
kuhar added a comment.Mar 17 2023, 4:10 PM

Hi @aprantl,

What are the requirements for building with modules enabled? I tried this locally but it didn't get very far, not sure if my system compiler & standard library are new enough (clang14).
If you can reproduce it on your end, could you check if applying D146231 fixes it? My guess is that we may need to 'normalize' types passed to all_equal to size_t.

kuhar added a comment.Mar 17 2023, 4:15 PM

Edit: Ah no, now I see that only one range is passed to the enumerate in ExplainOutputStyle.cpp. In that case we have exactly one type passed to the initialized list so I don't see how that'd fail. Checking other things...

kuhar added a comment.Mar 17 2023, 4:31 PM

I've just tried on my mac and can reproduce it with clang from xcode

$ clang --version
Apple clang version 14.0.0 (clang-1400.0.29.202)
Target: arm64-apple-darwin22.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

CMake command: cmake ../llvm-project/llvm -GNinja -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=1 -DLLVM_ENABLE_MODULES=1
Build command: ninja llvm-pdbutil

kuhar added a comment.Mar 17 2023, 4:56 PM

@aprantl This seems to me like a host compiler bug. I came up with a workaround: https://reviews.llvm.org/D146340.

also seeing similar error in downstream windows build of llvm.

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

also seeing similar error in downstream windows build of llvm.

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

also seeing similar error in downstream windows build of llvm.

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

Apologies - I was mistaken. We are actually seeing the issue with VS 2022 and not VS2019. I've done a bit more investigation and have discovered:
19.29.30133 (VS 2019 16.11.0) - works
19.31.31107 (VS2022 17.1) - fails
19.34.31933 (VS2022 17.4) - works

kuhar added a comment.Mar 25 2023, 4:17 PM

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

Apologies - I was mistaken. We are actually seeing the issue with VS 2022 and not VS2019. I've done a bit more investigation and have discovered:
19.29.30133 (VS 2019 16.11.0) - works
19.31.31107 (VS2022 17.1) - fails
19.34.31933 (VS2022 17.4) - works

I tried reproducing this but I don't know where to get this specific version from. I tried the earliest VS2022 release (17.0.0) from https://learn.microsoft.com/en-us/visualstudio/releases/2022/release-history#fixed-version-bootstrappers:

Microsoft (R) C/C++ Optimizing Compiler Version 19.30.30705 for x64

And llvm compiled fine for me.

kuhar added a comment.EditedMar 25 2023, 6:28 PM

@dstuttard I was able to reproduce it on 17.1 and submited a fix for review: https://reviews.llvm.org/D146893. Could you check this resolved the build failures that you see?

The exact version that I used was: 17.1.0 February 15, 2022, 17.1.32210.238, MSVC (19.31.31104).