[InstCombine] reduce code duplication; NFC

[libc++] Add myself to the credits.

Noticed while updating the credits for the to_chars patch.

[libc++] Remove support for Clang 9 and older.

I encountered this while reviewing an unrelated patch. Will land after
the CI passes.

Reviewed By: #libc, Mordante

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

[SCEV] Turn validity check in getExistingSCEV into assert (NFC).

Now that we track users of SCEV expressions, we should be able to always
invalidate containing expressions.

With that, I think the case where a value gets removed but
SCEVs containing references to it should not be possible any longer.
Turn check into an assert.

This slightly reduces compile-time:

NewPM-O3: -0.27%
NewPM-ReleaseThinLTO: -0.21%
NewPM-ReleaseLTO-g: -0.26%

http://llvm-compile-time-tracker.com/compare.php?from=c3dc6b081da6ba503e67d260033f81f61eb38ea3&to=95a4a028b1f1dd0bc3d221435953b7d2c031b3d5&stat=instructions

Reviewed By: nikic

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

[libc++][format] Adds formatting benchmarks.

These benchmarks will be used to test the performance inpact of the next
set of optimization patches.

Reviewed By: ldionne, #libc

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

[sanitizer] Remove storeIds and use padding of StackDepotNode

Depends on D114489.

Reviewed By: morehouse, dvyukov

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

[LV] Fix incorrectly marking a pointer indvar as 'scalar'.

collectLoopScalars should only add non-uniform nodes to the list if they
are used by a load/store instruction that is marked as CM_Scalarize.

Before this patch, the LV incorrectly marked pointer induction variables
as 'scalar' when they required to be widened by something else,
such as a compare instruction, and weren't used by a node marked as
'CM_Scalarize'. This case is covered by sve-widen-phi.ll.

This change also allows removing some code where the LV tried to
widen the PHI nodes with a stepvector, even though it was marked as
'scalarAfterVectorization'. Now that this code is more careful about
marking instructions that need widening as 'scalar', this code has
become redundant.

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

NFC: Simplify sve-widen-phi.ll by unrolling once.

The unroll factor > 1 has little value for what is being tested.

[sanitizer] Switch StackStore from pointers to 32bit IDs

Depends on D114488.

Reviewed By: morehouse, dvyukov, kstoimenov

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

[mlir] Enable MLIRDialectUtilsTests

Also remove `TooFewDims` test which tried to create an invalid AffineMap.
The creation of an invalid AffineMap is rejected by `willBeValidAffineMap`,
as a result we can deprecate the test.

Reviewed By: bondhugula

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

[ARM] CSINC/CSINV patterns from CMOV

We sometimes end up generating CMOV with constant operands that can be
simplified to CSINC or CSINV under Arm-8.1m. This adds some simple
patterns for them.

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

[Target] Use range-based for loops (NFC)

[ARM] Fold away unnecessary CSET/CMPZ

Codegen from expanded vector operations can end up with unnecessary
CMPZ/CSINC, of the form:
  CSXYZ A, B, C1 (CMPZ (CSINC 0, 0, C2, D), 0)

These can be converted to remove the CMPZ and CSINC, depending on the
condition.
  if C1==NE -> CSXYZ A, B, C2, D
  if C1==EQ -> CSXYZ A, B, NOT(C2), D

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

[PowerPC] Regenerate ppc64-P9-vabsd.ll tests

[DwarfCompileUnit] Set parent DIE right after creating a local entity

No functional changes intended.

Before this patch DwarfCompileUnit::createScopeChildrenDIE() and
DwarfCompileUnit::createAndAddScopeChildrenDIE() used to emit child subtrees
and then when all the children get created, attach them to a parent scope DIE.
However, when a DIE doesn't have a parent, all the requests for its unit DIE
fail.

Currently, this is not a big issue since it isn't usually needed to know unit DIE
for a local (function-scoped) entity. But once we introduce lexical blocks as
a valid scope for global variables (static locals) and type DIEs, any requests
for a unit DIE need to be guarded against local scope due to the potential
absence of the DIE's parent.

