[lldb] Simplify check for nill value in breakpoint_function_callback.test

[NFC][CSKY] Resort the instruction description in td

Resort the instruction description in td to make it easy to upstream more instructions and add predicts later.

[libc] Add hardware implementations of fma and fmaf for x86_64 and aarch64.

The current generic implementation of the fmaf function has been moved
to the FPUtil directory. This allows one use the fma operation from
implementations of other math functions like the trignometric functions
without depending on/requiring the fma/fmaf/fmal function targets. If
this pattern ends being convenient, we will switch all generic math
implementations to this pattern.

Reviewed By: lntue

Differential Revision: https://reviews.llvm.org/D100811

Revert "[Driver] Support default libc++ library location on Darwin"

This reverts the following commits because it breaks
TestAppleSimulatorOSType.py on GreenDragon [1].

caff17e503fe81d69e90dd69b14f5149659f9db4
f5efe0aa048b2bd3363b3a53efe9ae7367244801
ae8b2cab67408a043a4fe964d16e4803553c4ee0

[1] http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/31346/

[X86] Support some missing intrinsics

Support for _mm512_i32logather_pd, _mm512_mask_i32logather_pd,
_mm512_i32logather_epi64, _mm512_mask_i32logather_epi64, _mm512_i32loscatter_pd,
_mm512_mask_i32loscatter_pd, _mm512_i32loscatter_epi64,
_mm512_mask_i32loscatter_epi64.

Differential Revision: https://reviews.llvm.org/D100368

[RISCV] Add missing SEW=64 tests to vmslt-rv32.ll. NFC

[mlir] Support hoisting whole affine for loops in LICM

Reviewed By: bondhugula

Differential Revision: https://reviews.llvm.org/D100512

[dfsan] Enable origin tracking with fast8 mode

All related instrumentation tests have been updated.

Reviewed By: stephan.yichao.zhao

Differential Revision: https://reviews.llvm.org/D100903

[sanitizer] Fix glibc sparc build and add GetTls support

sanitizer_linux_libcdep.cpp doesn't build for Linux sparc (with minimum support
but can build) after D98926. I wasn't aware because the file didn't mention
`__sparc__`.

While here, add the relevant support since it does not add complexity
(the D99566 approach).  Adds an explicit `#error` for unsupported
non-Android Linux and FreeBSD architectures.

ThreadDescriptorSize is only used by lsan to scan thread-specific data keys in
the thread control block.

On TLS Variant II architectures (i386/x86_64/s390/sparc), our dl_iterate_phdr
based approach can cover the region from the first byte of the static TLS block
(static TLS surplus) to the thread pointer.
We just need to extend the range to include the first few members of struct
pthread. offsetof(struct pthread, specific_used) satisfies the requirement and
has not changed since 2007-05-10. We don't need to update ThreadDescriptorSize
for each glibc version.

Technically we could use the 524/1552 for x86_64 as well but there is potential
risk that large applications with thousands of shared object dependency may
dislike the time complexity increase if there are many threads, so I don't make
the simplification for now.

Differential Revision: https://reviews.llvm.org/D100892

Make sure PHIElimination doesn't copy debug locations across basic blocks.

PHIElimination may insert copy instructions in multiple basic
blocks. Moving debug locations across basic block boundaries would be
misleading as illustrated by the test case.

rdar://75463656

Differential Revision: https://reviews.llvm.org/D100886

[WebAssembly] Update README. NFC.

This is just a cleanup of the very high level stuff.  I'm sure there is
more to update here but I'll leave that to others and/or a followup.

Differential Revision: https://reviews.llvm.org/D100888

[lld-macho] Skip platform checks for a few libSystem re-exports

XCode 12 ships with mismatched platforms for these libraries,
so this hack is necessary...

Fixes PR49799.

Reviewed By: #lld-macho, gkm, smeenai

Differential Revision: https://reviews.llvm.org/D100913

[FuncAttrs] Always preserve FunctionAnalysisManagerCGSCCProxy

