Clean up

Rebase. Fix negative number handling.

Clean up includes

Handle negative numbers WIP. Add integration tests.

Clean up

Rebase

In D144503#4206725, @dstuttard wrote:

In D144503#4204120, @ronlieb wrote:

also seeing similar error in downstream windows build of llvm.

In D144503#4201034, @srj wrote:

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 )??

Do not calculate sizes in non-debug builds

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

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

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

In D144503#4203254, @aprantl wrote:

This somehow broke the -DLLVM_ENABLE_MODULES=1 build:

Can you take a look?

https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/52513/consoleFull#-458239162a1ca8a51-895e-46c6-af87-ce24fa4cd561

In D144503#4201034, @srj wrote:

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 &
        ]

Use adl_size to simplify the implementation and reduce branching.

In D146231#4199846, @dblaikie wrote:

Would std::distance suffice?

Fix outdated usage in AArch64PerfectShuffle

Address comments.

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

LGTM

Update test to check that .contains(x) is preferred over .find(x) when both are available.
Use std::find instead of llvm::find to make the behavior as clear as possible.

FYI, by a quick scan through the patch, it seems like a likely pessimization. Currently, llvm::is_contained performs a linear scan to find the element, while .find(x) is typically O(1) or O(log n). Related discussion on this topic: https://reviews.llvm.org/D146061

Here's an example that landed minutes ago in the tree: https://reviews.llvm.org/D145464

Fix a typo

Delegate to .find when .contains is not available. Improve function documentation.

In D146061#4194853, @nikic wrote:

In D146061#4194752, @kuhar wrote:

Sure, I agree with that. If I have map with a known type like DenseMap I'd rather call .contains(x) directly too. But this is not possible with C++17 containers std::, so I'd argue that until then is_contained(container, x) is more readable than something like container.find(x) != container.end().

I don't think we should promote usage of is_contained() for anything but the linear scan case. I don't want to be left guessing whether this is_contained() is a linear scan, or just a slightly different way to write container.find().

In D146061#4194551, @kazu wrote:

In D146061#4194466, @kuhar wrote:

Then I propose we frame it like this: llvm::is_contained is the (llvm-only) canonical/generic way to check if an element is in the range.

How about something like the (llvm-only) canonical/generic way to check if an element is in the range if a template needs to work with containers that may or may not have the .contains method (like an array and a set).

I'm saying this because I personally find Foo.contains(X) a little more readable than llvm::is_contained(Foo, X), and I would like our code base to look friendly to people new to the LLVM project (with the use of function names present in C++ standards) wherever reasonable to do so. (Sure, std::set::contains is very new, but I expect people to become familiar with this over time.)

In D146061#4194439, @dblaikie wrote:

This one is trickier for me - llvm::is_contained doesn't have a nearby standard equivalent ,so we can choose its behavior more flexibly. But std::find(iter, iter, value) exists in the standard library and there's value in llvm::find(range, value) being pretty close to the same/identical to the standard version - which doesn't optimize to member-find when available.

I would be inclined not to include a member-find optimization in llvm::find for that reason.

I'm undecided about whether that tips in favor of not having member-contains in llvm::is_contained.

Fix test failures. Add a regression test.

I discovered I skipped some existing tests, this doesn't always work. Working on a fix.

This is also consistent with how new C++ range functions are defined, e.g., https://en.cppreference.com/w/cpp/ranges/size that calls member .size when available and does iterator subtraction otherwise.

In D146061#4193557, @nikic wrote:

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

Update lambda signature

Also include clang/ since there's only one function to update

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).

Rebase. Add comments clarifying iterator reference_type requirments.

In D145969#4190390, @nickdesaulniers wrote:

In D145969#4190388, @kuhar wrote:

I'd consider defining a new operator== overload to handle cases like this instead.

On which class? Use or Instruction?

In D145969#4190387, @nickdesaulniers wrote:

I also wonder whether

diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
index abe38aa2a357..04f3df961662 100644
--- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -810,13 +810,13 @@ void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
   int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
   const Instruction *T = BB->getTerminator();
   for (auto CHI : C) {
-    Instruction *Insn = CHI.I;
+    const Instruction *Insn = CHI.I;
     if (!Insn) // No instruction was inserted in this CHI.
       continue;
     // If the Terminator is some kind of "exotic terminator" that produces a
     // value (such as InvokeInst, CallBrInst, or CatchSwitchInst) which the CHI
     // uses, it is not safe to hoist the use above the def.
-    if (!T->use_empty() && is_contained(Insn->operands(), cast<const Value>(T)))
+    if (!T->use_empty() && is_contained(Insn->operands(), T))
       continue;
     if (K == InsKind::Scalar) {
       if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))

would have done the trick. Should I file a bug about llvm::is_contained/std::find/mscv19?

Also rename the test

Rebase. Rename populate function (emulation -> lowering). Do not rely on temporary array refs.

Separately, it would be cool if we could make llvm::is_contained use the contains member when available, instead of doing a linear scan. It seems like a bit of a foot gun to me to have 2 functions with almost identical names but vastly different performance characteristics.