To avoid the aforementioned issue, this patch refactors a few DwarfCompileUnit
methods to support the idea of attaching a DIE to its parent as close to the
creation of this DIE as possible.

Reviewed By: ellis

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

[SCEV] Simplify forgetSymbolicName() (NFCI)

With the recently introduced tracking as well as D113349, we can
greatly simplify forgetSymbolicName(). In fact, we can simply
replace it with forgetMemoizedResults().

What forgetSymbolicName() used to do is to walk the IR use-def
chain to find all SCEVs that mention the SymbolicName. However,
thanks to use tracking, we can now determine the relevant SCEVs
in a more direct way. D113349 is needed to also clear out the
actual IR to SCEV mapping in ValueExprMap.

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

[SCEV] Simplify invalidation after BE count calculation (NFCI)

After backedge taken counts have been calculated, we want to
invalidate all addrecs and dependent expressions in the loop,
because we might compute better results with the newly available
backedge taken counts. Previously this was done with a forgetLoop()
style use-def walk. With recent improvements to SCEV invalidation,
we can instead directly invalidate any SCEVs using addrecs in this
loop. This requires a great deal less subtlety to avoid invalidating
more than necessary, and in particular gets rid of the hack from
D113349. The change is similar to D114263 in spirit.

[ARM] Extra testing for v2i1 types. NFC

This adds extra tests for various operations from making the v2i1 type
legal.

[DSE] Optimize defining access of defs while walking upwards.

This patch extends the code that walks memory defs upwards to find
clobbering accesses to also try to optimize the clobbering defining
access.

