These checks ensure that retained nodes of a DISubprogram belong to the
subprogram.

Tests with incorrect IR are fixed. We should not have variables of one subprogram present in retained nodes of other subprograms.

Also, interface for accessing DISubprogram's retained nodes is slightly
refactored. `DISubprogram::visitRetainedNodes` and
`DISubprogram::forEachRetainedNode` are added to avoid repeating checks
like
```
if (const auto *LV = dyn_cast<DILocalVariable>(N))
  ...
else if (const auto *L = dyn_cast<DILabel>(N))
  ...
else if (const auto *IE = dyn_cast<DIImportedEntity>(N))
  ...
```

Now that #149310 has restricted lifetime intrinsics to only work on
allocas, we can also drop the explicit size argument. Instead, the size
is implied by the alloca.

This removes the ability to only mark a prefix of an alloca alive/dead.
We never used that capability, so we should remove the need to handle
that possibility everywhere (though many key places, including stack
coloring, did not actually respect this).

lifetime.start and lifetime.end are primarily intended for use on
allocas, to enable stack coloring and other liveness optimizations. This
is necessary because all (static) allocas are hoisted into the entry
block, so lifetime markers are the only way to convey the actual
lifetimes.

However, lifetime.start and lifetime.end are currently *allowed* to be
used on non-alloca pointers. We don't actually do this in practice, but
just the mere fact that this is possible breaks the core purpose of the
lifetime markers, which is stack coloring of allocas. Stack coloring can
only work correctly if all lifetime markers for an alloca are
analyzable.

