Use pseudo parser for folding ranges

This first version only uses bracket matching. We plan to extend this to
use DirectiveTree as well.

Also includes changes to Token to allow retrieving corresponding token
in token stream of original source file.

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

[Verifier] Make Verifier recognize undef tokens as correct IR

Undef tokens may appear in unreached code as result of RAUW of some optimization,
and it should not be considered as bad IR.

Patch by Dmitry Bakunevich!

Differential Revision: https://reviews.llvm.org/D128904
Reviewed By: mkazantsev

[PowerPC] Add an ISEL pattern for i32 MULLI.

We add the following ISEL pattern for i64 imm in D87384, this patch is for i32.
`mul with (2^N * int16_imm) -> MULLI + RLWINM`

Reviewed By: shchenz

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

[LoopUnroll] Regenerate test checks (NFC)

[LV] Use PHI recipe instead of PredRecipe for subsequent uses.

At the moment, the VPPRedInstPHIRecipe is not used in subsequent uses of
the predicate recipe. This incorrectly models the def-use chains, as all
later uses should use the phi recipe. Fix that by delaying recording of
the recipe.

Reviewed By: Ayal

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

[pseudo] Add bracket recovery for function parameters.

[C++20] [Modules] Handle reachability for deduction guide

Previously, we forget to handle reachability for deduction guide.
The deduction guide is a hint to the compiler. And the deduction guide
should be able to use if the corresponding template decl is reachable.

[IR] Don't treat callbr as indirect terminator