FunctionAnalysisManagerCGSCCProxy should not be preserved if any of its
keys may be invalid. Since we are not removing/adding functions in
FuncAttrs, it's fine to preserve it.

Reviewed By: asbirlea

Differential Revision: https://reviews.llvm.org/D100893

[CMake][llvm] avoid changing global flags (may be used outside of llvm)

Changing global flags can break builds of projects that include/build
llvm as a sub-project, as the effect is global. Ideally we would
disable this warning at the directory level instead, but the obvious
way (disabling warning D9025) isn't supported. At least we can limit
the effect to only MSVC.

Patch by Jim Radford.

Differential Revision: https://reviews.llvm.org/D100900

Revert "[InstCombine] Recognize `((x * y) s/ x) !=/== y` as an signed multiplication overflow check (PR48769)"

This reverts commit 13ec913bdf500e2354cc55bf29e2f5d99e0c709e.

This commit introduces new uses of the overflow checking intrinsics that
depend on implementations in compiler-rt, which Windows users generally
do not link against. I filed an issue (somewhere) to make clang
auto-link the builtins library to resolve this situation, but until that
happens, it isn't reasonable for the optimizer to introduce new link
time dependencies.

[mlir] Disallow broadcast dimensions on TransferWriteOp.

The current implementation allows for TransferWriteOps with broadcasts that do not make sense. E.g., a broadcast could write a vector into a single (scalar) memory location, which is effectively the same as writing only the last element of the vector.

Differential Revision: https://reviews.llvm.org/D100842

Revert "Allow invokable sub-classes of IntrinsicInst"

This reverts commit d87b9b81ccb95217181ce75515c6c68bbb408ca4.

Post commit review raised concerns, reverting while discussion happens.

[Clang, builtins] Added aligned_alloc, memalign support

Revert "[InstCombine] `sext(trunc(x)) --> sext(x)` iff trunc is NSW (PR49543)"

I forgot about the case where we sign-extend to width smaller than the original.

This reverts commit 1e6ca23ab8e350c7bab5d7f93e4d3dee18d180cc.

Revert "[InstCombine] "Bypass" NUW trunc of lshr if we are going to sext the result (PR49543)"

I forgot about the case where we sign-extend to width smaller than the original.

This reverts commit 41b71f718b94c6f12bbaa670e97cabb070308ed2.

Allow invokable sub-classes of IntrinsicInst

It used to be that all of our intrinsics were call instructions, but over time, we've added more and more invokable intrinsics. According to the verifier, we're up to 8 right now. As IntrinsicInst is a sub-class of CallInst, this puts us in an awkward spot where the idiomatic means to check for intrinsic has a false negative if the intrinsic is invoked.

This change switches IntrinsicInst from being a sub-class of CallInst to being a subclass of CallBase. This allows invoked intrinsics to be instances of IntrinsicInst, at the cost of requiring a few more casts to CallInst in places where the intrinsic really is known to be a call, not an invoke.

After this lands and has baked for a couple days, planned cleanups:
    Make GCStatepointInst a IntrinsicInst subclass.
    Merge intrinsic handling in InstCombine and use idiomatic visitIntrinsicInst entry point for InstVisitor.
    Do the same in SelectionDAG.
    Do the same in FastISEL.

Differential Revision: https://reviews.llvm.org/D99976

[flang][msvc] Fix compilation of RuntimeGtest

Removes alternate spelling 'not' with '!'.

Reviewed by: ashermancinelli, awarzynski, Meinersbur

Differential revision: https://reviews.llvm.org/D100442

[InstCombine] "Bypass" NUW trunc of lshr if we are going to sext the result (PR49543)

This is a more convoluted form of the same pattern "sext of NSW trunc",
but in this case the operand of trunc was a right-shift,
and the truncation chops off just the zero bits that were shifted-in.

[NFC][InstCombine] Add tests for sext-of-trunc-nuw-of-lshr (PR49543)

[InstSimplify] Bypass no-op `and`-mask, using known bits (PR49543)

We already special-cased a few interesting patterns,
but that is strictly less powerful than using KnownBits.