* If a lifetime marker may operate on multiple allocas via a select/phi,
we don't know which lifetime actually starts/ends and handle it
incorrectly (https://github.com/llvm/llvm-project/issues/104776).
* Stack coloring operates on the assumption that all lifetime markers
are visible, and not, for example, hidden behind a function call or
escaped pointer. It's not possible to change this, as part of the
purpose of lifetime markers is that they work even in the presence of
escaped pointers, where simple use analysis is insufficient.

I don't think there is any way to have coherent semantics for lifetime
markers on allocas, while also permitting them on arbitrary pointer
values.

This PR restricts lifetimes to operate on allocas only. As a followup, I
will also drop the size argument, which is superfluous if we always
operate on an alloca. (This change also renders various code handling
lifetime markers on non-alloca dead. I plan to clean up that kind of
code after dropping the size argument as well.)

In practice, I've only found a few places that currently produce
lifetimes on non-allocas:

* CoroEarly replaces the promise alloca with the result of an intrinsic,
which will later be replaced back with an alloca. I think this is the
only place where there is some legitimate loss of functionality, but I
don't think this is particularly important (I don't think we'd expect
the promise in a coroutine to admit useful lifetime optimization.)
* SafeStack moves unsafe allocas onto a separate frame. We can safely
drop lifetimes here, as SafeStack performs its own stack coloring.
* Similar for AddressSanitizer, it also moves allocas into separate
memory.
* LSR sometimes replaces the lifetime argument with a GEP chain of the
alloca (where the offsets ultimately cancel out). This is just
unnecessary. (Fixed separately in
https://github.com/llvm/llvm-project/pull/149492.)
* InferAddrSpaces sometimes makes lifetimes operate on an addrspacecast
of an alloca. I don't think this is necessary.

If we use `CodeExtractor` to extract the block1 into a new function,

```
define void @foo() !dbg !2 {
entry:
  %1 = alloca i32, i64 1, align 4
  %2 = alloca i32, i64 1, align 4
  #dbg_declare(ptr %1, !8, !DIExpression(), !1)
  br label %block1

block1:
  store i32 1, ptr %1, align 4
  store i32 2, ptr %2, align 4
  #dbg_declare(ptr %2, !10, !DIExpression(), !1)
  ret void
}
```

it will look like the extracted function shown below (with some
irrelevent details removed).

```
define internal void @extracted(ptr %arg0, ptr %arg1) { 
newFuncRoot:
  br label %block1

block1:
  store i32 1, ptr %arg0, align 4
  store i32 2, ptr %arg1, align 4
  ret void
}
```

You will notice that it has replaced the usage of values that were in
the parent function (%1 and %2) with the arguments to the new function.
But it did not do the same thing with `#dbg_declare` which was simply
dropped because its location pointed to a value outside of the new
function. Similarly arg0 is without any debug record, although the value
that it replaced had one and we could materialize one for it based on
that.

This is not just a theoretical limitations. `CodeExtractor` is used to
create functions that implement many of the `OpenMP` constructs in
`OMPIRBuilder`. As a result of these limitations, the debug information
is missing from the created functions.

This PR tries to address this problem. It iterates over the input to the
extracted function and looks at their debug uses. If they were present
in the new function, it updates their location. Otherwise it materialize
a similar usage in the new function.

Most of these changes are localized in `fixupDebugInfoPostExtraction`.
Only other change is to propagate function inputs and the replacement
values to it.

---------

Co-authored-by: Tim Gymnich <tim@gymni.ch>
Co-authored-by: Michael Kruse <llvm-project@meinersbur.de>

These date back to when the non-intrinsic format of variable locations
was still being tested and was behind a compile-time flag, so not all
builds / bots would correctly run them. The solution at the time, to get
at least some test coverage, was to have tests opt-in to non-intrinsic
debug-info if it was built into LLVM.

Nowadays, non-intrinsic format is the default and has been on for more
than a year, there's no need for this flag to exist.

(I've downgraded the flag from "try" to explicitly requesting
non-intrinsic format in some places, so that we can deal with tests that
are explicitly about non-intrinsic format in their own commit).

This PR aims to remove undefined behavior from tests.

Verify that the arguments of a naked function are not used. They can
only be referenced via registers/stack in inline asm, not as IR values.
Doing so will result in assertion failures in the backend.

There's probably more that we should verify, though I'm not completely
sure what the constraints are (would it be correct to require that naked
functions are exactly an inline asm call + unreachable, or is more
allowed?)

Fixes https://github.com/llvm/llvm-project/issues/104718.

This patch makes the final major change of the RemoveDIs project, changing the
default IR output from debug intrinsics to debug records. This is expected to
break a large number of tests: every single one that tests for uses or
declarations of debug intrinsics and does not explicitly disable writing
records. 

If this patch has broken your downstream tests (or upstream tests on a
configuration I wasn't able to run):
1. If you need to immediately unblock a build, pass
`--write-experimental-debuginfo=false` to LLVM's option processing for all
failing tests (remember to use `-mllvm` for clang/flang to forward arguments to
LLVM).
2. For most test failures, the changes are trivial and mechanical, enough that
they can be done by script; see the migration guide for a guide on how to do
this: https://llvm.org/docs/RemoveDIsDebugInfo.html#test-updates
3. If any tests fail for reasons other than FileCheck check lines that need
updating, such as assertion failures, that is most likely a real bug with this
patch and should be reported as such.

For more information, see the recent PSA:
https://discourse.llvm.org/t/psa-ir-output-changing-from-debug-intrinsics-to-debug-records/79578

CodeExtractor shifts dbg.value intrinsics out of the region being
extracted and updates them to be appropriate in the extracted function.
With new non-intrinsic variable locations, we need to manually do this
too, with DPValues.

Most of this patch shifts and refactors some utilities in
fixupDebugInfoPostExtraction so that we can add a single extra helper
lambda that iterates over DPValues and applies update-utilities. We also
have to assign the IsNewDbgInfoFormat flag in a bunch of places -- this
normally gets set the moment you insert a block into a function (or
function into a module), however a few blocks are constructed here
before being inserted, thus we have to do some manual setup.

Tested via LoopExtractor_alloca.ll, which invokes debugify.

BlockFrequencyInfo calculates block frequencies as Scaled64 numbers but as a last step converts them to unsigned 64bit integers (`BlockFrequency`). This improves the factors picked for this conversion so that:

* Avoid big numbers close to UINT64_MAX to avoid users overflowing/saturating when adding multiply frequencies together or when multiplying with integers. This leaves the topmost 10 bits unused to allow for some room.
* Spread the difference between hottest/coldest block as much as possible to increase precision.
* If the hot/cold spread cannot be represented loose precision at the lower end, but keep the frequencies at the upper end for hot blocks differentiable.