Callbr is no longer an indirect terminator in the sense that is
relevant here (that it's successors cannot be updated). The primary
effect of this change is that callbr no longer prevents formation
of loop simplify form.

I decided to drop the isIndirectTerminator() method entirely and
replace it with isa<IndirectBrInst>() checks. I assume this method
was added to abstract over indirectbr and callbr, but it never
really caught on, and there is nothing left to abstract anymore
at this point.

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

[flang][openacc] Use TableGen to generate the clause parser

This patch introduce an automatic generation of the clause parser from the TableGen
information.

New information can be stored directly in the TableGen file:
- The different aliases that a clause support.
- prefix before a value.
- whether a prefix is optional or not.

Makes it easier to add new clauses and also avoid some error (`write` clause incorrect until now).

This patch is updating only the OpenACC part. A patch with a modification of the OpenMP clause parser will follow.

Reviewed By: kiranchandramohan

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

[obj2yaml] Refactor command line parsing

Similar to D73982 for yaml2obj.

* Hide unrelated options.
* Add an OVERVIEW: message.
* Disallow single-dash long options.

Reviewed By: jhenderson

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

[VP] Implementing expansion pass for VP load and store.

Added function to the ExpandVectorPredication pass to handle VP loads
and stores.

Reviewed By: simoll

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

[CodeGen] Remove unnecessary APInt copy. NFC

[Support][CodeGen] Fix spelling Divison->Division. NFC

[CodeGen] Don't compare bool with integer 0. NFC

The IsAdd field is a bool.

[LegacyPM] Remove WholeProgramDevirt

Unused after LTO removal from legacy optimization passline.

[LegacyPM] Remove FunctionImportLegacyPass

Unused after ThinLTO was removed from legacy optimization pipeline.

[Test] Mode test for pr56243 from LICM to LoopSimplifyCFG

[test] Change -function-import tests to use -passes=

[AMDGPU] Add the uses_dynamic_stack field to the kernel descriptor and the kernel metadata map

This change introduces the dynamic stack boolean field to code-object-v3
and above under the code properties of the kernel descriptor and under
the kernel metadata map of NT_AMDGPU_METADATA. This field corresponds to
the is_dynamic_callstack field of amd_kernel_code_t.

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

[test] Change -lowertypetests tests to use -passes=

[RISCV][NFC] Use more Arrayref in TargetLowering functions.

This patch replaces some foreach with Arrayref, and abstract some same literal array with a variable.

Reviewed By: craig.topper

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

[RISCV] Extend use of SHXADD instructions in RVV spill/reload code.

This patch extends D124824. It uses SHXADD+SLLI to emit 3, 5, or 9 multiplied by a power 2.

Reviewed By: craig.topper

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

[RISCV][test] Precommit test for D129179.

Reviewed By: craig.topper

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

[mlir][Math] Add constant folder for Log10Op.

This patch adds constant folder for Log10Op which only support single and double precision floating-point.

Reviewed By: Mogball

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

[libc++][ranges] Make range algorithms support proxy iterators

Also test all the range algorithms to verify the support.

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

[llvm] Modernize bool literals (NFC)

Identified with modernize-use-bool-literals.

[AVR] Remove redundant void (NFC)

Identified with modernize-redundant-void-arg.

[mlir] Remove unused using (NFC)

Identified with misc-unused-using-decls.

[test] Change test/SampleProfile to use opaque pointers

[libc++] Enable test for already written ranges algorithms

Reviewed By: Mordante, #libc

Spies: libcxx-commits

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

[RISCV] Simplify lowerGlobalAddress. NFC

Remove unused forward declarations (NFC)

Remove redundant return statements (NFC)

Identified with readability-redundant-control-flow.

Ensure newlines at the end of files (NFC)

[LegacyPM] Remove LowerTypeTestsPass

Unused after LTO removal from optimization passline.

[test] Change -lowertypetests tests to -passes=

[LegacyPM] Remove NameAnonGlobalLegacyPass

Unused after LTO removal from optimization passline.

[LegacyPM] Remove CanonicalizeAliasesLegacyPass

Unused after LTO removal from optimization passline.

[LegacyPM] Remove LTO passes from optimization pipeline

Following recent changes removing non-core features of the legacy
PM/optimization pipeline.

[LegacyPM] Remove PGO options from PassManagerBuilder

They have been dead since legacy PGO/SamplePGO passes were removed.

[ARM] Guard VMOVH and VINS patterns.

These instructions are only available when fp is available, so cannot be
used with just +mve. Add predicates to ensure we fall-back under the
right circumstances.

[RISCV] Teach targetShrinkDemandedConstant to handle OR and XOR.

We were only handling AND before, but SimplifyDemandedBits can
also call it for OR and XOR.

[LegacyPM] Remove SampleProfileLoaderLegacyPass

Following recent changes removing non-core features of the legacy
PM/optimization pipeline (e.g. PGO), remove SamplePGO.

[test] Change -sample-profile tests to -passes=

so that we can remove SampleProfileLoaderLegacyPass.

[SystemZ][z/OS] Implement detection and handling for XPLink Leaf procedures.

This PR adds support for creating leaf functions when there are no CSRs used, no function calls are made, no stack frame is acquired, and contain no try/catch/throw statements.

Reviewed By: uweigand

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

[RISCV] Teach RISCVCodeGenPrepare to optimize (i64 (and (zext/sext (i32 X), C1)))

If X is known positive by a dominating condition, we can fill in
ones into the upper bits of C1 if that would allow it to become an
simm12 allowing the use of ANDI.

This pattern often occurs in unrolled loops where the induction
variable has been widened.

To get the best benefit from this, I had to move the pass above
ConstantHoisting which is in addIRPasses. Otherwise the AND constant
is often hoisted away from the AND.

Reviewed By: asb

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

[RISCV] Remove unnecessary use of IRBuilder from RISCVCodeGenPrepare.

We're creating single instruction to replace another instruction.
We can insert using the InsertBefore operand of the constructor.
Then copy the debug location.

[RISCV] Remove Gather/Scatter Opt from the O0 pipeline.

[DAG] Fold (or (and X, C1), (and (or X, Y), C2)) -> (or (and X, C1|C2), (and Y, C2))

Pulled out of D77804

Alive2: https://alive2.llvm.org/ce/z/g61VRe

[DAG] Add or(and(x,c1),and(or(x,y),c2)) tests

Tests for the fold suggested in D77804

Conversion from '__int64' to 'long', possible loss of data

llvm-project\libcxx\test\std\time\time.hms\time.hms.members\seconds.pass.cpp(38): note: see reference to function template instantiation 'long check_seconds<std::chrono::seconds>(Duration)' being compiled
        with
        [
            Duration=std::chrono::seconds
        ]
llvm-project\libcxx\test\std\time\time.hms\time.hms.members\seconds.pass.cpp(31): warning C4244: 'return': conversion from '_Rep' to 'long', possible loss of data
        with
        [
            _Rep=__int64
        ]

Reviewed By: #libc, Mordante

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

fix comment typo to cycle bots

[DAG] computeKnownBits - move UDIV handling to same place as UREM/SREM. NFC.

[DAG] Add MERGE_VALUE computeKnownBits/ComputeNumSignBits handling.

Just forward the value tracking to the operand specified by the ResNo

[LV] Move VPPredInstPHIRecipe::execute to VPlanRecipes.cpp (NFC)

[llvm] Fix header guards (NFC)

Identified with llvm-header-guard.

[AMDGPU] Improve liveness copying in si-optimize-exec-masking-pre-ra

Further improve liveness copying for CC register post optimization
by mirroring live internal splits.
The fixes a bug in register allocation when CC register liveness
is extended across a branches instead of split.

Reviewed By: arsenm

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

[CodeGen] Qualify auto variables in for loops (NFC)

[test] Remove duplicate -sample-profile tests

When -passes=sample-profile is tested, -sample-profile is redundant.

[sanitizer] Compare against the alignment of the latter range trying to find consecutive TLS blocks in GetStaticTlsBoundary

On a mips64el-linux-gnu system, the dynamic linker arranges TLS blocks
like:

    [0] 0xfff7fe9680..0xfff7fe9684, align = 0x4
    [1] 0xfff7fe9688..0xfff7fe96a8, align = 0x8
    [2] 0xfff7fe96c0..0xfff7fe9e60, align = 0x40
    [3] 0xfff7fe9e60..0xfff7fe9ef8, align = 0x8

Note that the dynamic linker can only put [1] at 0xfff7fe9688, not
0xfff7fe9684 or it will be misaligned.  But we were comparing the
distance between two blocks with the alignment of the previous range,
causing GetStaticTlsBoundary fail to merge the consecutive blocks.

Compare against the alignment of the latter range to fix the issue.

Reviewed By: MaskRay

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

[Analysis] Qualify auto variables in for loops (NFC)

[llvm] Wrap multi-statement macro definitions with do ... while (0)

[IndVars] Directly use unsigned integer induction for FPToUI/FPToSI of float induction

Depend on D129358

Reviewed By: nikic

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

[NFC] Remove obsolete all_passes_registration from integration tests.

After https://reviews.llvm.org/D128593 this is not needed (and not available). Was missed in original landing because integration tests do not run on pre-merge.

[mlir] Overhaul C/Python registration APIs to properly scope registration/loading activities.

Since the very first commits, the Python and C MLIR APIs have had mis-placed registration/load functionality for dialects, extensions, etc. This was done pragmatically in order to get bootstrapped and then just grew in. Downstreams largely bypass and do their own thing by providing various APIs to register things they need. Meanwhile, the C++ APIs have stabilized around this and it would make sense to follow suit.

The thing we have observed in canonical usage by downstreams is that each downstream tends to have native entry points that configure its installation to its preferences with one-stop APIs. This patch leans in to this approach with `RegisterEverything.h` and `mlir._mlir_libs._mlirRegisterEverything` being the one-stop entry points for the "upstream packages". The `_mlir_libs.__init__.py` now allows customization of the environment and Context by adding "initialization modules" to the `_mlir_libs` package. If present, `_mlirRegisterEverything` is treated as such a module. Others can be added by downstreams by adding a `_site_initialize_{i}.py` module, where '{i}' is a number starting with zero. The number will be incremented and corresponding module loaded until one is not found. Initialization modules can:

* Perform load time customization to the global environment (i.e. registering passes, hooks, etc).
* Define a `register_dialects(registry: DialectRegistry)` function that can extend the `DialectRegistry` that will be used to bootstrap the `Context`.
* Define a `context_init_hook(context: Context)` function that will be added to a list of callbacks which will be invoked after dialect registration during `Context` initialization.

Note that the `MLIRPythonExtension.RegisterEverything` is not included by default when building a downstream (its corresponding behavior was prior). For downstreams which need the default MLIR initialization to take place, they must add this back in to their Python CMake build just like they add their own components (i.e. to `add_mlir_python_common_capi_library` and `add_mlir_python_modules`). It is perfectly valid to not do this, in which case, only the things explicitly depended on and initialized by downstreams will be built/packaged. If the downstream has not been set up for this, it is recommended to simply add this back for the time being and pay the build time/package size cost.

CMake changes:
* `MLIRCAPIRegistration` -> `MLIRCAPIRegisterEverything` (renamed to signify what it does and force an evaluation: a number of places were incidentally linking this very expensive target)
* `MLIRPythonSoure.Passes` removed (without replacement: just drop)
* `MLIRPythonExtension.AllPassesRegistration` removed (without replacement: just drop)
* `MLIRPythonExtension.Conversions` removed (without replacement: just drop)
* `MLIRPythonExtension.Transforms` removed (without replacement: just drop)

Header changes:
* `mlir-c/Registration.h` is deleted. Dialect registration functionality is now in `IR.h`. Registration of upstream features are in `mlir-c/RegisterEverything.h`. When updating MLIR and a couple of downstreams, I found that proper usage was commingled so required making a choice vs just blind S&R.

Python APIs removed:
  * mlir.transforms and mlir.conversions (previously only had an __init__.py which indirectly triggered `mlirRegisterTransformsPasses()` and `mlirRegisterConversionPasses()` respectively). Downstream impact: Remove these imports if present (they now happen as part of default initialization).
  * mlir._mlir_libs._all_passes_registration, mlir._mlir_libs._mlirTransforms, mlir._mlir_libs._mlirConversions. Downstream impact: None expected (these were internally used).

C-APIs changed:
  * mlirRegisterAllDialects(MlirContext) now takes an MlirDialectRegistry instead. It also used to trigger loading of all dialects, which was already marked with a TODO to remove -- it no longer does, and for direct use, dialects must be explicitly loaded. Downstream impact: Direct C-API users must ensure that needed dialects are loaded or call `mlirContextLoadAllAvailableDialects(MlirContext)` to emulate the prior behavior. Also see the `ir.c` test case (e.g. `  mlirContextGetOrLoadDialect(ctx, mlirStringRefCreateFromCString("func"));`).
  * mlirDialectHandle* APIs were moved from Registration.h (which now is restricted to just global/upstream registration) to IR.h, arguably where it should have been. Downstream impact: include correct header (likely already doing so).

C-APIs added:
  * mlirContextLoadAllAvailableDialects(MlirContext): Corresponds to C++ API with the same purpose.

Python APIs added:
  * mlir.ir.DialectRegistry: Mapping for an MlirDialectRegistry.
  * mlir.ir.Context.append_dialect_registry(MlirDialectRegistry)
  * mlir.ir.Context.load_all_available_dialects()
  * mlir._mlir_libs._mlirAllRegistration: New native extension that exposes a `register_dialects(MlirDialectRegistry)` entry point and performs all upstream pass/conversion/transforms registration on init. In this first step, we eagerly load this as part of the __init__.py and use it to monkey patch the Context to emulate prior behavior.
  * Type caster and capsule support for MlirDialectRegistry

This should make it possible to build downstream Python dialects that only depend on a subset of MLIR. See: https://github.com/llvm/llvm-project/issues/56037

Here is an example PR, minimally adapting IREE to these changes: https://github.com/iree-org/iree/pull/9638/files In this situation, IREE is opting to not link everything, since it is already configuring the Context to its liking. For projects that would just like to not think about it and pull in everything, add `MLIRPythonExtension.RegisterEverything` to the list of Python sources getting built, and the old behavior will continue.

Reviewed By: mehdi_amini, ftynse

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

[BOLT] Add function layout class

This patch adds a dedicated class to keep track of each function's
layout. It also lays the groundwork for splitting functions into
multiple fragments (as opposed to a strict hot/cold split).

Reviewed By: maksfb

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

Revert "[Support] Remove redundant declaration setCurrentDebugTypes (NFC)"

This reverts commit 52232abc230435d4c1e1273d4b857a11f2c7b45b.

This patch breaks builds when NDEBUG is defined.

[Driver] Don't passs --dynamic-linker in -r mode

No behavior change as GNU ld/gold/ld.lld ignore --dynamic-linker in -r mode.
This change makes the intention clearer as we already suppress --dynamic-linker
for -shared, -static, and -static-pie.

Reviewed by: MaskRay, phosek

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

[test] Fix memory leak in validateTargetProfile

Unfortunatly fixing leak expose use-after-free if delete more then one
Compilation for the same Driver, so I am changing validateTargetProfile
to create own Driver each time.

The test was added by D122865.

[libcxx] Replace remaining _LIBCPP_INLINE_VISIBILITY in __support

Replace remaining _LIBCPP_INLINE_VISIBILITY in __support with _LIBCPP_HIDE_FROM_ABI.

Reviewed by: Mordante

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

[Support] Remove redundant declaration setCurrentDebugTypes (NFC)

The function is declared in llvm/include/llvm/Support/Debug.h.

Identified with readability-redundant-declaration.

[CodeGen] Remove redundant declaration createGreedyRegisterAllocator (NFC)

The function is declared in llvm/include/llvm/CodeGen/Passes.h.

Identified with readability-redundant-declaration.

[CodeGen] Use RegClassFilterFunc where appropriate (NFC)

[libc++][AIX] Correct the definition of __regex_word for AIX

Summary:
The patch changes the definition of __regex_word to 0x8000 for AIX because the current definition 0x80 clashes with ctype_base::print (_ISPRINT is defined as 0x80 in AIX ctype.h).

Reviewed by: Mordante, hubert.reinterpretcast, libc++

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

[test] Don't leak DerivedArgList in test

[SDAG] narrow truncated sign_extend_inreg

trunc (sign_ext_inreg X, iM) to iN --> sign_ext_inreg (trunc X to iN), iM

There are improvements on existing tests from this, and there are a pair
of large regressions in D127115 for Thumb2 caused by not folding this
pattern.

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

[Analysis] Remove isArithmeticRecurrenceKind

The last use was removed on Jul 30, 2021 in commit
9d355949937038c32c7608ebb558bbc3984f6340.

[clang-format] Never remove braces in macro definitions

Fixes #56559.

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

[lld-macho] Handle filename being passed in -lto_object_path

Clang passes a filename rather than a directory in -lto_object_path when
using FullLTO. Previously, it was always treated it as a directory, so
lld would crash when it attempted to create temporary files inside it.

Fixes #54805

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

[AMDGPU] Use default member initialization (NFC)

Identified with modernize-use-default-member-init.

[test] Fix leak in test

[PGO][InstrProf][test] Convert to opaque pointers and fix some stale tests

[AMDGPU] Declare TableRef in terms of ArrayRef (NFC)

Visual C++ doesn't support C99 compound literal

Fix test libcxx/test/std/containers/sequences/array/array.creation/to_array.pass.cpp

Reviewed By: #libc, Mordante

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

Tests ignore the return value of sto{meow}, triggering nodiscard warnings in MS STL

Reviewed By: #libc, Mordante

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

Revert rG14364200821f7b2d97edf6e78160c514800d3ec6 "[ARM] Regenerate reg_sequence.ll test checks"

Breaks on some apple machines

[SystemZ] Add funnel shift test coverage

Based off conversations on Issue #56495

[LV] Avoid creating new run-time VF expression for each runtime checks.

At the moment, the cost of runtime checks for scalable vectors is
overestimated due to creating separate vscale * VF expressions for each
check. Instead re-use the first expression.

[clang-format][docs] Fix incorrect 'clang-format 7' option markers

Introduced by 23a5090c6, some style option markers indicated
'clang-format 7', though their respective options were available in
different releases.

[ARM] Regenerate reg_sequence.ll test checks

[DAG] visitINSERT_VECTOR_ELT - refactor BUILD_VECTOR creation from INSERT_VECTOR_ELT chain.

D127595 added the ability to recurse up a (one-use) INSERT_VECTOR_ELT chain to create a BUILD_VECTOR before other combines manage to break the chain, something that is particularly bad in D127115.

The patch generalises this so it doesn't have to build the chain starting from the last element insertion, instead it can now start from any insertion and will recurse up the chain until it finds all elements or finds a UNDEF/BUILD_VECTOR/SCALAR_TO_VECTOR which represents that start of the chain.

Fixes several regressions in D127115

[DAG] visitINSERT_VECTOR_ELT - remove duplicate VT.getVectorNumElements() call. NFC.

Don't sink ptrtoint/inttoptr sequences into non-noop addrspacecasts.

In https://reviews.llvm.org/D30114, support for mismatching address
spaces was introduced to CodeGenPrepare's optimizeMemoryInst, using
addrspacecast as it was argued that only no-op addrspacecasts would be
considered when constructing the address mode. However, by doing
inttoptr/ptrtoint, it's possible to get CGP to emit an addrspace
that's not actually no-op, introducing a miscompilation:

define void @kernel(i8* %julia_ptr) {
  %intptr = ptrtoint i8* %julia_ptr to i64
  %ptr = inttoptr i64 %intptr to i32 addrspace(3)*

  br label %end
end:

  store atomic i32 1, i32 addrspace(3)* %ptr unordered, align 4
  ret void
}

Gets compiled to:

define void @kernel(i8* %julia_ptr) {
end:
  %0 = addrspacecast i8* %julia_ptr to i32 addrspace(3)*
  store atomic i32 1, i32 addrspace(3)* %0 unordered, align 4
  ret void
}

In the case of NVPTX, this introduces a cvta.to.shared, whereas
leaving out the %end block and branch doesn't trigger this
optimization. This results in illegal memory accesses as seen in
https://github.com/JuliaGPU/CUDA.jl/issues/558

In this change, I introduced a check before doing the pointer cast
that verifies address spaces are the same. If not, it emits a
ptrtoint/inttoptr combination to get a no-op cast between address
spaces. I decided against disallowing ptrtoint/inttoptr with
non-default AS in matchOperationAddr, because now its still possible
to look through multiple sequences of them that ultimately do not
result in a address space mismatch (i.e. the second lit test).

[AArch64] Regenerate arm64-vector-ldst.ll test checks

[AArch64] Regenerate arm64-neon-simd-ldst-one.ll test checks

[AArch64] Regenerate arm64-vmax.ll test checks

[AArch64] Regenerate arm64-mul.ll test checks

[mlir][NFC] Fully qualify typenames in SymbolInterfaces.td

[VectorCombine] Only consider shuffle uses with the same type.

The backend getShuffleCosts do not currently handle shuffles that change
size very well. Limit the shuffles we collect to the same type to make
sure they do not cause issues as reported in D128732.

Fix signed/unsigned mismatch