We should be able to find set the optimized access of our starting def
(KillingDef), if the following holds:

 1. It is the first call of getDomMemoryDef for KillingDef (so Current
    ==  KillingDef->getDefiningAccess().
 2. No potentially aliasing defs are skipped.

Then if a (partly) aliasing def is encountered, it can be used as
optimized access for KillingDef. No further optimizations can be
applied to KillingDef.

I'd appreciate a careful look, as the existing documentation is not too
clear on what is expected for optimized accesses.

The motivation for this patch is to use the optimized accesses to cover
more cases of redundant stores as follow-up to D111727.

Reviewed By: nikic

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

[NVPTX][AsmPrinter] Avoid removing globals before calling AsmPrinter::doFinalization()

Instead of removing globals from a module, we, it seems, can just override
AsmPrinter::emitGlobalVariable() to do nothing as NVPTXAsmPrinter already
emitted globals by this time and we don't want to do it twice.

Reviewed By: tra

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

Reland [SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this introduces an additional
flag on forgetMemoizedResults() to not remove SCEVUnknown phis from
the value map. The invalidation after BECount calculation wants to
leave these alone and skips them in its own use-def walk, but we can
still end up invalidating them via forgetMemoizedResults() if there
is another IR value with the same SCEV. This is intended as a temporary
workaround only, and the need for this should go away once the
getBackedgeTakenInfo() invalidation is refactored in the spirit of
D114263.

-----

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrote to ValueExprMap in a few places,
  without updating ExprValueMap. Add a helper to ensures they stay
  consistent. The adjustment in forgetSymbolicName() explicitly
  drops the old value from the map, so that we don't rely on it
  being overwritten.
* forgetMemoizedResultsImpl() was dropping the SCEV from
  ExprValueMap, but not dropping the corresponding entries from
  ValueExprMap.

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

[ARM] implement support for ALU/LDR PC-relative group relocations

Currently, LLD does not support the complete set of ARM group relocations.
Given that I intend to start using these in the Linux kernel [0], let's add
support for these.

This implements the group processing as documented in the ELF psABI. Notably,
this means support is dropped for very far symbol references that also carry a
small component, where the immediate is rotated in such a way that only part of
it wraps to the other end of the 32-bit word. To me, it seems unlikely that
this is something anyone could be relying on, but of course I could be wrong.

[0] https://lore.kernel.org/r/20211122092816.2865873-8-ardb@kernel.org/

Reviewed By: peter.smith, MaskRay

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

[test] Use -passes syntax in Feature/OperandBundles lit tests

Simply use the new PM syntax instead of the deprecated legacy PM
syntax when specifying the opt pipeline in some regression tests.

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

[test] Use -passes in lit tests for the UpdateTestChecks tool

The UpdateTestChecks tool itself does not care about which pass
manager that is used in the opt invocation. So the lit tests that
are verifying the behavior of the UpdateTestChecks tool is updated
to use the new-PM syntax (-passes=) when specifying the pass pipeline
in the test cases that are used for verifying the UpdateTestChecks
tool.

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

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
In this patch focus has been put on test cases for ConstantMerge,
ConstraintElimination, CorrelatedValuePropagation, GlobalDCE,
GlobalOpt, SCCP, TailCallElim and PredicateInfo.

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

[RISCV] Emit DWARF location expression for RVV stack objects.

VLENB is the length of a vector register in bytes. We use
<vscale x 64 bits> to represent one vector register. The dwarf offset is
VLENB * scalable_offset / 8.

For the mask vector, it occupies one vector register.

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

[Target] Use range-based for loops (NFC)

Fixed broken build under GCC 5.4.

This diff fixes broken build caused by D108550. Under GCC 5, auto lambdas that capture this require `this->` for member calls.

Reviewed By: bondhugula

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

[ELF][test] Test that .o definition does not inherit .so STV_PROTECTED

Test %t2.so %t.o beside %t.o %t2.so

[libcxx][NFC] Add tests for associative containers key_comp and value_comp

Add missing tests to improve associative containers code coverage:
 - Tests for key_comp() and value_comp() observers
 - Tests for std::map and std::multimap value_compare member class

Reviewed by: ldionne, rarutyun, #libc

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

[ELF] Simplify Symbol::extract. NFC

[sanitizer] Switch StackStore to 8 MiB blocks

Larger blocks are more convenient for compressions.
Blocks are allocated with MmapNoReserveOrDie to save some memory.

Also it's 15% faster on StackDepotBenchmarkSuite

Depends on D114464.

Reviewed By: morehouse

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

[InstSimplify] Fold X {lshr,udiv} C <u X --> true for nonzero X, non-identity C

This eliminates the bounds check in Rust code like

pub fn mid(data: &[i32]) -> i32 {
  if data.is_empty() { return 0; }
  return data[data.len()/2];
}

(from https://blog.sigplan.org/2021/11/18/undefined-behavior-deserves-a-better-reputation/)

Alive proofs:
lshr https://alive2.llvm.org/ce/z/nyTu8D
udiv https://alive2.llvm.org/ce/z/CNUZH7

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

[compiler-rt][CMake] Support powerpcspe build

Reviewed By: jhibbits, MaskRay

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

[compiler-rt][CMake] Support powerpc32 on Linux

Reviewed By: MaskRay

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

Revert "[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency"

This reverts commit bee8dcda1f01831808885ea23f9ac1467ce660f5.

Some sanitizer buildbots fail with:
> Attempt to use a SCEVCouldNotCompute object!

For example:
https://lab.llvm.org/buildbot/#/builders/85/builds/7020/steps/9/logs/stdio

[InstSimplify] baseline tests for icmp of lshr/udiv fold (NFC)

Precommits tests for https://reviews.llvm.org/D114279

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

[flang] Fix reversed comparison in RESHAPE() runtime

RESHAPE() fails inappropriately at runtime if the source array
is larger than the result -- which is perfectly valid -- because
of an obviously reversed comparison of their numbers of elements
is activating the runtime asserts meant for the opposite case
(source smaller than result).

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

[mlir] Fix a warning

This patch fixes:

  mlir/lib/IR/MLIRContext.cpp:1020:3: error: use of the 'nodiscard'
  attribute is a C++17 extension [-Werror,-Wc++17-extensions]

[DAG] Restore dropped condition

This was dropped in fcee33bd5a35786d905a40f42ed28d5a988d75eb,
presumably accidentally.

[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this makes
insertValueToMap() resilient against the value already being
present in the map -- previously I only checked this for the
createSimpleAffineAddRec() case, but the same issue can also
occur for the general createNodeForPHI(). In both cases, the
addrec may be constructed and added to the map in a recursive
query trying to create said addrec. In this case, this happens
due to the invalidation when the BE count is computed, which
ends up clearing out the symbolic name as well.

-----

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrote to ValueExprMap in a few places,
  without updating ExprValueMap. Add a helper to ensures they stay
  consistent. The adjustment in forgetSymbolicName() explicitly
  drops the old value from the map, so that we don't rely on it
  being overwritten.
* forgetMemoizedResultsImpl() was dropping the SCEV from
  ExprValueMap, but not dropping the corresponding entries from
  ValueExprMap.

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

[ELF][PPC64] Make --power10-stubs/--no-power10-stubs proper aliases for --power10-stubs={auto,no}

This allows --power10-stubs= and --[no-]power10-stubs to override each other
(they are position dependent in GNU ld).

Also improve --help messages and the manpage.

Note: GNU ld's default "auto" mode uses heuristics to decide whether Power10
instructions are used. Arguably it is a design mistake of R_PPC64_REL24_NOTOC
(acked by the relevant folks on a libc-alpha discussion). We don't implement
"auto", so the default --power10-stubs is the same as "yes".

[MLIR] Avoid creation of buggy affine maps when incorrect values of number of dimensions and number of symbols are provided.

We check whether the maximum index of dimensional identifier present
in the result expressions is less than dimCount (number of dimensional
identifiers) argument passed in the AffineMap::get() and the maximum index
of symbolic identifier present in the result expressions is less than
symbolCount (number of symbolic identifiers) argument passed in AffineMap::get().

Reviewed By: nicolasvasilache, bondhugula

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

[MLIR] Prevent creation of buggy affine map after linearizing collapsed dimensions of source map

Initially we were passing wrong numSymbols argument while calling
AffineMap::get() for creaating affine map with linearized result
expressions. The main problems was the number of symbols of the newly
to be created map may be different from that of the source map, as
new symbolic identifiers may be introduced while creating strided layout
linearized expressions.

Reviewed By: nicolasvasilache, bondhugula

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

[ELF] Rename fetch to extract

The canonical term is "extract" (GNU ld documentation, Solaris's `-z *extract`
options). Avoid inventing a term and match --why-extract. (ld64 prefers "load"
but the word is overloaded too much)

Mostly MFC, except for --help messages and the header row in
--print-archive-stats output.

[DAG] Pull out repeated isLittleEndian() calls. NFC.

[MLIR] Allow `Idempotent` trait to be applied to binary ops.

Add `Idempotent` trait to `arith.{andi,ori}`.

Reviewed By: mehdi_amini

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

[libc++] Trigger rebuild of the Docker image so we get a new nightly Clang

[mlir][Vector] Support 0-D vectors in `BroadcastOp`

This changes the op to produce `AnyVectorOfAnyRank` following mostly the code for 1-D vectors.

Depends On D114598

Reviewed By: nicolasvasilache

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

[mlir][Standard] Support 0-D vectors in `SplatOp`

This changes the op to produce `AnyVectorOfAnyRank` and implements this by just
inserting the element (skipping the shuffle that we do for the 1-D case).

Depends On D114549

Reviewed By: nicolasvasilache

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

[MLIR] Simplex: fix a bug when rolling back a Simplex with no solutions

Previously, when adding a constraint to a Simplex that is already marked
as having no solutions (marked empty), the Simplex would be marked empty again,
and a second UnmarkEmpty entry would be pushed to the undo log. When rolling
back, Simplex should be unmarked empty only after rolling back past the
creation of the first constraint that made it empty.

Reviewed By: Groverkss

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

[llvm-cov][NFC] Add missing character to fix docs buildbot break.

[libc] Make string entrypoints mutualy exclusive.

For example, strcpy does not pull memcpy now.

Reviewed By: gchatelet

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

[Target] Use range-based for loops (NFC)

[MLIR] Simplex::pivot: also update the redundant rows when pivoting

Previously, the pivot function would only update the non-redundant rows when
pivoting. This is incorrect because in some cases, when rolling back past a
`detectRedundant` call, the basis being used could be different from that which
was used at the time of returning from the `detectRedundant` call. Therefore,
it is important to update the redundant rows as well during pivots. This could
also be triggered by pivots that occur when testing successive constraints for
being redundant in `detectRedundant` after some initial constraints are marked redundant.

Reviewed By: Groverkss

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

[LLVM][llvm-cov] Inclusive language: rename option -name-whitelist to -name-allowlist

Renamed the option for llvm-cov and changed variable names to use more
inclusive terms. Also changed the binary for the test.

Reviewed By: alanphipps

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

[libc++] Properly handle errors happening during Lit configuration

Instead of silently swallowing errors that happen during Lit configuration
(for example trying to obtain compiler macros but compiling fails), raise
an exception with some amount of helpful information.

This should avoid the possibility of silently configuring Lit in a bogus
way, and also provides more helpful information when things fail.

Note that this requires a bit more finesse around how we handle some
failing configuration checks that we would previously return None for.

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

[libc++] Add missing __format__ attributes

-Wformat-nonliteral was turned on in https://reviews.llvm.org/D112927,
however we forgot to apply some __format__ attributes in Linux specific
code paths, which led to warnings when building on Linux. This patch
addresses that oversight.

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

Revert "Reland "[lldb] Remove non address bits when looking up memory regions""

This reverts commit fac3f20de55769d028bd92220e74f22fa57dd4b2.

I found this has broken how we detect the last memory region in
GetMemoryRegions/"memory region" command.

When you're debugging an AArch64 system with pointer authentication,
the ABI plugin will remove the top bit from the end address of the last
user mapped area.

(lldb)
[0x0000fffffffdf000-0x0001000000000000) rw- [stack]

ABI plugin removes anything above the 48th bit (48 bit virtual addresses
by default on AArch64, leaving an address of 0.

(lldb)
[0x0000000000000000-0x0000000000400000) ---

You get back a mapping for 0 and get into an infinite loop.

[clangd] IncludeCleaner: Attribute symbols from non self-contained headers to their parents

When a symbol comes from the non self-contained header, we recursively uplift
the file we consider used to the first includer that has a header guard. We
need to do this while we still have FileIDs because every time a non
self-contained header is included, it gets a new FileID but is later
deduplicated by HeaderID and it's not possible to understand where it was
included from.

Based on D114370.

Reviewed By: sammccall

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

[SLP]Improve analysis/emission of vector operands for alternate nodes.

Compiler has an analysis for perfect diamond matching but it does not
support nodes with main/alternate opcodes. The problem is that the
scalars themselves are different and might not match directly with other
nodes, but operands and main/alternate opcodes might match and compiler
might reuse some previously emitted vector instructions. Need to include
this analysis in the cost model and actual vector instructions emission
process.

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

[pstl] Fix incorrect usage of std::invoke_result

std::invoke_result takes function object type and arguments separately
(unlike std::result_of) so, std::invoke_result_t<F()> usage is
incorrect.

On the other hand, we don't need std::invoke() semantics here at all. So
just simplifying the code without extra dependency and use trailing
return type as the fix.

Reviewed By: MikeDvorskiy

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

[mlir][OpenMP] Add support for SIMD modifier

Add support for SIMD modifier in OpenMP worksharing loops.

Reviewed By: ftynse

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

[SLP][NFC]Add a test for gathered instructions in loop, NFC.

[Bug 49018][lldb] Fix incorrect help text for 'memory write' command

Certain commands like 'memory write', 'register read' etc all use
the OptionGroupFormat options but the help usage text for those
options is not customized to those commands.

One such example is:

  (lldb) help memory read
           -s <byte-size> ( --size <byte-size> )
               The size in bytes to use when displaying with the selected format.
  (lldb) help memory write
   -s <byte-size> ( --size <byte-size> )
               The size in bytes to use when displaying with the selected format.

This patch allows such commands to overwrite the help text for the options
in the OptionGroupFormat group as needed and fixes help text of memory write.

llvm.org/pr49018.

Reviewed By: DavidSpickett

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

[SCEV] Turn check in createSimpleAffineAddRec to assertion. (NFC)

Accum is guaranteed to be defined outside L (via Loop::isLoopInvariant
checks above). I think that should guarantee that the more powerful
ScalarEvolution::isLoopInvariant also determines that the value is loop
invariant.

Reviewed By: nikic

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

[mlir][linalg][bufferize][NFC] InsertSliceOp no-copy detection as PostAnalysis

There is special logic for InsertSliceOp to check if a memcpy is needed. This change extracts that piece of code and makes it a PostAnalysisStep.

The purpose of this change is to untangle `bufferize` from BufferizationAliasInfo. (Not fully there yet.)

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

[clangd] Record information about non self-contained headers in IncludeStructure

This will be useful for IncludeCleaner.

Reviewed By: sammccall

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

Provide a definition for OperationPosition::kDown

This isn't necessary in C++17, but C++14 still requires it.

[PDL] fix unused variable warning in Release builds

[tsan] Relax atexit5.cpp a bit more so it's not as dependent on the standard library implementation

[clang][deps] NFC: Extract function

This commits extracts a couple of nested conditions into a separate function with early returns, making the control flow easier to understand.

Added line numbers to the debug output of PDL bytecode.

This is a small diff that splits out the debug output for PDL bytecode. When running bytecode with debug output on, it is useful to know the line numbers where the PDLIntepr operations are performed. Usually, these are in a single MLIR file, so it's sufficient to print out the line number rather than the entire location (which tends to be quite verbose). This debug output is gated by `LLVM_DEBUG` rather than `#ifndef NDEBUG` to make it easier to test.

Reviewed By: rriddle

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

Multi-root PDL matching using upward traversals.

This is commit 4 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review).

This PR integrates the various components (root ordering algorithm, nondeterministic execution of PDL bytecode) to implement multi-root PDL matching. The main idea is for the pattern to specify mulitple candidate roots. The PDL-to-PDLInterp lowering selects one of these roots and "hangs" the pattern from this root, traversing the edges downwards (from operation to its operands) when possible and upwards (from values to its uses) when needed. The root is selected by invoking the optimal matching multiple times, once for each candidate root, and the connectors are determined form the optimal matching. The costs in the directed graph are equal to the number of upward edges that need to be traversed when connecting the given two candidate roots. It can be shown that, for this choice of the cost function, "hanging" the pattern an inner node is no better than from the optimal root.

The following three main additions were implemented as a part of this PR:
1. OperationPos predicate has been extended to allow tracing the operation accepting a value (the opposite of operation defining a value).
2. Predicate checking if two values are not equal - this is useful to ensure that we do not traverse the edge back downwards after we traversed it upwards.
3. Function for for building the cost graph among the candidate roots.
4. Updated buildPredicateList, building the predicates optimal branching has been determined.

Testing: unit tests (an integration test to follow once the stack of commits has landed)

Reviewed By: rriddle

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

Implementation of the root ordering algorithm

This is commit 3 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review).

We form a graph over the specified roots, provided in `pdl.rewrite`, where two roots are connected by a directed edge if the target root can be connected (via a chain of operations) in the underlying pattern to the source root. We place a restriction that the path connecting the two candidate roots must only contain the nodes in the subgraphs underneath these two roots. The cost of an edge is the smallest number of upward traversals (edges) required to go from the source to the target root, and the connector is a `Value` in the intersection of the two subtrees rooted at the source and target root that results in that smallest number of such upward traversals. Optimal root ordering is then formulated as the problem of finding a spanning arborescence (i.e., a directed spanning tree) of minimal weight.

In order to determine the spanning arborescence (directed spanning tree) of minimum weight, we use the [Edmonds' algorithm](https://en.wikipedia.org/wiki/Edmonds%27_algorithm). The worst-case computational complexity of this algorithm is O(_N_^3) for a single root, where _N_ is the number of specified roots. The `pdl`-to-`pdl_interp` lowering calls this algorithm as a subroutine _N_ times (once for each candidate root), so the overall complexity of root ordering is O(_N_^4). If needed, this complexity could be reduced to O(_N_^3) with a more efficient algorithm. However, note that the underlying implementation is very efficient, and _N_ in our instances tends to be very small (<10). Therefore, we believe that the proposed (asymptotically suboptimal) implementation will suffice for now.

Testing: a unit test of the algorithm

Reviewed By: rriddle

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

Introduced iterative bytecode execution.

This is commit 2 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review).

This commit implements the features needed for the execution of the new operations pdl_interp.get_accepting_ops, pdl_interp.choose_op:
1. The implementation of the generation and execution of the two ops.
2. The addition of Stack of bytecode positions within the ByteCodeExecutor. This is needed because in pdl_interp.choose_op, we iterate over the values returned by pdl_interp.get_accepting_ops until we reach finalize. When we reach finalize, we need to return back to the position marked in the stack.
3. The functionality to extend the lifetime of values that cross the nondeterministic choice. The existing bytecode generator allocates the values to memory positions by representing the liveness of values as a collection of disjoint intervals over the matcher positions. This is akin to register allocation, and substantially reduces the footprint of the bytecode executor. However, because with iterative operation pdl_interp.choose_op, execution "returns" back, so any values whose original liveness cross the nondeterminstic choice must have their lifetime executed until finalize.

Testing: pdl-bytecode.mlir test

Reviewed By: rriddle, Mogball

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

[AArch64][SVEIntrinsicOpts] Fix: predicated SVE mul/fmul are not commutative

We can not swap multiplicand and multiplier because the sve intrinsics
are predicated. Imagine lanes in vectors having the following values:
         pg = 0
         multiplicand = 1 (from dup)
         multiplier = 2
The resulting value should be 1, but if we swap multiplicand and multiplier it will become 2,
which is incorrect.

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

[Docs] Removed /Zd flag still mentioned in documentation

https://reviews.llvm.org/D93458 removed the /Zd flag as MSVC doesn't support that syntax. Instead users should be using -gline-tables-only.
The /Zd flag is still mentioned at https://clang.llvm.org/docs/UsersManual.html#clang-cl :   /Zd                     Emit debug line number tables only.

Fix PR52571

Reviewed By: xgupta

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

Defines new PDLInterp operations needed for multi-root matching in PDL.

This is commit 1 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review).

These operations are:
* pdl.get_accepting_ops: Returns a list of operations accepting the given value or a range of values at the specified position. Thus if there are two operations `%op1 = "foo"(%val)` and `%op2 = "bar"(%val)` accepting a value at position 0, `%ops = pdl_interp.get_accepting_ops of %val : !pdl.value at 0` will return both of them. This allows us to traverse upwards from a value to operations accepting the value.
* pdl.choose_op: Iteratively chooses one operation from a range of operations. Therefore, writing `%op = pdl_interp.choose_op from %ops` in the example above will select either `%op1`or `%op2`.

Testing: Added the corresponding test cases to mlir/test/Dialect/PDLInterp/ops.mlir.

Reviewed By: rriddle

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

[libunwind][ARM] Handle end of stack during unwind

When unwind step reaches the end of the stack that means the force unwind should notify the stop function.
This is not an error, it could mean just the thread is cleaned up completely.

Reviewed By: #libunwind, mstorsjo

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

[AMDGPU] Add SIMemoryLegalizer comments to clarify bit usage

Attempt to further document the intended cache policies requested
by different combinations of GLC, SLC and DLC bits.
GFX10 non-temporal stores are updated to set GLC.

Reviewed By: t-tye

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

[GlobalISel] Fold or of shifts to funnel shift.

This change folds a basic funnel shift idiom:
- (or (shl x, amt), (lshr y, sub(bw, amt))) -> fshl(x, y, amt)
- (or (shl x, sub(bw, amt)), (lshr y, amt)) -> fshr(x, y, amt)

This also helps in folding to rotate shift if x and y are equal since we
already have a funnel shift to rotate combine.

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

[LoopVectorize] When tail-folding, don't always predicate uniform loads

In VPRecipeBuilder::handleReplication if we believe the instruction
is predicated we then proceed to create new VP region blocks even
when the load is uniform and only predicated due to tail-folding.

I have updated isPredicatedInst to avoid treating a uniform load as
predicated when tail-folding, which means we can do a single scalar
load and a vector splat of the value.

Tests added here:

  Transforms/LoopVectorize/AArch64/tail-fold-uniform-memops.ll

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

[clang][deps] NFC: Clean up wording (ignored vs minimized)

The filesystem used during dependency scanning does two things: it caches file entries and minimizes source file contents. We use the term "ignored file" in a couple of places, but it's not clear what exactly that means. This commit clears up the semantics, explicitly spelling out this relates to minimization.

[clang][deps] NFC: Remove else after early return

[AArch64][SVE] Generate ASRD instructions for power of 2 signed divides

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

[ARM] Generate VCTP from SETCC

This converts a vector SETCC([0,1,2,..], splat(n), ult) to vctp n, which
can be fewer instructions and prevent the need for constant pool loads.

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

[DAG] SimplifyDemandedVectorElts - attempt to handle ADD(x,x) as single use

If the ADD node is the only user of the repeated operand, then treat this as single use - allows us to peek through shl(x,1) patterns.

[lldb] Fix 'memory write' to not allow specifying values when writing file contents

Currently the 'memory write' command allows specifying the values when
writing the file contents to memory but the values are actually ignored. This
patch fixes that by erroring out when values are specified in such cases.

Reviewed By: DavidSpickett

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

[libcxx] Implement three-way comparison for std::reverse_iterator

This patch implements operator<=> for std::reverse_iterator and
also adds a test that checks that three-way comparison of different
instantiations of std::reverse_iterator works as expected (related to
D113417).

Reviewed By: ldionne, Quuxplusone, #libc

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

[clang] Fix crash on broken parameter declarators

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

[ARM] Add some vctp from setcc tests. NFC

[clang] Change ordering of PreableCallbacks to make sure PP can be referenced in them

Currently, BeforeExecute is called before BeginSourceFile which does not allow
using PP in the callbacks. Change the ordering to ensure it is possible.
This is a prerequisite for D114370.

Originated from a discussion with @kadircet.

Reviewed By: sammccall

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

[CodeGen] Add scalable vector support for lowering of llvm.get.active.lane.mask

Currently the generic lowering of llvm.get.active.lane.mask is done
in SelectionDAGBuilder::visitIntrinsicCall and currently assumes
only fixed-width vectors are used. This patch changes the code to be
more generic and support scalable vectors too. I have added tests
for SVE here:

  CodeGen/AArch64/active_lane_mask.ll

although the code quality leaves a lot to be desired. The code will
be improved significantly in a later patch that makes use of the
SVE whilelo instruction.

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

[mlir][linalg] Simplify the hoist padding tests.

Use primarily matvec instead of matmul to test hoist padding. Test the hoisting only starting from already padded IR. Use one-dimensional tiling only except for the tile_and_fuse test that exercises hoisting on a larger loop nest with fill and pad tensor operations in the backward slice.

Reviewed By: nicolasvasilache

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

[clang][AST] Check context of record in structural equivalence.

The AST structural equivalence check did not differentiate between
a struct and a struct with same name in different namespace. When
type of a member is checked it is possible to encounter such a case
and wrongly decide that the types are similar. This problem is fixed
by check for the namespaces of a record declaration.

Reviewed By: martong

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

[mlir][Vector] Minor formatting fixes in Vector.md

Reviewed By: nicolasvasilache

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

tsan: remember and print function that installed at_exit callbacks

Sometimes stacks for at_exit callbacks don't include any of the user functions/files.
For example, a race with a global std container destructor will only contain
the container type name and our at_exit_wrapper function. No signs what global variable
this is.
Remember and include in reports the function that installed the at_exit callback.
This should give glues as to what variable is being destroyed.

Depends on D114606.

Reviewed By: vitalybuka, melver

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

tsan: add a test for on_exit

Depends on D114605.

Reviewed By: vitalybuka, melver

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

tsan: add test for __cxa_atexit

Add a test for a common C++ bug when a global object is destroyed
while background threads still use it.

Depends on D114604.

Reviewed By: vitalybuka, melver

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