So instead get the known bits for the operand of `and`,
and iff all the unset bits of the `and`-mask are known to be zeros
in the operand, we can omit said `and`.

[NFC][InstSimplify] Add one more test for unneeded 'and'

[InstCombine] `sext(trunc(x)) --> sext(x)` iff trunc is NSW (PR49543)

If we can tell that trunc only chops off sign bits, and not all of them,
then we can simply sign-extend the trunc's source.

[NFC][InstCombine] Add test for sign-extending NSW trunc (PR49543)

[InstCombine] fold shift-of-srem-by-2 to mask+shift

There are several potential srem-by-2 folds
because the result is known {-1,0,1}.

https://alive2.llvm.org/ce/z/LuVyeK

[InstCombine] add tests for srem-by-2; NFC

[WebAssembly] Remove unused known_gcc_test_failures.txt. NFC

Differential Revision: https://reviews.llvm.org/D100887

[lld-link] Warn on exported deleting dtor

MSVC linker has this [[ https://docs.microsoft.com/en-us/cpp/error-messages/tool-errors/linker-tools-warning-lnk4102?view=msvc-160 | warning]], so lld-link should also warn on this.

Differential Revision: https://reviews.llvm.org/D100606

[lld-macho] Ensure segments are laid out contiguously

codesign/libstuff checks that the `__LLVM` segment is directly
before `__LINKEDIT` by checking that `fileOff + fileSize == next segment
fileOff`. Previously, there would be gaps between the segments due to
the fact that their fileOffs are page-aligned but their fileSizes
aren't. In order to satisfy codesign, we page-align fileOff *before*
calculating fileSize. (I don't think codesign checks for the relative
ordering of other segments, so in theory we could do this just for
`__LLVM`, but ld64 seems to do it for all segments.)

Note that we *don't* round up the fileSize of the `__LINKEDIT` segment.
Since it's the last segment, it doesn't need to worry about contiguity;
in addition, codesign checks that the last (hidden) section in
`__LINKEDIT` covers the last byte of the segment, so if we rounded up
`__LINKEDIT`'s size we would have to do the same for its last section,
which is a bother.

While at it, I also addressed a FIXME in the linkedit-contiguity.s test
to cover more `__LINKEDIT` sections.

Reviewed By: #lld-macho, thakis, alexshap

Differential Revision: https://reviews.llvm.org/D100848

[lld-macho] Support subtractor relocations that reference sections

The minuend (but not the subtrahend) can reference a section.

Note that we do not yet properly validate that the subtrahend isn't
referencing a section; I've filed PR50034 to track that.

I've also extended the reloc-subtractor.s test to reorder symbols, to
make sure that the addends are being associated with the minuend (and not
the subtrahend) relocation.

Fixes PR49999.

Reviewed By: #lld-macho, thakis

Differential Revision: https://reviews.llvm.org/D100804

[COST][AARCH64] Improve cost of reverse shuffles for AArch64.

Introduced the cost of thre reverse shuffles for AArch64, currently just
copied the costs for PermuteSingleSrc.

Differential Revision: https://reviews.llvm.org/D100871

[Driver] Don't use capture for InstalledDir

This is another attempt to address the issue introduced in
ae8b2cab67408a043a4fe964d16e4803553c4ee0.

We cannot capture InstalledDir because FileCheck doesn't handle
the backslashes correctly, so instead we just consume the entire
path prefix which is what other tests are doing.

[Driver] Support both slashes

This addresses Windows breakage introduced by
ae8b2cab67408a043a4fe964d16e4803553c4ee0.

Reapply "Look through invertible recurrences in isKnownNonEqual"

I'd reverted this in commit 3b6acb179708ea2f3caf95ace0f134fcbc460333 due to buildbot failures.  This patch contains the fix for said issue.  I'd forgotten to handle the case where two phis in the same block have different operand order.  We canonicalize away from this, but it's still valid IR.  The tests included in this change (as opposed to simply having test output changed), crashed without the fix.

Original commit message follows...

This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle.

(Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.)

Differential Revision: https://reviews.llvm.org/D99912

[flang] Fix assignment of parameterized derived types

We were erroneously emitting error messages for assignments of derived types
where the associated objects were instantiated with non-constant LEN type
parameters.

I fixed this by adding the member function MightBeAssignmentCompatibleWith() to
the class DerivedTypeSpec and calling it to determine whether it's possible
that objects of parameterized derived types can be assigned to each other.  Its
implementation first compares the uninstantiated values of the types.  If they
are equal, it then compares the values of the constant instantiated type
parameters.

I added tests to assign04.f90 to exercise this new code.

Differential Revision: https://reviews.llvm.org/D100868

[AArch64][GlobalISel] Clarify fallback debug print

... to only print when that fallback actually happens.

[WebAssembly] More codegen for f64x2.convert_low_i32x4_{s,u}

af7925b4dd65 added a custom DAG combine for recognizing fp-to-ints of
extract_subvectors that could be lowered to f64x2.convert_low_i32x4_{s,u}
instructions. This commit extends the combines to recognize equivalent
extract_subvectors of fp-to-ints as well.

Differential Revision: https://reviews.llvm.org/D100790

[Driver] Support default libc++ library location on Darwin

Darwin driver currently uses libc++ headers that are part of Clang
toolchain when available (by default ../include/c++/v1 relative to
executable), but it completely ignores the libc++ library itself
because it doesn't pass the location of libc++ library that's part
of Clang (by default ../lib relative to the exceutable) to the linker
always using the system copy of libc++.

This may lead to subtle issues when the compilation fails because the
headers that are part of Clang toolchain are incompatible with the
system library. Either the driver should ignore both headers as well as
the library, or it should always try to use both when available.

This patch changes the driver behavior to do the latter which seems more
reasonable, it makes it easy to test and use custom libc++ build on
Darwin while still allowing the use of system version. This also matches
the Clang driver behavior on other systems.

Differential Revision: https://reviews.llvm.org/D45639

[llvm-objdump] Remove "No" prefixes on variables

...to remove double negation in the code. Requested in D100583.

No behavior change.

Differential Revision: https://reviews.llvm.org/D100849

[flang] Implement IPARITY, PARITY, and FINDLOC reductions

Define APIs for, and implement, these three more recently-introduced
standard reduction transformational intrinsic functions to the runtime.

Differential Revision: https://reviews.llvm.org/D100863

Get Section from resolved_addr in Target::ReadMemory

Landing this fix for Augusto Noronha.  The code is getting the
Section from 'addr' passed in, but it may have been expressed as
a load address when it was created and Target::ReadMemory tries to
convert it to a Section+offset if that's now possible; use the
Section found from that cleanup if it exists.

Differential Revision: https://reviews.llvm.org/D100850

[libcxx] adds `iter_difference_t` and `iter_value_t`

Implements parts of:
    * P0896R4 The One Ranges Proposal

Depends on D99855.

Reviewed By: ldionne, #libc

Differential Revision: https://reviews.llvm.org/D99863

[Compiler-rt] Fix bug when considering CMake path returned by llvm-config.

The previous check was wrong because it only checks that the LLVM CMake
directory exists. However, it's possible that the directory exists but
the `LLVMConfig.cmake` file does not. When this happens we would
incorectly try to include the non-existant file.

To fix this we make the check stricter by checking that the file
we want to include actually exists.

This is a follow up to fd28517d878e1d3d14f492ab659aabdf729fd331.

rdar://76870467

Revert "Look through invertible recurrences in isKnownNonEqual"

This reverts commit be20eae25f50f5ef648aeefa1143e1c31e4410fc.  It appears to have caused a crash on a buildbot (https://lab.llvm.org/buildbot#builders/77/builds/5653).  Reverting while investigating.

Rearrange code to reduce diff for D99687 [nfc]

Adding the switches to reduce diffs.  I'm about to split that into an lshr part and an ashr part, doing the NFC part first makes it easier to maintain both diffs.

clang: Update libstdc++ issue workaround

Add some specificity to libstdc++ hack, perhaps we can remove it at a
later date.

[tests] Expand coverage for D99687

[InstCombine] Recognize `((x * y) s/ x) !=/== y` as an signed multiplication overflow check (PR48769)

We already had support for it's unsigned variant, so simply extend it
to also handle the signed variant.

Fixes https://bugs.llvm.org/show_bug.cgi?id=48769

[NFC][InstCombine] Add tests for signed mul overflow check via mul-sdiv pattern (PR48769)

[NFC][SCEV] Split getLosslessPtrToIntExpr out of getPtrToIntExpr()

[NFC][LoopVectorize] Autogenerate check lines in pr45259.ll

We might as well test all of the codegen here.

[ELF] Don't set versionId on undefined weak lazy symbols

An unfetched lazy symbol (undefined weak) should be considered to have its
original versionId which is VER_NDX_GLOBAL, instead of the lazy symbol's
versionId. (The original versionId cannot be non-VER_NDX_GLOBAL because a
undefined versioned symbol is an error.)

The regression was introduced in D77280 when making version scripts work
with lazy symbols fetched by LTO calls.

Fix PR49915

Differential Revision: https://reviews.llvm.org/D100624

Fix clang Visual Studio build instructions

Change cd ..\.. to cd llvm-project (the former is probably a leftover
of the old svn instructions)

Committer: Adrian McCarthy <amccarth@google.com>

Differential Revision: https://reviews.llvm.org/D68321

[mlir] Make some functions public to use custom TypeIDs

Currently, it is only possible to register an operation or a type
when the TypeID is defined at compile time. Same with InterfaceMaps
which can only be defined with compile-time defined interfaces.

With those changes, it is now possible to register types/operations
with custom TypeIDs. This is necessary to define new operations/types
at runtime.

Differential Revision: https://reviews.llvm.org/D99084

Look through invertible recurrences in isKnownNonEqual

This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle.

(Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.)

Differential Revision: https://reviews.llvm.org/D99912

[libcxx][test] Construct non-empty containers in iterator's debug mode tests

The debug mode tests for map/set's iterators construct empty
containers, making the code after the first increment meaningless.
It's never executed since the tests exit earlier.

It doesn't seem to be intentional, so the patch makes the tests
to construct containers that include at least one element.

Reviewed By: curdeius, Quuxplusone

Differential Revision: https://reviews.llvm.org/D100029

[docs] Fix doxygen comments wrongly attached to the clang namespace

Looking at the Doxygen-generated documentation for the clang namespace
currently shows several random comments from different parts of the
codebase. These are caused by:

- File doc comments that aren't marked with \file, so they're attached to
  the next declaration, which is usually "namespace clang {".
- Class doc comments placed before the namespace rather than before the
  class.

This commit fixes these comments. The generated doxygen documentation now
has proper docs for several classes and files, and the docs for the clang
namespace is now empty.

Differential Revision: https://reviews.llvm.org/D96738

[mlir][Standard][NFC] Fix op documentation

A couple of standard op examples that use an outdated syntax need an
update.

Differential Revision: https://reviews.llvm.org/D100840

[docs] Use make_unique in FrontendAction example

The code example for "RecursiveASTVisitor based ASTFrontendActions"
was using unique_ptr<X>(new X) when creating the AST consumer; change
it to use make_unique instead. The main function of the same example
already used make_unique.

Differential Revision: https://reviews.llvm.org/D93185

Update tests checks, NFC.

[llvm-objdump] Prefer positive boolean Verbose instead of negative NonVerbose. NFC

Differential Revision: https://reviews.llvm.org/D100791

[test] Add a couple extra tests for recurrence matching in unreachable code

These are salvaged from D100004 as we took a different approach to the fix.

[COST]Add a test for reverse shuffles cost on AArch64, NFC.

[test] Add a couple more tests for D99912

Tolerate missing debug info in the shared_ptr pretty printer.

Certain fields of shared ptr have virtual functions and therefore
have their debug info homed in libc++. But if libc++ wasn't built
with debug info, the pretty printer would fail.

This patch makes the pretty printer tolerate such conditions and
updates the test harness.

This patch significantly reworks a previous attempt.

This addresses https://bugs.llvm.org/show_bug.cgi?id=48937

Differential Revision: https://reviews.llvm.org/D100610

[tests] Update per review comment on D99912

(I'd copy and pasted the wrong test before tweaking, as a result, it wasn't a very good negative test.)

[libcxx][doc] Use Phabricator links.

Use a link to the Phabricator review in the patch column.

Reviewed By: zoecarver, cjdb, #libc

Differential Revision: https://reviews.llvm.org/D100707

[OpenMP] Add OpenMPOpt as a Module pass

Summary:
This patch registers OpenMPOpt as a Module pass in addition to a CGSCC
pass. This is so certain optimzations that are sensitive to intact
call-sites can happen before inlining. The old `openmpopt` pass name is
changed to `openmp-opt-cgscc` and `openmp-opt` calls the Module pass.
The current module pass only runs a single check but will be expanded in
the future.

Reviewed By: jdoerfert

Differential Revision: https://reviews.llvm.org/D99202

[PhaseOrdering] Add second test case for PR36760

Silence MSVC signed/unsigned comparison warning. NFCI.

[mlir] Pass AnalysisManager as optional parameter to analysis ctor, so it can request any other analysis as dependency

Differential Revision: https://reviews.llvm.org/D100274

[clangd] Use dirty filesystem when performing cross file tweaks

Cross file tweaks can now use the dirty buffer contents easily when performing cross file effects.
This can be noted on the DefineOutline tweak, now working when the target file is unsaved

Reviewed By: sammccall

Differential Revision: https://reviews.llvm.org/D93978

[mlir][spirv] Support conversion of extract op from vector<1xT> type

Differential Revision: https://reviews.llvm.org/D100814

[PhaseOrdering] Add test case for PR36760

Ensures that the correct sequence of simplifycfg/instcombine/sroa reduce the IR to just a icmp+select

[X86][SSE] combineX86ShuffleChain - check if we're blending with zero into already zero elements

Add a SelectionDAG::MaskedElementsAreZero helper that wraps SelectionDAG::MaskedValueIsZero testing for entirely zero vector elements

[SLP] Add detection of shuffled/perfect matching of tree entries.

SLP supports perfect diamond matching for the vectorized tree entries
but do not support it for gathered entries and does not support
non-perfect (shuffled) matching with 1 or 2 tree entries. Patch adds
support for this matching to improve cost of the vectorized tree.

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D100495

free(nullptr) does not violate the nofree specification

This fixes a subtle and nasty bug in my 86664638. The problem is that free(nullptr) is well defined (and common).

The specification for the nofree attributes talks about memory objects, and doesn't explicitly address null, but I think it's reasonable to assume that nofree doesn't disallow a call to free(nullptr). If it did, we'd have to prove nonnull on an argument to ever infer nofree which doesn't seem to be the intent.

This was found by Nuno and Alive2 over in https://reviews.llvm.org/D100141#2697374.

Differential Revision: https://reviews.llvm.org/D100779

[libc++] NFC: Normalize `#endif //` comment indentation

GlobalISel: Defer register creation in handleAssignments

This is currently built on top of the SelectionDAG call lowering, but
does not use it the same way. SelectionDAG passes legalized types to
the assignment functions, and the tablegenerated assignment functions
may change the value types expected for registers. This does not
change the types used, just moves the register creation to help fix
this in the future.

Defer the register creation until after all of the assignment
decisions have been made. This will also help have correct tail call
compatibility checking in a future change. Currently it does not work
as expected for any arguments split across multiple registers.

[AMDGPU] Allow multiple uses of the same literal

In GFX10 VOP3 can have a literal, which opens up the possibility of two
operands using the same literal value, which is allowed and only counts
as one use of the constant bus.

AMDGPUAsmParser::validateConstantBusLimitations already knew about this
but SIInstrInfo::verifyInstruction did not.

Differential Revision: https://reviews.llvm.org/D100770

[AArch64] Bump apple-latest CPU alias to apple-a14.

[AArch64] Don't always override CPU for arm64e.

This demotes the apple-a12 CPU selection for arm64e to just be the
last-resort default.  Concretely, this means:
- an explicitly-specified -mcpu will override the arm64e default;
  a user could potentially pick an invalid CPU that doesn't have
  v8.3a support, but that's not a major problem anymore
- arm64e-apple-macos (and variants) will pick apple-m1 instead of
  being forced to apple-a12.

[AArch64] Add apple-m1 CPU, and default to it for macOS.

apple-m1 has the same level of ISA support as apple-a14,
so this is a straightforward mechanical change.  However, that
also means this inherits apple-a14's v8.5a+nobti quirkiness.

rdar://68287159

[gn build] Port 120fa8293e22

[libc++][nfc] Move iterator_traits and related into __iterator/iterator_traits.h.

Based on D100682 and D99855.

(Note: I originally was going to just make this part of D99855, but I decided not to because this patch moves lots of unrelated code around, and I didn't want to make D99855 harder to review because of unrelated code-changes/moves.)

Differential Revision: https://reviews.llvm.org/D100686

GlobalISel: Check for powers of 2 for inverse funnel shift lowering

This doesn't make a practical difference since it would only be broken
if a target actually had a legal non-power-of-2 inverse shift.

[libcxx] makes `iterator_traits` C++20-aware

* adds `iterator_traits` specialisation that supports all expected
  member aliases except for `pointer`
* adds `iterator_traits` specialisations for iterators that meet the
  legacy iterator requirements but might lack multiple member aliases
* makes pointer `iterator_traits` specialisation require objects

Depends on D99854.

Differential Revision: https://reviews.llvm.org/D99855

Revert "[SLP] Add detection of shuffled/perfect matching of tree entries."

This reverts commit daf6e18c55c2ac56bbf0f9de233fb2a1150ee331 to fix the
compiler crash.

[ARM] Limit PerformExtractEltToVMOVRRD to when f64 is legal.

The generic SoftFloatVectorExtract.ll test was failing when run on arm
machines, as it tries to create a f64 under soft float. Limit the
transform to when f64 is legal.

Also add a missing override, as reported in D100244.

AMDGPU/GlobalISel: Fix uitofp/sitofp with non-power-of-2 integers

Ensure target-multiversioning emits deferred declarations

As reported in PR50025, sometimes we would end up not emitting functions
needed by inline multiversioned variants. This is because we typically
use the 'deferred decl' mechanism to emit these.  However, the variants
are emitted after that typically happens.  This fixes that by ensuring
we re-run deferred decls after this happens. Also, the multiversion
emission is done recursively to ensure that MV functions that require
other MV functions to be emitted get emitted.

GlobalISel: Restrict narrow scalar for fptoui/fptosi results

This practically only works for the f16 case AMDGPU uses, not wider
types.

Fixes bug 49710 by failing legalization.

MachineVerifier: Continue reporting errors for copies

This was skipping verification of later copies, but generally the
verifier tries to report as many things wrong as possible in the
function.

[SLP] Add detection of shuffled/perfect matching of tree entries.

SLP supports perfect diamond matching for the vectorized tree entries
but do not support it for gathered entries and does not support
non-perfect (shuffled) matching with 1 or 2 tree entries. Patch adds
support for this matching to improve cost of the vectorized tree.

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D100495

[mlir][StandardToSPIRV] Add support for lowering std.xor on bool to SPIR-V

std.xor ops on bool are lowered to spv.LogicalNotEqual. For Boolean values, xor
and not-equal are the same thing.

Reviewed By: antiagainst

Differential Revision: https://reviews.llvm.org/D100817

[gn build] reformat all gn files

$ git ls-files '*.gn' '*.gni' | xargs llvm/utils/gn/gn.py format

(and manually wrap two comments)