Filter out intrinsics if we have other import candidates to suggest

Fixes #97618

Also open to just sorting these candidates to be last. Pretty easy to modify the code to do that, too.

Introduce `-Zvirtual-function-elimination` codegen flag

Fixes #68262

This PR adds a codegen flag `-Zvirtual-function-elimination` to enable the VFE optimization in LLVM. To make this work, additonal  information has to be added to vtables ([`!vcall_visibility` metadata](https://llvm.org/docs/TypeMetadata.html#vcall-visibility-metadata) and a `typeid` of the trait). Furthermore, instead of just `load`ing functions, the [`llvm.type.checked.load` intrinsic](https://llvm.org/docs/LangRef.html#llvm-type-checked-load-intrinsic) has to be used to map functions to vtables.

For technical details of the changes, see the commit messages.

I also tested this flag on https://github.com/tock/tock on different boards to verify that this fixes the issue https://github.com/tock/tock/issues/2594. This flag is able to improve the size of the resulting binary by about 8k-9k bytes by removing the unused debug print functions.

[Rendered documentation update](https://github.com/flip1995/rust/blob/pk-vfe/src/doc/rustc/src/codegen-options/index.md#virtual-function-elimination)

Use valtrees as the type-system representation for constant values

This is not quite ready yet, there are still some problems with pretty printing and symbol mangling and `deref_const` seems to not work correctly in all cases.

Mainly opening now for a perf-run (which should be good to go, despite the still existing problems).

r? `@oli-obk`

cc `@lcnr` `@RalfJung`

Integrate measureme's hardware performance counter support.

*Note: this is a companion to https://github.com/rust-lang/measureme/pull/143, and duplicates some information with it for convenience*

**(much later) EDIT**: take any numbers with a grain of salt, they may have changed since initial PR open.

## Credits

I'd like to start by thanking `@alyssais,` `@cuviper,` `@edef1c,` `@glandium,` `@jix,` `@Mark-Simulacrum,` `@m-ou-se,` `@mystor,` `@nagisa,` `@puckipedia,` and `@yorickvP,` for all of their help with testing, and valuable insight and suggestions.
Getting here wouldn't have been possible without you!

(If I've forgotten anyone please let me know, I'm going off memory here, plus some discussion logs)

## Summary

This PR adds support to `-Z self-profile` for counting hardware events such as "instructions retired" (as opposed to being limited to time measurements), using the `rdpmc` instruction on `x86_64` Linux.

While other OSes may eventually be supported, preliminary research suggests some kind of kernel extension/driver is required to enable this, whereas on Linux any user can profile (at least) their own threads.

Supporting Linux on architectures other than x86_64 should be much easier (provided the hardware supports such performance counters), and was mostly not done due to a lack of readily available test hardware.
That said, 32-bit `x86` (aka `i686`) would be almost trivial to add and test once we land the initial `x86_64` version (as all the CPU detection code can be reused).

A new flag `-Z self-profile-counter` was added, to control which of the named `measureme` counters is used, and which defaults to `wall-time`, in order to keep `-Z self-profile`'s current functionality unchanged (at least for now).

The named counters so far are:
* `wall-time`: the existing time measurement
    * name chosen for consistency with `perf.rust-lang.org`
    * continues to use `std::time::Instant` for a nanosecond-precision "monotonic clock"
* `instructions:u`: the hardware performance counter usually referred to as "Instructions retired"
    * here "retired" (roughly) means "fully executed"
    * the `:u` suffix is from the Linux `perf` tool and indicates the counter only runs while userspace code is executing, and therefore counts no kernel instructions
        * *see [Caveats/Subtracting IRQs](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Subtracting-IRQs) for why this isn't entirely true and why `instructions-minus-irqs:u` should be preferred instead*
* `instructions-minus-irqs:u`: same as `instructions:u`, except the count of hardware interrupts ("IRQs" here for brevity) is subtracted
    * *see [Caveats/Subtracting IRQs](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Subtracting-IRQs) for why this should be preferred over `instructions:u`*
* `instructions-minus-r0420:u`: experimental counter, same as `instructions-minus-irqs:u` but subtracting an undocumented counter (`r0420:u`) instead of IRQs
    * the `rXXXX` notation is again from Linux `perf`, and indicates a "raw" counter, with a hex representation of the low-level counter configuration - this was picked because we still don't *really* know what it is
    * this only exists for (future) testing and isn't included/used in any comparisons/data we've put together so far
    * *see [Challenges/Zen's undocumented 420 counter](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Epilogue-Zen’s-undocumented-420-counter) for details on how this counter was found and what it does*

---

There are also some additional commits:
* ~~see [Challenges/Rebasing *shouldn't* affect the results, right?](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Rebasing-*shouldn’t*-affect-the-results,-right) for details on the changes to `rustc_parse` and `rustc_trait_section` (the latter far more dubious, and probably shouldn't be merged, or not as-is)~~
  *  **EDIT**: the effects of these are no long quantifiable, the PR includes reverts for them
* ~~see [Challenges/`jemalloc`: purging will commence in ten seconds](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#jemalloc-purging-will-commence-in-ten-seconds) for details on the `jemalloc` change~~
  * this is also separately found in #77162, and we probably want to avoid doing it by default, ideally we'd use the runtime control API `jemalloc` offers (assuming that can stop the timer that's already running, which I'm not sure about)
  * **EDIT**: until we can do this based on `-Z` flags, this commit has also been reverted
* the `proc_macro` change was to avoid randomized hashing and therefore ASLR-like effects

---

**(much later) EDIT**: take any numbers with a grain of salt, they may have changed since initial PR open.

#### Write-up / report

Because of how extensive the full report ended up being, I've kept most of it [on `hackmd.io`](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view), but for convenient access, here are all the sections (with individual links):
<sup>(someone suggested I'd make a backup, so [here it is on the wayback machine](http://web.archive.org/web/20201127164748/https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view) - I'll need to remember to update that if I have to edit the write-up)</sup>

* [**Motivation**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Motivation)

* [**Results**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Results)
    * [**Overhead**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Overhead)
    *Preview (see the report itself for more details):*

    |Counter|Total<br>`instructions-minus-irqs:u`|Overhead from "Baseline"<br>(for all 1903881<br>counter reads)|Overhead from "Baseline"<br>(per each counter read)|
    |-|-|-|-|
    |Baseline|63637621286 ±6||
    |`instructions:u`|63658815885 ±2|&nbsp;&nbsp;+21194599 ±8|&nbsp;&nbsp;+11|
    |`instructions-minus-irqs:u`|63680307361 ±13|&nbsp;&nbsp;+42686075 ±19|&nbsp;&nbsp;+22|
    |`wall-time`|63951958376 ±10275|+314337090 ±10281|+165|

    * [**"Macro" noise (self time)**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#“Macro”-noise-(self-time))
    *Preview (see the report itself for more details):*

    || `wall-time` (ns) | `instructions:u` | `instructions-minus-irqs:u`
    -: | -: | -: | -:
    `typeck` | 5478261360 ±283933373 (±~5.2%) | 17350144522 ±6392 (±~0.00004%) | 17351035832.5 ±4.5 (±~0.00000003%)
    `expand_crate` | 2342096719 ±110465856 (±~4.7%) | 8263777916 ±2937 (±~0.00004%) | 8263708389 ±0 (±~0%)
    `mir_borrowck` | 2216149671 ±119458444 (±~5.4%) | 8340920100 ±2794 (±~0.00003%) | 8341613983.5 ±2.5 (±~0.00000003%)
    `mir_built` | 1269059734 ±91514604 (±~7.2%) | 4454959122 ±1618 (±~0.00004%) | 4455303811 ±1 (±~0.00000002%)
    `resolve_crate` | 942154987.5 ±53068423.5 (±~5.6%) | 3951197709 ±39 (±~0.000001%) | 3951196865 ±0 (±~0%)

    * [**"Micro" noise (individual sampling intervals)**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#“Micro”-noise-(individual-sampling-intervals))

* [**Caveats**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Caveats)
    * [**Disabling ASLR**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Disabling-ASLR)
    * [**Non-deterministic proc macros**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Non-deterministic-proc-macros)
    * [**Subtracting IRQs**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Subtracting-IRQs)
    * [**Lack of support for multiple threads**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Lack-of-support-for-multiple-threads)

* [**Challenges**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Challenges)
    * [**How do we even read hardware performance counters?**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#How-do-we-even-read-hardware-performance-counters)
    * [**ASLR: it's free entropy**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#ASLR-it’s-free-entropy)
    * [**The serializing instruction**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#The-serializing-instruction)
    * [**Getting constantly interrupted**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Getting-constantly-interrupted)
    * [**AMD patented time-travel and dubbed it `SpecLockMap`<br><sup>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;or: "how we accidentally unlocked `rr` on AMD Zen"</sup>**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#AMD-patented-time-travel-and-dubbed-it-SpecLockMapnbspnbspnbspnbspnbspnbspnbspnbspor-“how-we-accidentally-unlocked-rr-on-AMD-Zen”)
    * [**`jemalloc`: purging will commence in ten seconds**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#jemalloc-purging-will-commence-in-ten-seconds)
    * [**Rebasing *shouldn't* affect the results, right?**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Rebasing-*shouldn’t*-affect-the-results,-right)
    * [**Epilogue: Zen's undocumented 420 counter**](https://hackmd.io/sH315lO2RuicY-SEt7ynGA?view#Epilogue-Zen’s-undocumented-420-counter)

The offset in the llvm.type.checked.load intrinsic differs on 32 bit platforms

This adds the typeid and `vcall_visibility` metadata to vtables when the
-Cvirtual-function-elimination flag is set.

The typeid is generated in the same way as for the
`llvm.type.checked.load` intrinsic from the trait_ref.

The offset that is added to the typeid is always 0. This is because LLVM
assumes that vtables are constructed according to the definition in the
Itanium ABI. This includes an "address point" of the vtable. In C++ this
is the offset in the vtable where information for RTTI is placed. Since
there is no RTTI information in Rust's vtables, this "address point" is
always 0. This "address point" in combination with the offset passed to
the `llvm.type.checked.load` intrinsic determines the final function
that should be loaded from the vtable in the
`WholeProgramDevirtualization` pass in LLVM. That's why the
`llvm.type.checked.load` intrinsics are generated with the typeid of the
trait, rather than with that of the function that is called. This
matches what `clang` does for C++.

The vcall_visibility metadata depends on three factors:

1. LTO level: Currently this is always fat LTO, because LLVM only
   supports this optimization with fat LTO.
2. Visibility of the trait: If the trait is publicly visible, VFE
   can only act on its vtables after linking.
3. Number of CGUs: if there is more than one CGU, also vtables with
   restricted visibility could be seen outside of the CGU, so VFE can
   only act on them after linking.

To reflect this, there are three visibility levels: Public, LinkageUnit,
and TranslationUnit.

Add the intrinsic

declare {i8*, i1} @llvm.type.checked.load(i8* %ptr, i32 %offset, metadata %type)

This is used in the VFE optimization when lowering loading functions
from vtables to LLVM IR. The `metadata` is used to map the function to
all vtables this function could belong to. This ensures that functions
from vtables that might be used somewhere won't get removed.

This function computes a Itanium-like typeid for a trait_ref. This is
required for the VFE optimization in LLVM. It is used to map
`llvm.type.checked.load` invocations, that is loading the function from
a vtable, to the vtables this function could be from.

It is important to note that `typeid`s are not unique. So multiple
vtables of the same trait can share `typeid`s.

To apply the optimization the `Virtual Function Elim` module flag has to
be set. To apply this optimization post-link the `LTOPostLink` module
flag has to be set.

Adds the virtual-function-elimination unstable compiler flag and a check
that this flag is only used in combination with -Clto. LLVM can only
apply this optimization with fat LTO.

Rollup of 5 pull requests

Successful merges:

 - #97869 (BTree: tweak internal comments)
 - #97935 (Rename the `ConstS::val` field as `kind`.)
 - #97948 (lint: add diagnostic translation migration lints)
 - #98042 (Fix compat_fn option method on miri)
 - #98069 (rustdoc:  remove link on slice brackets)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup

rustdoc:  remove link on slice brackets

This is #91778, take two.

Fixes #91173

The reason I'm reevaluating this change is #97668, which makes fully-generic slices link to the slice docs page. This fixes some downsides in the original PR, where `Box<[T]>`, for example, was not linked to the primitive.slice.html page. In this PR, the `[T]` inside is still a link.

The other major reason for wanting to reevaluate this is the changed color scheme. When this feature was first introduced in rustdoc, primitives were a different color from structs and enums. This way, eagle-eyed users could figure out that the square brackets were separate links from the structs inside. Now, all types have the same color, so a significant fraction of users won't even know the links are there unless they pay close attention to the status bar or use an accessibility tool that lists all links on the page.

Fix compat_fn option method on miri

This change is required to make `WaitOnAddress` work with rust-lang/miri#2231

lint: add diagnostic translation migration lints

Introduce allow-by-default lints for checking whether diagnostics are written in
`SessionDiagnostic` or `AddSubdiagnostic` impls and whether diagnostics are translatable. These lints can be denied for modules once they are fully migrated to impls and translation.

These lints are intended to be temporary - once all diagnostics have been changed then we can just change the APIs we have and that will enforce these constraints thereafter.

r? `````@oli-obk`````

Rename the `ConstS::val` field as `kind`.

And likewise for the `Const::val` method.

Because its type is called `ConstKind`. Also `val` is a confusing name
because `ConstKind` is an enum with seven variants, one of which is
called `Value`. Also, this gives consistency with `TyS` and `PredicateS`
which have `kind` fields.

The commit also renames a few `Const` variables from `val` to `c`, to
avoid confusion with the `ConstKind::Value` variant.

r? `@BoxyUwU`

BTree: tweak internal comments

⬆ rust-analyzer

r? `@ghost`

Remove RegionckMode in favor of calling new skip_region_resolution

Simple cleanup. We can skip a bunch of stuff for places where NLL does the region checking, so skip earlier.

r? rust-lang/types

And likewise for the `Const::val` method.

Because its type is called `ConstKind`. Also `val` is a confusing name
because `ConstKind` is an enum with seven variants, one of which is
called `Value`. Also, this gives consistency with `TyS` and `PredicateS`
which have `kind` fields.

The commit also renames a few `Const` variables from `val` to `c`, to
avoid confusion with the `ConstKind::Value` variant.

Sync rustfmt subtree

Rollup of 4 pull requests

Successful merges:

 - #95211 (Improve parser diagnostics)
 - #95243 (Add Apple WatchOS compile targets)
 - #97385 (Add WIP stable MIR crate)
 - #97508 (Harden bad placeholder checks on statics/consts)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup

Harden bad placeholder checks on statics/consts

Resubmission of #89161
Fixes https://github.com/rust-lang/rust/issues/88643

In #83739, I added a check for trait objects on statics/consts but it wasn't robust. `is_suggestable_infer_ty` fn does a more strict check and finds more bad placeholders. See https://github.com/rust-lang/rust/pull/89161#issuecomment-934690300 for the more detailed explanation.

r? `@pnkfelix` as you're the reviewer of the previous PR

Add WIP stable MIR crate

r? ``@pnkfelix``

Discussion about this happend in the SMIR meeting yesterday. Some info can be found at https://rust-lang.zulipchat.com/#narrow/stream/320896-project-stable-mir/topic/dev.20plan.20mtg/near/283774691

Add Apple WatchOS compile targets

Hello,

I would like to add the following target triples for Apple WatchOS as Tier 3 platforms:

armv7k-apple-watchos
arm64_32-apple-watchos
x86_64-apple-watchos-sim
There are some pre-requisites Pull Requests:
https://github.com/rust-lang/compiler-builtins/pull/456 (merged)
https://github.com/alexcrichton/cc-rs/pull/662 (pending)
https://github.com/rust-lang/libc/pull/2717 (merged)

There will be a subsequent PR with standard library changes for WatchOS.  Previous compiler and library changes were in a single PR (https://github.com/rust-lang/rust/pull/94736) which is now closed in favour of separate PRs.

Many thanks!
Vlad.

### Tier 3 Target Requirements

Adds support for Apple WatchOS compile targets.

Below are details on how this target meets the requirements for tier 3:

>   tier 3 target must have a designated developer or developers (the "target maintainers") on record to be CCed when issues arise regarding the target. (The mechanism to track and CC such developers may evolve over time.)

`@deg4uss3r` has volunteered to be the target maintainer. I am also happy to help if a second maintainer is required.

> Targets must use naming consistent with any existing targets; for instance, a target for the same CPU or OS as an existing Rust target should use the same name for that CPU or OS. Targets should normally use the same names and naming conventions as used elsewhere in the broader ecosystem beyond Rust (such as in other toolchains), unless they have a very good reason to diverge. Changing the name of a target can be highly disruptive, especially once the target reaches a higher tier, so getting the name right is important even for a tier 3 target.

Uses the same naming as the LLVM target, and the same convention as other Apple targets.

> Target names should not introduce undue confusion or ambiguity unless absolutely necessary to maintain ecosystem compatibility. For example, if the name of the target makes people extremely likely to form incorrect beliefs about what it targets, the name should be changed or augmented to disambiguate it.

I don't believe there is any ambiguity here.

> Tier 3 targets may have unusual requirements to build or use, but must not create legal issues or impose onerous legal terms for the Rust project or for Rust developers or users.

I don't see any legal issues here.

> The target must not introduce license incompatibilities.
> Anything added to the Rust repository must be under the standard Rust license (MIT OR Apache-2.0).
> The target must not cause the Rust tools or libraries built for any other host (even when supporting cross-compilation to the target) to depend on any new dependency less permissive than the Rust licensing policy. This applies whether the dependency is a Rust crate that would require adding new license exceptions (as specified by the tidy tool in the rust-lang/rust repository), or whether the dependency is a native library or binary. In other words, the introduction of the target must not cause a user installing or running a version of Rust or the Rust tools to be subject to any new license requirements.
> If the target supports building host tools (such as rustc or cargo), those host tools must not depend on proprietary (non-FOSS) libraries, other than ordinary runtime libraries supplied by the platform and commonly used by other binaries built for the target. For instance, rustc built for the target may depend on a common proprietary C runtime library or console output library, but must not depend on a proprietary code generation library or code optimization library. Rust's license permits such combinations, but the Rust project has no interest in maintaining such combinations within the scope of Rust itself, even at tier 3.
> Targets should not require proprietary (non-FOSS) components to link a functional binary or library.
> "onerous" here is an intentionally subjective term. At a minimum, "onerous" legal/licensing terms include but are not limited to: non-disclosure requirements, non-compete requirements, contributor license agreements (CLAs) or equivalent, "non-commercial"/"research-only"/etc terms, requirements conditional on the employer or employment of any particular Rust developers, revocable terms, any requirements that create liability for the Rust project or its developers or users, or any requirements that adversely affect the livelihood or prospects of the Rust project or its developers or users.

I see no issues with any of the above.

> Neither this policy nor any decisions made regarding targets shall create any binding agreement or estoppel by any party. If any member of an approving Rust team serves as one of the maintainers of a target, or has any legal or employment requirement (explicit or implicit) that might affect their decisions regarding a target, they must recuse themselves from any approval decisions regarding the target's tier status, though they may otherwise participate in discussions.
> This requirement does not prevent part or all of this policy from being cited in an explicit contract or work agreement (e.g. to implement or maintain support for a target). This requirement exists to ensure that a developer or team responsible for reviewing and approving a target does not face any legal threats or obligations that would prevent them from freely exercising their judgment in such approval, even if such judgment involves subjective matters or goes beyond the letter of these requirements.

Only relevant to those making approval decisions.

> Tier 3 targets should attempt to implement as much of the standard libraries as possible and appropriate (core for most targets, alloc for targets that can support dynamic memory allocation, std for targets with an operating system or equivalent layer of system-provided functionality), but may leave some code unimplemented (either unavailable or stubbed out as appropriate), whether because the target makes it impossible to implement or challenging to implement. The authors of pull requests are not obligated to avoid calling any portions of the standard library on the basis of a tier 3 target not implementing those portions.

core and alloc can be used. std support will be added in a subsequent PR.

> The target must provide documentation for the Rust community explaining how to build for the target, using cross-compilation if possible. If the target supports running tests (even if they do not pass), the documentation must explain how to run tests for the target, using emulation if possible or dedicated hardware if necessary.

Use --target=<target> option to cross compile, just like any target. Tests can be run using the WatchOS simulator (see https://developer.apple.com/documentation/xcode/running-your-app-in-the-simulator-or-on-a-device).

> Tier 3 targets must not impose burden on the authors of pull requests, or other developers in the community, to maintain the target. In particular, do not post comments (automated or manual) on a PR that derail or suggest a block on the PR based on a tier 3 target. Do not send automated messages or notifications (via any medium, including via `@)` to a PR author or others involved with a PR regarding a tier 3 target, unless they have opted into such messages.
> Backlinks such as those generated by the issue/PR tracker when linking to an issue or PR are not considered a violation of this policy, within reason. However, such messages (even on a separate repository) must not generate notifications to anyone involved with a PR who has not requested such notifications.

I don't foresee this being a problem.

> Patches adding or updating tier 3 targets must not break any existing tier 2 or tier 1 target, and must not knowingly break another tier 3 target without approval of either the compiler team or the maintainers of the other tier 3 target.
> In particular, this may come up when working on closely related targets, such as variations of the same architecture with different features. Avoid introducing unconditional uses of features that another variation of the target may not have; use conditional compilation or runtime detection, as appropriate, to let each target run code supported by that target.

No other targets should be affected by the pull request.

Improve parser diagnostics

This pr fixes https://github.com/rust-lang/rust/issues/93867 and contains a couple of diagnostics related changes to the parser.
Here is a short list with some of the changes:
- don't suggest the same thing that is the current token
- suggest removing the current token if the following token is one of the suggestions (maybe incorrect)
- tell the user to put a type or lifetime after where if there is none (as a warning)
- reduce the amount of tokens suggested (via the new eat_noexpect and check_noexpect methods)

If any of these changes are undesirable, i can remove them, thanks!